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 ajaja3a3a3a44.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