Combinatorial interpretations for a class of algebraic equations and uniform partitions

中央研究院 数學研咒所 Combinatorial interpretations for a class of algebraic equations and uniform partitions Speaker: Yeong-Nan Yeh Institute of mathemetics academia sinica Aug21,2012

Combinatorial interpretations for a class of algebraic equations and uniform partitions Speaker: Yeong-Nan Yeh Institute of mathemetics, Academia sinica Aug. 21, 2012

中央研究院 数學研咒所 Catalan paths An n-Catalan path is a lattice path from(0,0 to(2n, O)in the first quadrant consisting of up step(l, 1)and down-step(1, -1) 第2页

第2页 Catalan paths • An n-Catalan path is a lattice path from (0,0) to (2n,0) in the first quadrant consisting of up￾step (1,1) and down-step (1,-1)

中央研究院 数學研咒所 Catalan number (2n) for n>0 nn+1(n)-(7+1ln! 1,1,2,5,14,42,132,429,1430,4862,16796,, 第3页

第3页 Catanlan number 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, …

中央研究院 数學研咒所 Generating function: C(2)=22 ≥0 Algebaric equation C(z)=1+zC(z)2 第4页

第4页 2 ( ) 1 ( ) Algebaric equation : C z = + zC z   = 0 Generating function : ( ) n n n C z c z

中央研究院 数學研咒所 Motzkin paths An n-Motizkin path is a lattice path from(, 0 to(n, O)in the first quadrant consisting of up step(1, 1), level-step(1, 0)and down-step(1, -1) Motzkin number:1,1,2,4,9,21,51,127,323,835,…, 第5页

第5页 Motzkin paths • An n-Motizkin path is a lattice path from (0,0) to (n,0) in the first quadrant consisting of up￾step (1,1), level-step (1,0) and down-step (1,-1). Motzkin number:1, 1, 2, 4, 9, 21, 51, 127, 323, 835, …

中央研究院 数學研咒所 Generating function: M(2)=>m,z n≥0 Algebaric equation M(z)=1+zM(x)+2M(z)2 第6页

第6页 2 2 ( ) 1 ( ) ( ) Algebaric equation : M z = + zM z + z M z   = 0 Generating function : ( ) n n n M z m z

中央研究院 数學研咒所 Combinatorial structure Generating function f(=) Algebaric equation Catalan path: ( 1, 1),(1,-1)inC(=) C(z)=1+/C2 the first quadrant 1+zC()C(丿 Motzkin path: 1, 1),(1 M(-) M=)=1+2M=)+2/M/ D), (1,0)in the first quadrant =1+M(2)/1+M(2 ?9() 白y=1+·F(z,y) Given an algebaric equation y=1+ zyF(z, y) for arbitrary polynomial F(z,y), how to construct a combinatorial structure such that its generating function f(E) satisfies this equation? f(z)=1+Ef(z)F(=,f(z)) 第7页

第7页 Combinatorial structure Generating function f(z) Algebaric equation Catalan path:(1,1),(1,-1) in the first quadrant C(z) C(z)=1+z[C(z)]2 =1+zC(z)·C(z) Motzkin path:(1,1),(1,- 1),(1,0) in the first quadrant M(z) M(z)=1+zM(z)+z2 [M(z)]2 =1+zM(z)·[1+zM(z)] ??? ??f(z) ◼ Given an algebaric equation for arbitrary polynomial F(z,y) , how to construct a combinatorial structure such that its generating function f(z) satisfies this equation? y =1+ zy • F(z, y) y =1+ zyF(z, y) f (z) =1+ zf (z)F(z, f (z))

中央研究院 数學研咒所 Lattice paths a lattice path is a sequence (p(, v2).(kyg of vectors in the plane with (x1y)∈∠0×么{(0,0)}, where Z and zso are the sets of integers and nonnegative integers respective 第8页

第8页 Lattice paths • A lattice path is a sequence (x1 ,y1 )(x2 ,y2 )…(xk ,yk ) of vectors in the plane with (xi ,yi )∈Z≥0×Z\{(0,0)}, where Z and Z≥0 are the sets of integers and nonnegative integers respectively

中央研究院 数學研咒所 Weight of a lattice path Let w be a function from Zo XZto r, wherer is the set of real numbers For any lattice path P=(x,yu(2, 22).(xkdk define the weight of P, denoted by w(P),as k w(P)=wx,yi) 第9页

第9页 Weight of a lattice path • Let w be a function from Z≥0×Z to R, where R is the set of real numbers. • For any lattice path P=(x1 ,y1 )(x2 ,y2 )…(xk ,yk ) define the weight of P, denoted by w(P), as = = k i i i w P w x y 1 ( ) ( , )

中央研究院 数學研咒所 S-path and S-nonnegative path Let s be a finite subset of zo Xa(0,0) An S-path is a lattice pat th (x1y1)(x2y2).(x2yk) with(xpy)∈S An S-nonnegative path is an S-path in the first quadrant 第10页

第10页 S-path and S-nonnegative path • Let S be a finite subset of Z≥0×Z\{(0,0)}. • An S-path is a lattice path (x1 ,y1 )(x2 ,y2 )…(xk ,yk ) with (xi ,yi )∈S. • An S-nonnegative path is an S-path in the first quadrant