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
Example: Let S=( 2.X133'X2, Determine the number 4-permutations of s Solution: Let pr be the number r-permutations of s, g(x)=(1+x+x2/2!)(1+x+x2/2!+x3/3!) Note: pr is coefficient of x/r!. Example: Let S=(2 X13 3 X2, 4 X33. Determine the number of 4-permutations of s so that each of the 3 types of objects occurs even times. Solution: Let pa be the number 4-permutations, g(x)=(1+x2/2)(1+x2/2)(1+x2/2!+x4/4!)
▪ Example：Let S={2·x1 ,3·x2 }，Determine the number 4-permutations of S. ▪ Solution: Let pr be the number r-permutations of S, ▪ g(x)=(1+x+x2 /2!)(1+x+x2 /2!+x3 /3!) ▪ Note: pr is coefficient of xr /r!. ▪ Example：Let S={2·x1 ,3·x2 ,4·x3 }. Determine the number of 4-permutations of S so that each of the 3 types of objects occurs even times. ▪ Solution: Let p4 be the number 4-permutations, g(x)=(1+x2 /2!)(1+x2 /2!)(1+x2 /2!+x4 /4!)
Example: Let s=loo.a1,oo a2, oo a3, Determine the number of r-permutations of s so that az occurs even times and a, occurs at least one time Solution: Let pr be the number r-permutations of s so that a2 occurs even times and a occurs at least one time, g(x)=(1+x+x2/2!++x/r!+….)(x+x2/2!+,+xr/r!+.) (1+x2/2!+x44!+.…,)=eY(ex-1)(e+ex)/2 =(e3x-e2x+e-1)2 22(31-2+4)n
▪ Example: Let S={·a1 ,·a2 , ·a3 }，Determine the number of r-permutations of S so that a3 occurs even times and a2 occurs at least one time. ▪ Solution: Let pr be the number r-permutations of S so that a3 occurs even times and a2 occurs at least one time, ▪ g(x)=(1+x+x2 /2!+…+xr /r!+…)(x+x2 /2!+…+xr /r! +…) (1+x2 /2!+x4 /4!+…)=ex (ex -1)(ex+e-x )/2 ▪ =(e3x -e 2x+ex -1)/2 = = − + 1 ! (3 2 1) 2 1 n n n n n x
4.7 Recurrence relations P13, P112(Sixth)P13, P100(Fifth Definition: A recurrence relation for the sequencefan is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely, 0, aj,..., an-1, for all integers n with neno, where no is a nonnegative integer A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation Initial condition: the information about the beginning of the sequence
4.7 Recurrence Relations ▪ P13, P112(Sixth) P13, P100 (Fifth) ▪ Definition: A recurrence relation for the sequence{an } is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely, a0 , a1 , …, an-1 , for all integers n with nn0 , where n0 is a nonnegative integer. ▪ A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation. ▪ Initial condition: the information about the beginning of the sequence
Example(fibonacci sequence): 13世纪初意大利数学家 fibonacci研究过著名的兔 子繁殖数目问题 A young pair rabbits (one of each sex) is placed in enclosure. A pair rabbits dose not breed until they are 2 months old, each pair of rabbits produces another pair each month. Find a recurrence relation for the number of pairs of rabbits in the enclosure after n months, assuming that no rabbits ever die Solution: Let fn be the number of pairs of rabbits after n months ()Born during month n (2)Present in month n-1 Fn=Fn+Fn-, FI=F2=1
▪ Example(Fibonacci sequence): ▪ 13 世纪初意大利数学家 Fibonacci 研究过著名的兔 子繁殖数目问题 ▪ A young pair rabbits (one of each sex) is placed in enclosure. A pair rabbits dose not breed until they are 2 months old, each pair of rabbits produces another pair each month. Find a recurrence relation for the number of pairs of rabbits in the enclosure after n months, assuming that no rabbits ever die. ▪ Solution: Let Fn be the number of pairs of rabbits after n months, ▪ (1)Born during month n ▪ (2)Present in month n-1 ▪ Fn=Fn-2+Fn-1，F1=F2=1
Example(the Tower of Hanoi): There are three pegs and n circular disks of increasing size on one peg, with the largest disk on the bottom. These disks are to be transferred, one at a time, onto another of the pegs, with the provision that at no time is one allowed to place a larger disk on top of a smaller one. The problem is to determine the number of moves necessary for the transfer. Solution: Let h(n) denote the number of moves needed to solve the Tower of Hanoi problem with n disks. h(1)=1 ()We must first transfer the top n-1 disks to a peg (Then we transfer the largest disk to the vacant peg ()Lastly, we transfer the n-1 disks to the peg which contains the largest disk h(n)=2h(n-1)+1,h(1)=1
▪ Example (The Tower of Hanoi): There are three pegs and n circular disks of increasing size on one peg, with the largest disk on the bottom. These disks are to be transferred, one at a time, onto another of the pegs, with the provision that at no time is one allowed to place a larger disk on top of a smaller one. The problem is to determine the number of moves necessary for the transfer. ▪ Solution: Let h(n) denote the number of moves needed to solve the Tower of Hanoi problem with n disks. h(1)=1 ▪ (1)We must first transfer the top n-1 disks to a peg ▪ (2)Then we transfer the largest disk to the vacant peg ▪ (3)Lastly, we transfer the n-1 disks to the peg which contains the largest disk. ▪ h(n)=2h(n-1)+1, h(1)=1
