Set co =0,c1 =1 -2-2 → ce)=点Th C(p-22aat C()-z=C( Then C(2)=-4.Since C(0)=0,C(2)=-4.By Newton's Binomial Theorem c-2月-r =户1+e 22 c-(会-）i-点(）Caaln mer)
Set c0 = 0, c1 = 1 =⇒ X∞ n=2 cnz n = X∞ n=2 Xn−1 k=1 ckcn−kz n = X∞ n=2 Xn k=0 ckcn−kz n . Let C(z) = P∞ n≥0 cnz n . Then C(z) 2 = P∞ n=0 Pn k=0 ckcn−kz n . C(z) − z = C(z) 2 . Then C(z) = 1 2 ± 1 2 √ 1 − 4z. Since C(0) = 0, C(z) = 1 2 − 1 2 √ 1 − 4z. By Newton’s Binomial Theorem C(z) = 1 2 − 1 2 X∞ n≥0 1 2 n (−4z) n = X∞ n≥1 1 2 (−1)n+14 n z n 2 = X∞ n≥1 1 n 2n − 2 n − 1 z n . So cn = 1 n 2n − 2 n − 1 , cn+1 = 1 n+1 2n n (Catalan number). 4
Combinatorics,2017 Fall,USTC Week 3 Note 1 2017.9.26,Tuesday 1 Generating Function(GF)and Selections Letf(e)=∑m2on)rn,j=1,2,…,k fa=i国…fi国=（∑i)…r n=0 \ Denote f()=coefficient of r"in f(r). Facts: ()Letf(m)=∑e,马s220,ie网， f)=if…f=∑n2,Them bn= ie.bn=#integer solutions to1+2+…+k=n,y∈ (2)Lt1)=z20,then f(d)=1+x+x2+…= So f(r)=is the generating function of=inon-negative integer s0l1ti0nst0工1+r2++rk=n. (3)Let I=Zso,i.e.then f()=.(Exercise mmbers of thre kins ofll ind the 1
Combinatorics, 2017 Fall, USTC Week 3 Note 1 2017.9.26,Tuesday 1 Generating Function(GF) and Selections Let fj (x) = P n≥0 fj (n)x n, j = 1, 2, · · · , k f(x) = f1(x)f2(x)· · · fk(x) = X∞ n=0 X n1+···+nk=n f1(n1)f2(n2)· · · fk(nk) ! x n . Denote [x n]f(x) = coefficient of x n in f(x). Facts: (1) Let fj (x) = P i∈Ij x i , Ij ⊆ Z≥0, j ∈ [k], f(x) = f1f2 · · · fk = P n≥0 bnx n. Then bn = X n1+···nk=n,nj∈Ij 1, i.e. bn = ] integer solutions to x1 + x2 + · · · + xk = n, xj ∈ Ij . (2) Let Ij = Z≥0, then fj (x) = 1 + x + x 2 + · · · = 1 1−x . So f(x) = 1 (1−x) k is the generating function of bn = ]non-negative integer solutions to x1 + x2 + · · · + xk = n. (3) Let Ij = Z>0, i.e. xj > 0, then f(x) = x k (1−x) k . (Exercise) Problem 1: How many ways to pay 20 yuan using five 1-yuan bills, four 2- yuan bills, three 5-yuan bills ? Let an be ]ways to pay n-yuan given unlimited numbers of three kinds of bills, find the GF of {an}. Solution. (1) f1(x) = 1+x+x 2 +x 3 +x 4 +x 5 , f2(x) = 1+x 2 +x 4 +x 6 +x 8 , f3(x) = 1 + x 5 + x 10 + x 15, f(x) = f1f2f3, then [x 20]f(x) is the answer. 1
(2={0,1,2…2={0,2,4…},=0,5,10,15,…} on∑ner.Thes f(e)=hh=古☆☆isthe generating Problem 2:Let p be the mumber of partitions of n.Find the GF of (p Solution.Let nj be of the i's in such a partition of n,then P=2国=n21 E.g.Compute pa 2++…+++…0+++） 4=4,3+1,2+2,2+1+1,1+1+1+1. 2 Exponential GF(EGF)and Arrangements 会b界a台ss信a+台+a=noma T= erlealea! What's the GF of Tn? Def:The EGF of the sequence (an}is f() Ect1:a)=∑m2o0r”,je网. =…+ 2
(2) I1 = {0, 1, 2, · · · }, I2 = {0, 2, 4, · · · }, I3 = {0, 5, 10, 15, · · · }, fj (x) = P n∈Ij x n. Then f(x) = f1f2f3 = 1 1−x · 1 1−x2 · 1 1−x5 is the generating function. Integer Partition: Write n as a sum of positive integers without regard to the ordering of the numbers. Problem 2: Let pn be the number of partitions of n. Find the GF of {pn}. Solution. Let nj be ] of the j’s in such a partition of n, then X j≥1 j · nj = n. Let ij = j · nj , which is the contribution of the addends j in a partition of n, then ij ∈ {0, j, 2j, 3j, · · · }. Let fj (x) = 1 + x j + x 2j + x 3j + · · · = 1 1−xj , then the GF of {pn} is P(x) = Πj≥1fj (x) = Πj≥1 1 1 − x j . E.g. Compute p4 (1 +x+x 2 +x 3 +· · ·)(1 +x 2 +x 4 +· · ·)(1 +x 3 +x 6 +· · ·)(1 +x 4 +x 8 +· · ·) = 1 + x + 2x 2 + 3x 3 + 5x 4 + · · · 4 = 4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1. 2 Exponential GF(EGF) and Arrangements E.g. Tn = ] strings of length n over {a, b, c} s.t. both the numbers of a and b are even. Find Tn. A selection of e1 a’s, e2 b’s and e3 c’s with e1 + e2 + e3 = n contributes n! e1!e2!e3! to Tn. Therefore Tn = X e1 + e2 + e3 = n e1, e2 ∈ 2Z≥0 , e3 ∈ Z≥0 n! e1!e2!e3! What’s the GF of Tn ? Def: The EGF of the sequence {an} is f(x) = P n≥0 an n! x n. Fact 1: fj (x) = P n≥0 fj (n) n! x n, j ∈ [k]. f(x) = f1 · · · fk = X n≥0 X n1 + · · · + nk = n n1, · · · nk ≥ 0 Πk j=1fj (nj ) n1!n2! · · · nk! x n , 2
i.e.f()is the EGF of 器 Gn= Fact 2:f()=il Ij Zz0.j Let 工高 Then I=1f;is the EGF of Problem3:Find EGF of (T} Solution.Let n-2爱 Therefore, =M-g的)若男r 4 4 iG低EOPn be dnod Problem 4:Let be the number of ways to send n students to 4 classes R,R2,R,R,s.t.each class has at least one student an=bn 3
i.e. f(x) is the EGF of an = X n1 + · · · + nk = n n1, · · · nk ≥ 0 n!Πk j=1fj (nj ) n1!n2! · · · nk! . Fact 2: fj (x) = P i∈Ij x i i! , Ij ⊆ Z≥0, j ∈ [k]. Let bn = P i1 + · · · + ik = n n! i1!···ik! = ]strings of length n over {a1, · · · , ak} s.t. the number of occurrence of aj is in Ij . Then Πk j=1fj is the EGF of {bn}n≥0. Problem 3: Find EGF of {Tn}. Solution. Let T(x) = X∞ n=0 Tn n! x n , f1(x) = f2(x) = X i∈2Z≥0 x i i! = X∞ n=0 x 2n (2n)! = e x + e −x 2 , f3(x) = X i∈Z≥0 x i i! = X∞ n=0 x n n! = e x . Therefore, T(x) = f1f2f3 = X n≥0 3 n + 2 + (−1)n 4 x n n! ⇒ Tn = 3 n + 2 + (−1)n 4 . Note: GF can find the number of selections, while EGF can be used to find the number of arrangements. Problem 4: Let an be the number of ways to send n students to 4 classes R1, R2, R3, R4, s.t. each class has at least one student. Solution. Let bn be the number of vectors of length n over [4] s.t. each i ∈ [4] occurs at least once. Then an = bn = X i1 + i2 + i3 + n4 = n i1, · · · n4 ≥ 1 n! i1!i2!i3!i4! . 3
Letf(r)=∑n21=e-l,ie.Then the EGF of{an}is =66=-43+62-后+1 →an=4"-4,3"+6.2-4,n≥1，anda0=0. Exercise:Use EGF to find=vectors of length n over [ 4
Let fi(x) = P n≥1 x n n! = e x − 1, i ∈ [4]. Then the EGF of {an} is f = f1f2f3f4 = X n≥0 (4n − 4 · 3 n + 6 · 2 n − 4)x n n! + 1. ⇒ an = 4n − 4 · 3 n + 6 · 2 n − 4, n ≥ 1, and a0 = 0. Exercise: Use EGF to find an = ] vectors of length n over [k]. 4