中央研究院 数學研咒所 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