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