A context-free grammar for peaks and double descents of permutations

doi:10.1016/j.aam.2018.06.004

CORC > 上海财经大学 > 上海财经大学

	A context-free grammar for peaks and double descents of permutations
	Fu, Amy M.
刊名	ADVANCES IN APPLIED MATHEMATICS
	2018-09
卷号	100 页码:179-196
关键词	Context-free grammars Grammatical labeling Exterior peaks Proper double descents
ISSN号	0196-8858
DOI	10.1016/j.aam.2018.06.004
英文摘要	This paper is concerned with the joint distribution of the number of exterior peaks and the number of proper double descents over permutations on [n] = {1, 2,..., n}. The notion of exterior peaks of a permutation was introduced by Aguiar, Bergeron and Nyman in their study of the peak algebra. Gessel obtained the generating function of the number of permutations on [n] with a given number of exterior peaks. On the other hand, by establishing differential equations, Elizalde and Noy derived the generating function for the number of permutations on [n] with a given number of proper double descents. Barry and Basset deduced the generating function of the number of permutations on [n] with no proper double descents. We find a context-free grammar that can be used to compute the number of permutations on [n] with a given number of exterior peaks and a given number of proper double descents. Based on the grammar, the recurrence relation of the number of permutations on [n] with a give number of exterior peaks can be easily obtained. Moreover, we use the grammatical calculus to derive the generating function without solving differential equations. Our formula reduces to the formulas of Gessel, Elizalde-Noy, Barry, and Basset. Finally, from the grammar we establish a relationship between our generating function and the generating function of the joint distribution of the number of peaks and the number of double descents derived by Carlitz and Scoville. (C) 2018 Elsevier Inc. All rights reserved.
WOS研究方向	Mathematics
语种	英语
出版者	ACADEMIC PRESS INC ELSEVIER SCIENCE
WOS记录号	WOS:000442067000010
内容类型	期刊论文
源URL	[http://10.2.47.112/handle/2XS4QKH4/527]
专题	上海财经大学
通讯作者	Fu, Amy M.
作者单位	Shanghai Univ Finance & Econ, Sch Math, Shanghai 200433, Peoples R China
推荐引用方式 GB/T 7714	Fu, Amy M.. A context-free grammar for peaks and double descents of permutations[J]. ADVANCES IN APPLIED MATHEMATICS,2018,100:179-196.
APA	Fu, Amy M..(2018).A context-free grammar for peaks and double descents of permutations.ADVANCES IN APPLIED MATHEMATICS,100,179-196.
MLA	Fu, Amy M.."A context-free grammar for peaks and double descents of permutations".ADVANCES IN APPLIED MATHEMATICS 100(2018):179-196.