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