4.6.2 Exponential generating functions The number of r-combinations of multiset S=Loo.,ooa2y. oo.ak: C(r+k-l, r), generating function: ∑C(k+r-1,r) The number of r-permutation of set s=a1,a2,... a}:p(n,r), generating function: p(, ry
▪ 4.6.2 Exponential generating functions ▪ The number of r-combinations of multiset S={·a1 ,·a2 ,…,·ak } : C(r+k-1,r), ▪ generating function: k r r y C k r r y (1 ) 1 ( 1, ) 0 − + − = = The number of r-permutation of set S={a1 ,a2 ,…, ak } :p(n,r), generating function: =0 ( , ) r r p n r y
● ax ax r=0 (1+x)y=∑C( n rX ∑m(n r=0 r=0 Definition 2 The exponential generating function for the sequence ao, aj,..., ang... of real numbers is the infinite series f(x)=∑x=ao+a1x+2x2+…+x”+… 0
▪ C(n,r)=p(n,r)/r! = = + = = n r n r r n r r x x C n r x p n r 0 0 ! (1 ) ( , ) ( , ) = n r r r r x a 0 ! Definition 2: The exponential generating function for the sequence a0 ,a1 ,…,an ,…of real numbers is the infinite series = = + + ++ + = n n r r r x n a x a x a a x r a f x ! 2! ! ( ) 2 2 0 1 0 = = 0 ! ( ) r r ax r ax e
(2) m+m2 +.mI=1 k ≥0 ating Is the number of r-permutatio ns of s given g(x)=gn(x)' g n,(x).. gn(x), where for i=1, 2,., K, gn(x)=1+x+x22+…,+x"!n;! ) The coefficient of x/r!ingn(x)gn2(x)∵…gn(x)is m.+m.+…m=rm1!m2!…mk m≥0
▪ Theorem 4.17: Let S be the multiset {n1·a1 ,n2·a2 ,…,nk·ak } where n1 ,n2 ,…,nk are nonnegative integers. Let br be the number of rpermutations of S. Then the exponential generating function g(x) for the sequence b1 , b2 ,…, bk ,… is given by ▪ g(x)=gn1 (x)·g n2 (x)·…·gnk (x)，where for i=1,2,…,k, ▪ gni (x)=1+x+x2 /2!+…+xni/ni ! . ▪ (1)The coefficient of xr /r! in gn1 (x)·g n2 (x)·…·gnk (x) is + + = 0 1 2 1 2 ! ! ! ! i k m m m m r m m mk r is the number of r - permutatio ns of S ! ! ! ! (2) 0 1 2 1 2 + + = i k m m m m r m m mk r
Example: Let s=(1 a1,.a2,, 1 ag Determine the number r-permutations of s Solution: Let p be the number permutations of s, and g(x)=(1+x)=∑C(n,r)x A(n-)2 =0(n-r)!r!
▪ Example: Let S={1·a1 ,1·a2 ,…,1·ak }. Determine the number r-permutations of S. ▪ Solution: Let pr be the number rpermutations of S, and = = = − = − = = + = k r r k r r k r k r r x n r n x r n r n g x x C n r x 0 0 0 ( )! ! ! !( )! ! ( ) (1 ) ( , )
Example:LetS={oo·a1,o:a2,…,ooa}, Determine the number r-permutations of s Solution: Let p be the number r- permutations of s, gr(x)=(1+x+x2/2!,,+xr/r!+…),then g(x)=(1+x+x2/2!+.+xTr!+.)k=(e)=ek ∑k 0 0
▪ Example: Let S={·a1 ,·a2 ,…,·ak }， Determine the number r-permutations of S. ▪ Solution: Let pr be the number rpermutations of S, ▪ gri(x)=(1+x+x2 /2!+…+xr /r!+…)，then ▪ g(x)=(1+x+x2 /2!+…+xr /r!+…)k=(ex ) k=ekx = = = = 0 0 ! ! ( ) r r r r r r x k r kx