4.6 Generating functions 4.6.1 Generating functions the number n of r-combinations of s equals nks), then Let s=(n, la,n2°a2y…,nk°ak},andn=n1+n2+ (1)0 when r>n (2)1 when r=n (3)N=C(k+r-l, r)when ni 2r for each i=1, 2,...,n (4)If r<n, and there is, in general, no simple formula for the number of r-combinations of s A solution can be obtained by the inclusion-exclusion principle and technique of generating functions 6-combination ajaja3a3a3a4
4.6 Generating functions ▪ 4.6.1 Generating functions ▪ Let S={n1 •a1 ,n2 •a2 ,…,nk •ak }, and n=n1+n2+…+nk=|S|，then the number N of r-combinations of S equals ▪ (1)0 when r>n ▪ (2)1 when r=n ▪ (3) N=C(k+r-1,r) when ni r for each i=1,2,…,n. ▪ (4)If r<n, and there is, in general, no simple formula for the number of r-combinations of S. ▪ A solution can be obtained by the inclusion-exclusion principle and technique of generating functions. ▪ 6-combination a1a1a3a3a3a4
Xx2,X=xi+i2+…+i=yr r-combination ofs Definition 1: The generating function for the sequence a0s2a1y…,any… of real numbers is the infinite series f(X)=a0+a1x+a2x2+…+anx"+…, an ∑ax=∑ b,x' if only if a;=b; for all i=0,1,…n, i=0 i=0
▪ x i1x i2…xik= xi1+i2+…+ik=xr ▪ r-combination of S ▪ Definition 1: The generating function for the sequence a0 ,a1 ,…,an ,… of real numbers is the infinite series f(x)=a0+a1x+a2x 2+…+anx n+…, and = = = 0 i 0 i i i i i a x b x if only if ai=bi for all i=0,1, …n, …
We can define generating function for finite sequences of real numbers by extending a finite sequences a0 1r,gan into an infinite sequence by setting an+=0, an+2=0, and so on. The generating function f(x) of this infinite sequence a is a polynomial of degree n since no terms of the form a; x, with i>n occur, that is f(x=ao+,+ x2+.tanx
▪ We can define generating function for finite sequences of real numbers by extending a finite sequences a0 ,a1 ,…,an into an infinite sequence by setting an+1=0, an+2=0, and so on. ▪ The generating function f(x) of this infinite sequence {an } is a polynomial of degree n since no terms of the form ajx j , with j>n occur, that is f(x)=a0+a1x+a2x 2+…+anx n