(1.) S(n,k) is equal to the number of partitions of [n] into k non-ordered non-empty set.(2.) S(n,k)k! is equal to the number of surjective functions f : [n] → []Theorem1.41.We haveS(n,k) =-i)nk!i=0Proof. For i E [], letA, = [all functions f : [n] → []\[]ThenAinAn..nA=[all surjective f : [n] →[]].SokS(n,k)k!=the number ofsurjective f:[n] →[]=(-1)"sii=0whereSi = Z IAil=(k-i)nTe(l)Finally, we get-i)nS(n,k) :k!i=0I1.6Generating FunctionsDefinition 1.42. The (ordinary) generating function for an infinity sequence [ao,ai,.. isapowerseriesf(a) =Ean"n.n≥0Wehavetwowaystoviewthispowerseries.(i). When the power series En≥0o anrn converges (i.e. there exists a radius R > 0 of con-vergence), we view GF as a function of r and we can apply operations of calculus on it(including differentiation and integration).Forexample,weknowthatf(n)(0)ann!Recall the following sufficient condition on the radius of convergence that if anl≤ Kn forsome K > 0, then Zn≥o anan converges in the interval (-K, k).11
(1.) S(n, k) is equal to the number of partitions of [n] into k non-ordered non-empty set. (2.) S(n, k)k! is equal to the number of surjective functions f : [n] → [k]. Theorem 1.41. We have S(n, k) = 1 k! X k i=0 (−1)i k i (k − i) n . Proof. For i ∈ [k], let Ai = {all functions f : [n] → [k]\{i}}. Then A c 1 ∩ A c 2 ∩ · · · ∩ A c k = {all surjective f : [n] → [k]}. So S(n, k)k! = the number of surjective f : [n] → [k] = X k i=0 (−1)iSi , where Si = X I∈( [k] i ) |AI | = k i (k − i) n . Finally, we get S(n, k) = 1 k! X k i=0 (−1)i k i (k − i) n . 1.6 Generating Functions Definition 1.42. The (ordinary) generating function for an infinity sequence {a0, a1, · · · } is a power series f(x) = X n≥0 anx n . We have two ways to view this power series. (i). When the power series P n≥0 anx n converges (i.e. there exists a radius R > 0 of convergence), we view GF as a function of x and we can apply operations of calculus on it (including differentiation and integration). For example, we know that an = f (n) (0) n! . Recall the following sufficient condition on the radius of convergence that if |an| ≤ Kn for some K > 0, then P n≥0 anx n converges in the interval (− 1 K , 1 K ). 11
(ii). When we are not sure of the convergence, we view the generating function as a formalobject with additions and multiplications. Let a(a) = n>0 ane" and b(r) = En≥0 bnrn.Addition.a(r) +b(r) =(an +bn)rnn≥0Multiplication.Let Cn =n=oaibn-i.Thena(a)b(ar) =cnann≥0Example 1.43.We see -=n=o rn holds for all -1 < <1. By the point view of (i), itsfirstderivativeqivesO1nan-1:=(n+1)rn.(1-a)2n=0n=1Problem 1.44. Let ao = 1 and an = 2an-1 for n ≥1. Find an.Solution.Considerthegenerating function,f(a) =an2" =1 +anz" =1 + 2a an-12n-1 =1 + 2rf(a).n=0n=1n=1So f(r) = 1-2, which implies that f(α) = t=0 2"r" and an = 2n.IFrom this problem, we see one of the basic ideas for using generating function: in order to findthe general expression of an, we work on its generating function f(r); once we find the formulaof f(r), then we can expand f(r) into a power series and get an by choosing the coefficient ofthe right term.Fact 1.45. For j e [nl, let fi(r) :=Eiel, rt, where I, C Z. Let b, be the number of solutions toii +i2+...+in=k for ijEIj.ThenII fi(a) =bxak.k=0j=1Fact1.46.If f(α)=IIk=,fi(r)forpolynomialsfi,...fk,thenkZII (r]fa),[r"]f =i1+i2+...j=1where [r"]f is the coefficient of rn in f.Problem 1.47. Let An be the set of strings of length n with entries from the set [a,b,c] andwith no"aa"occuring (in the consecutive positions). Find |Anl for n ≥1.12
(ii). When we are not sure of the convergence, we view the generating function as a formal object with additions and multiplications. Let a(x) = P n≥0 anx n and b(x) = P n≥0 bnx n . Addition. a(x) + b(x) = X n≥0 (an + bn)x n . Multiplication. Let cn = Pn i=0 aibn−i . Then a(x)b(x) = X n≥0 cnx n . Example 1.43. We see 1 1−x = P∞ n=0 x n holds for all −1 < x < 1. By the point view of (i), its first derivative gives 1 (1 − x) 2 = X∞ n=1 nxn−1 = X∞ n=0 (n + 1)x n . Problem 1.44. Let a0 = 1 and an = 2an−1 for n ≥ 1. Find an. Solution. Consider the generating function, f(x) = X∞ n=0 anx n = 1 +X∞ n=1 anx n = 1 + 2x X∞ n=1 an−1x n−1 = 1 + 2xf(x). So f(x) = 1 1−2x , which implies that f(x) = P+∞ n=0 2 nx n and an = 2n . From this problem, we see one of the basic ideas for using generating function: in order to find the general expression of an, we work on its generating function f(x); once we find the formula of f(x), then we can expand f(x) into a power series and get an by choosing the coefficient of the right term. Fact 1.45. For j ∈ [n], let fj (x) := P i∈Ij x i , where Ij ⊂ Z. Let bk be the number of solutions to i1 + i2 + . + in = k for ij ∈ Ij . Then Yn j=1 fj (x) = X∞ k=0 bkx k . Fact 1.46. If f(x) = Qk i=1 fi(x) for polynomials f1, ., fk, then [x n ]f = X i1+i2+···+ik=n Y k j=1 [x ij ]fj , where [x n ]f is the coefficient of x n in f. Problem 1.47. Let An be the set of strings of length n with entries from the set {a, b, c} and with no “aa” occuring (in the consecutive positions). Find |An| for n ≥ 1. 12
Solution. Let an =[Anl. We first observe that ai = 3,a2 = 8. For n ≥ 3, we will find an byrecursion as following. If the first string is 'a', the second string has two choices, 'b' or c'. Thenthe last n - 2 strings have an-2 choices. If the first string is ‘b' or ‘c', the last n - 1 strings havean-1choices.They areall different.Totally,for n≥3,wehavean=2an-1+2an-2-Set ao = 1, then an = 2an-1 + 2an-2 holds for n ≥ 2. The generating function of [an] isf(r) =ana" = a0 + a1r +(2an-1 + 2an-2)rn = 1 + 3r + 2r(f(z) -1) + 2r2 f(r),n≥0n≥2which implies that1+#f(r) = 1- 2# - 242ByPartialFractionDecomposition,wecalculatethatf(r) = 1- V3111+V323V3-1-2r2V3V3+1+2which implies that1-V3+1+V311-22an(V3+1)23-1V3-2/3 3+1Note that an must be an integer but its expression is of a combination of irrational terms! Observethat→ 0 as n→ oo.Thus, when n is sufficiently large, this integer ar<1, so (V3+1V3+1is about the value of the second term ()".Equivalentlyan will be the nearestinteger to that.Definition 1.48. For any real r and an integer k ≥ 0, let) = r(r -1).(r- k+1)k!Theorem 1.49 (Newton's Binomial Theorem).For any real number r and r E(-1,1)(r)rk(1+r)"=-Proof. By Taylor series, it is obvious.Corollary 1.50. Let r = -n for some integer n ≥ 0. Then(-n)(-n - 1) (-n - k + 1) = (-1)* (n+k-k!Thereforen+k-1(1 + )-n = (-1)13
Solution. Let an = |An|. We first observe that a1 = 3, a2 = 8. For n ≥ 3, we will find an by recursion as following. If the first string is ‘a’, the second string has two choices, ‘b’ or ‘c’. Then the last n − 2 strings have an−2 choices. If the first string is ‘b’ or ‘c’, the last n − 1 strings have an−1 choices. They are all different. Totally, for n ≥ 3, we have an = 2an−1 + 2an−2. Set a0 = 1, then an = 2an−1 + 2an−2 holds for n ≥ 2. The generating function of {an} is f(x) = X n≥0 anx n = a0 + a1x + X n≥2 (2an−1 + 2an−2)x n = 1 + 3x + 2x(f(x) − 1) + 2x 2 f(x), which implies that f(x) = 1 + x 1 − 2x − 2x 2 . By Partial Fraction Decomposition, we calculate that f(x) = 1 − √ 3 2 √ 3 1 √ 3 + 1 + 2x + 1 + √ 3 2 √ 3 1 √ 3 − 1 − 2x , which implies that an = 1 − √ 3 2 √ 3 1 √ 3 + 1 −2 √ 3 + 1n + 1 + √ 3 2 √ 3 1 √ 3 − 1 2 √ 3 − 1 n . Note that an must be an integer but its expression is of a combination of irrational terms! Observe that √−2 3+1 < 1, so √−2 3+1n → 0 as n → ∞. Thus, when n is sufficiently large, this integer an is about the value of the second term 1+√ 3 2 √ 3 √ 1 3−1 √ 2 3−1 n . Equivalently an will be the nearest integer to that. Definition 1.48. For any real r and an integer k ≥ 0, let r k = r(r − 1).(r − k + 1) k! . Theorem 1.49 (Newton’s Binomial Theorem). For any real number r and x ∈ (−1, 1), (1 + x) r = X∞ k=0 r k x k . Proof. By Taylor series, it is obvious. Corollary 1.50. Let r = −n for some integer n ≥ 0. Then −n k = (−n)(−n − 1)· · ·(−n − k + 1) k! = (−1)k n + k − 1 k . Therefore (1 + x) −n = X∞ k=0 (−1)k n + k − 1 k x k . 13
Problem 1.51.Let an be the number of ways to pay n Yuan using 1-Yuan bills, 2-Yuan billsand 5-Yuan bills. What is the generating function of this sequence [an]?Solution. Observe that an is the number of integer solutions (ii,i2, z3) to ii + i2 + i3 = n, wherei1 e l1 - (0, 1,2,.., i2 e I2 := (0, 2, 4,..] and ig e I3 := [0, 5, 10,..]. et fi(a) := Emel, mfor j =1,2,3. By Fact 1.45, we have+80111Zanzn = fi(a)f2(a)f3(a) :1-221-25n=0I1.7IntegerPartitionsHow many ways are there to write a natural number n as a sum of several natural numbers? Thetotal number of ordered partitions of n is Zi<kn (r=1) = 2n-1. Here "ordered partition" meansthat wewill view1+1+2,1+2+1 as two different partitions of 4.We then consider the unordered partitions.For instance, we will view1+2+3 and 3+2+1of6asthesame one.Let pn be the number of unordered partitions of n. So p1 = 1, p2 = 2, p3 = 3 and p4 = 5. Wehave the following theorem.Theorem 1.52. The generating function P(r) of (pn)n≥0 is an infinite product of polynomialsP(r) =k=Proof. Let n, be the number of the j's in such a partition of n. Then it holds thatjnj=n.j≥1Ifwe use i,to express the contribution of the addends equal to j in apartition ofn (i.e.,i,= j·ng)thenij=n,where ij E[0,j,2j,3j,..]izNote that in the above summation, j can run from 1 to infinity, or run from 1 to n. So by thefact we discussed earlier,Pnisthe coefficient of rn in theproductP(α)=(1+r+r2+...)(1+22+a4+..)...(1+rn+r2n+...)...=T4.This finishes the proof of this theorem.14
Problem 1.51. Let an be the number of ways to pay n Yuan using 1-Yuan bills, 2-Yuan bills and 5-Yuan bills. What is the generating function of this sequence {an}? Solution. Observe that an is the number of integer solutions (i1, i2, i3) to i1 + i2 + i3 = n, where i1 ∈ I1 := {0, 1, 2, .}, i2 ∈ I2 := {0, 2, 4, .} and i3 ∈ I3 := {0, 5, 10, .}. Let fj (x) := P m∈Ij x m for j = 1, 2, 3. By Fact 1.45, we have X +∞ n=0 anx n = f1(x)f2(x)f3(x) = 1 1 − x · 1 1 − x 2 · 1 1 − x 5 . 1.7 Integer Partitions How many ways are there to write a natural number n as a sum of several natural numbers? The total number of ordered partitions of n is P 1≤k≤n n−1 k−1 = 2n−1 . Here “ordered partition” means that we will view 1 + 1 + 2, 1 + 2 + 1 as two different partitions of 4. We then consider the unordered partitions. For instance, we will view 1 + 2 + 3 and 3 + 2 + 1 of 6 as the same one. Let pn be the number of unordered partitions of n. So p1 = 1, p2 = 2, p3 = 3 and p4 = 5. We have the following theorem. Theorem 1.52. The generating function P(x) of {pn}n≥0 is an infinite product of polynomials P(x) = + Y∞ k=1 1 1 − x k . Proof. Let nj be the number of the j’s in such a partition of n. Then it holds that X j≥1 j · nj = n. If we use ij to express the contribution of the addends equal to j in a partition of n (i.e., ij = j·nj ), then X j≥1 ij = n, where ij ∈ {0, j, 2j, 3j, .}. Note that in the above summation, j can run from 1 to infinity, or run from 1 to n. So by the fact we discussed earlier, pn is the coefficient of x n in the product P(x) = (1 + x + x 2 + · · ·)(1 + x 2 + x 4 + · · ·)· · ·(1 + x n + x 2n + · · ·)· · · = + Y∞ k=1 1 1 − x k . This finishes the proof of this theorem. 14
1.8TheCatalan NumberFirst let us recall the definition of () for real numbers r and positive integers k, and the Newton'sbinomial Theorem.We obtained that_ (-1)-12 (2k -2)!4kk!(k-1)!Let n-gon be a polygon with n corners, labeled as corner l, corner 2.., corner n.Definition 1.53. A triangulation of the n-gon is a way to add lines between corners to maketriangles such that these lines do not cross inside of the polygon.Then we have the following theorem.Theorem 1.54. The total number of triangulations of the (k +2)-gon is (2k), which is alsocalled the kth Catalan number.Proof. Let bn-1 be the number of triangulations of the n-gon, for n ≥ 3. It is not hard to seethat b2= 1,b3 = 2,by = 5. We want to find a general formula of bn.Consider the triangle T in a triangulation of n-gon which contains corners 1 and 2. Thetriangle T should contain a third corner, say i, where 3≤i≤ n.We have the following two cases.Case 1. If i = 3 or n, the triangle T divides the n-gon into the triangle T itself plus an(n -1)-gon, which results in bn-2 triangulations of n-gon.Case 2. For 4 ≤i ≤ n -1, the triangle T divides the n-gon into three regions: an (n-i+2)-gon, triangle T and an (i - 1)-gon, therefore it results in bi-2 x bn-i+1 many triangulations ofn-gonTherefore, combining Cases 1 and 2, we get thatn-1n-3bn-1 = bn-2 +bi=-2bn-i+1 + bn=2 = bn-2 +bjbn-j-1 + bn-2.i=4j=2Byletting bo =0 and bi =1, we getK-bn-1 =bjbn-1-jbk=bjbk-for k ≥ 2.for n≥3orj=0j=0rk.ThereforeLet f(r) =Zk≥o bkak. Note that f"(r) = Ek≥0 (j=0 bjbk-jf(a)=a+bkak=+bjbk-bjbk->>r+f(r)r+k≥2k≥2(j=0k≥0(j=0Solving F(a) - f(n) + = 0, we get that f() = I+ or I, But notice that f(0) = 0,soit has to bethe case that() = 1-VI-4h215
1.8 The Catalan Number First let us recall the definition of r k for real numbers r and positive integers k, and the Newton’s binomial Theorem. We obtained that 1 2 k = (−1)k−12 4 k · (2k − 2)! k!(k − 1)!. Let n-gon be a polygon with n corners, labeled as corner 1, corner 2,., corner n. Definition 1.53. A triangulation of the n-gon is a way to add lines between corners to make triangles such that these lines do not cross inside of the polygon. Then we have the following theorem. Theorem 1.54. The total number of triangulations of the (k + 2)-gon is 1 k+1 2k k , which is also called the k th Catalan number. Proof. Let bn−1 be the number of triangulations of the n-gon, for n ≥ 3. It is not hard to see that b2 = 1, b3 = 2, b4 = 5. We want to find a general formula of bn. Consider the triangle T in a triangulation of n-gon which contains corners 1 and 2. The triangle T should contain a third corner, say i, where 3 ≤ i ≤ n. We have the following two cases. Case 1. If i = 3 or n, the triangle T divides the n-gon into the triangle T itself plus an (n − 1)-gon, which results in bn−2 triangulations of n-gon. Case 2. For 4 ≤ i ≤ n−1, the triangle T divides the n-gon into three regions: an (n−i+ 2)- gon, triangle T and an (i − 1)-gon, therefore it results in bi−2 × bn−i+1 many triangulations of n-gon. Therefore, combining Cases 1 and 2, we get that bn−1 = bn−2 + nX−1 i=4 bi−2bn−i+1 + bn−2 = bn−2 + nX−3 j=2 bj bn−j−1 + bn−2. By letting b0 = 0 and b1 = 1, we get bn−1 = nX−1 j=0 bj bn−1−j for n ≥ 3 or bk = X k j=0 bj bk−j for k ≥ 2. Let f(x) = P k≥0 bkx k . Note that f 2 (x) = P k≥0 Pk j=0 bj bk−j x k . Therefore f(x) = x + X k≥2 bkx k = x + X k≥2 X k j=0 bj bk−j x k = x + X k≥0 X k j=0 bj bk−j x k = x + f 2 (x). Solving f 2 (x) − f(x) + x = 0, we get that f(x) = 1+√ 1−4x 2 or 1− √ 1−4x 2 . But notice that f(0) = 0, so it has to be the case that f(x) = 1 − √ 1 − 4x 2 . 15