Uniform partition extension of combinatorial models
| 报告题目：Uniform partition extension of combinatorial models 报告人：Yeongnan Yeh (叶永南) 研究员 台北中央研究院数学所 报告时间：2013年7月7日（星期日）下午15:00 报告地点： 精正搂二楼学术报告厅 欢迎师生踊跃参加！ Abstract: An n-Dyck path is a lattice path in the first quadrant with starting point (0,0) and endpoint (2n,0), and consisting of two kinds of steps: up-step U=(1,1) and down-step D=(1,-1). Let 12cn=1n+12nn' type="#_x0000_t75"> , called the n-th catalan number, and C(x) the generating function of the catalan sequence. 12cn' type="#_x0000_t75"> counts n-Dyck paths and C(x) satisfies the functional equation 12Cx=1+xC(x)2' type="#_x0000_t75">. An n-free Dyck path is a lattice path by relaxing Dyck paths to the whole plane, not just in the first quadrant. Let 12cn,k' type="#_x0000_t75"> be the number of n-free Dyck paths with k up-steps lying below x-axis. Chung-Feller theorem shows that 12cn,k' type="#_x0000_t75"> is the same as the n-th catalan number 12cn' type="#_x0000_t75"> for k=0,1,…,n. So the model, n-free Dyck paths, is called a uniform partition extension of n-Dyck paths, and the parameter, the number of up-steps lying below x-axis, is called a uniform partition parameter. Let C(x,y) be the ordinary generating function of the sequence 12cn,k' type="#_x0000_t75">. Then C(x,y) has a very simple expression in terms of C(x): 12Cx,y=yCxy-C(x)y-1,' type="#_x0000_t75"> called the function of uniform partition type for C(x). The Chung-Feller theorem on Dyck paths can be derived from the combinatorial interpretation of C(x,y). This implies a method to find a uniform partition extension for a combinatorial model. In this talk, we will give a survey for these results of our series of papers on this research direction.
|