CombinatoricsInstructor: Jie Ma, Scribed by Jun Gao, Jialin He and Tianchi Yang2020Fall,USTCContents2Enumeration1.21.1Binomial Coefficients31.2Counting Mappings .1.34The Binomial Theorem61.4Estimating Binomial Coefficients1.58InclusionandExclusion1.611GeneratingFunctions1.714IntegerPartitions1.815The Catalan Number1.916Random Walks181.10 Exponential Generating Functions212Basic of Graphs223Sperner's Lemma243.1 Double Counting253.2Sperner's Theorem273.3Littlewood-OffordProblem274Turan Type Problem5Trees29305.1TheFirst Proof of Cayley's Formula5.231TheSecondProofofCayley'sFormula5.333The Third Proof of Cayley'sFormula356IntersectingFamily6.1The Second Proof of Erdos-Ko-Rado Theorem37397Partially Ordered Sets (Poset)397.1 Poset.7.2The Order From Disorder41427.3ThePigeonholePrinciple437.4SecondProofofErdos-SzekeresTheorem438Ramsey's Theorem1
Combinatorics Instructor: Jie Ma, Scribed by Jun Gao, Jialin He and Tianchi Yang 2020 Fall, USTC Contents 1 Enumeration 2 1.1 Binomial Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Counting Mappings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 The Binomial Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Estimating Binomial Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5 Inclusion and Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.6 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.7 Integer Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.8 The Catalan Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.9 Random Walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.10 Exponential Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2 Basic of Graphs 21 3 Sperner’s Lemma 22 3.1 Double Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2 Sperner’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.3 Littlewood-Offord Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4 Tur´an Type Problem 27 5 Trees 29 5.1 The First Proof of Cayley’s Formula . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2 The Second Proof of Cayley’s Formula . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.3 The Third Proof of Cayley’s Formula . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6 Intersecting Family 35 6.1 The Second Proof of Erd˝os-Ko-Rado Theorem . . . . . . . . . . . . . . . . . . . . . 37 7 Partially Ordered Sets (Poset) 39 7.1 Poset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 7.2 The Order From Disorder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 7.3 The Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 7.4 Second Proof of Erd˝os-Szekeres Theorem . . . . . . . . . . . . . . . . . . . . . . . . 43 8 Ramsey’s Theorem 43 1
489TheProbabilisticMethod509.1 The Linearity of Expectation9.2 The Deleting Method539.3Markovs Inequality545610 The Algebraic Method5610.1Odd/EvenTown10.2 Even/Odd Town575810.3Fisher'sInequality5910.41-DistanceProblem6410.5 Bollobas'Theorem6710.6 Covering by Complete Bipartite Subgraphs6811FiniteProjectivePlane (FPP)1EnumerationFirst we give some standard notation that will be used throughout this course. Let n be a positiveinteger. We will use[n] to denote the set (1,2,...,n]. Given a set X, [X| denotes the numberof elements contained in X. Sometimes we also use “#" to express the word “number". Thefactorial of n is the productn!=n-(n-1).2.1,which can be extended to all non-negative integers by letting O! = 1.1.1 Binomial CoefficientsLet X be a set of size n. Define 2X = [A : A C X) to be the family of all subsets of X. So[2X| = 2/XI = 2n. Let () = [A : A C X, [A| = k).Fact 1.1. For integers n >0 and 0≤k≤n, we havel(x)] = () = (n-k).Proof. If k = 0, then it is clear that I()/ = I(0)/ = 1 = (). Now we consider k > 0. Letn!(n) :=n(n - 1).-- (n - k +1) =(n - k)First we will show that number of ordered k-tuples (ri, 2,.., rk) with distinct a E X is (n)k.There are n choices for the first element i.When i,..i is chosen, there are exactly n -ichoices for the element i+1So the number of ordered k-tuples (i,2,.., ) with distinct; E X is (n)k. Since any subset A E (x) correspond to k! ordered k-tuples, it follows thatI(2)= = (y, This fnishes the pof.Next we discuss more properties of binomial coefficients. For a positive integer n strictly lessthan k, we let (r) = 0.Fact 1.2. (1). (n) = (nnk) for 0 ≤ k ≤ n.(2). 2n = Z0≤k≤n (),(3). () = (“=1)+ ("=1).2
9 The Probabilistic Method 48 9.1 The Linearity of Expectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 9.2 The Deleting Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 9.3 Markov’s Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 10 The Algebraic Method 56 10.1 Odd/Even Town . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 10.2 Even/Odd Town . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 10.3 Fisher’s Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 10.4 1-Distance Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 10.5 Bolloba´s’ Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 10.6 Covering by Complete Bipartite Subgraphs . . . . . . . . . . . . . . . . . . . . . . 67 11 Finite Projective Plane (FPP) 68 1 Enumeration First we give some standard notation that will be used throughout this course. Let n be a positive integer. We will use [n] to denote the set {1, 2, ., n}. Given a set X, |X| denotes the number of elements contained in X. Sometimes we also use “#” to express the word “number”. The factorial of n is the product n! = n · (n − 1)· · · 2 · 1, which can be extended to all non-negative integers by letting 0! = 1. 1.1 Binomial Coefficients Let X be a set of size n. Define 2X = {A : A ⊆ X} to be the family of all subsets of X. So |2 X| = 2|X| = 2n . Let X k = {A : A ⊆ X, |A| = k}. Fact 1.1. For integers n > 0 and 0 ≤ k ≤ n, we have | X k | = n k = n! k!(n−k)!. Proof. If k = 0, then it is clear that | X 0 | = |{∅}| = 1 = n 0 . Now we consider k > 0. Let (n)k := n(n − 1)· · ·(n − k + 1) = n! (n − k)!. First we will show that number of ordered k-tuples (x1, x2, ., xk) with distinct xi ∈ X is (n)k. There are n choices for the first element x1. When x1, .xi is chosen, there are exactly n − i choices for the element xi+1. So the number of ordered k-tuples (x1, x2, ., xk) with distinct xi ∈ X is (n)k. Since any subset A ∈ X k correspond to k! ordered k-tuples, it follows that | X k | = (n)k k! = n! k!(n−k)! . This finishes the proof. Next we discuss more properties of binomial coefficients. For a positive integer n strictly less than k, we let n k = 0. Fact 1.2. (1). n k = n n−k for 0 ≤ k ≤ n. (2). 2 n = P 0≤k≤n n k . (3). n k = n−1 k−1 + n−1 k . 2
Proof. (1) is trivial. Since 2lml = Uo<k<n(μl), we see 2n =Eo<k<n ("), proving (2). Finally,we consider (3). Note that the first term on the right hand side (r-1) is the number of k-setscontaining a fixed element, while the second term (n--l) is the number of k-sets avoiding thiselement. So their summation gives the total number of k-sets in [n], which is (r). This finishesthe proof.Pascal's triangle is a triangular array constructed by summing adjacent elements in preced-ing rows. By Fact 1.2 (3), in the following graph we have that the k-th element in the n row is(s=1).A234568828936D36X126268410 -101045120210252210120451Fact 1.3.The number of integer solutions (r1,.., &n) to the equation ri +..En =k with eachTiE [0,1] is (n)Fact 1.4. The number of integer solution (r1,...n) with each ri≥ 0, to the equation ri+..-n-his (n+k)-)Proof. Suppose we have k sweets (of the same sort), which we want to distribute to n children.In how many ways can we do this? Let i denote the number of sweets we give to the i-th child,this question is equivalent to that state above.We lay out the sweets in a single row of length r and let the first child pick them up from leftto right (can be O). After a while we stop him/her and let the second child pick up sweets, etc.The distribution is determined by the specifying the place of where to start a new child. Equaltoselectn-1elementsfromn+r-l elementsto bethechild, othersbethe sweets(thefirstchild always starts at the beginning) Sotheansweris (国Exercise 1.5.Prove that=E()(m)1.2CountingMappingsDefine XY to be the set of all functions f :Y-→X.Fact 1.6. [XxY = [X|Y].Proof. Let [Y] = r. We can view XY as the set of all strings ri2..., with elements r; E X,indexed by the r element of Y.SoxY=xjYl.3
Proof. (1) is trivial. Since 2[n] = ∪0≤k≤n [n] k , we see 2n = P 0≤k≤n n k , proving (2). Finally, we consider (3). Note that the first term on the right hand side n−1 k−1 is the number of k-sets containing a fixed element, while the second term n−1 k is the number of k-sets avoiding this element. So their summation gives the total number of k-sets in [n], which is n k . This finishes the proof. Pascal’s triangle is a triangular array constructed by summing adjacent elements in preceding rows. By Fact 1.2 (3), in the following graph we have that the k-th element in the n row is n k−1 . 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 5 1 5 10 10 5 1 6 1 6 15 20 15 6 1 7 1 7 21 35 35 21 7 1 8 1 8 28 56 70 56 28 8 1 9 1 9 36 84 126 126 84 36 9 1 10 1 10 45 120 210 252 210 120 45 10 1 Fact 1.3. The number of integer solutions (x1, ., xn) to the equation x1 + · · · xn = k with each xi ∈ {0, 1} is n k . Fact 1.4. The number of integer solution (x1, .xn) with each xi ≥ 0, to the equation x1+· · · xn = k is n+k−1 n−1 . Proof. Suppose we have k sweets (of the same sort), which we want to distribute to n children. In how many ways can we do this? Let xi denote the number of sweets we give to the i-th child, this question is equivalent to that state above. We lay out the sweets in a single row of length r and let the first child pick them up from left to right (can be 0). After a while we stop him/her and let the second child pick up sweets, etc. The distribution is determined by the specifying the place of where to start a new child. Equal to select n − 1 elements from n + r − 1 elements to be the child, others be the sweets (the first child always starts at the beginning). So the answer is n+k−1 n−1 . Exercise 1.5. Prove that Xm k=0 m k n + k m = Xm k=0 n k m k 2 k . 1.2 Counting Mappings Define XY to be the set of all functions f : Y → X. Fact 1.6. |XY | = |X| |Y | . Proof. Let |Y | = r. We can view XY as the set of all strings x1x2.xr with elements xi ∈ X, indexed by the r element of Y . So |XY | = |X| |Y | . 3
Fact 1.7. The number of injective functions f : [r] - [n] is (n)r.Proof. We can view the injective function f as a ordered k-tuples (ri, 2, ., rr) with distinctri e X, so the number of injective functions f : [r] -→ [n] is (n)r.图Definition 1.8 (The Stirling number of the second kind). Let S(r,n) be the number ofpartition of [r] into n unordered non-empty parts.Exercise 1.9.Provethat2r-2S(r, 2) = 322Fact 1.10. The number of surjective functions f : [r] → [n] is n!S(r,n)Proof. Since f is a surjective function if and only if for any i e [n], f-1(i) 0 if and only ifUie[njf-1(i) =[r], and S(r, n) is the number of partition of [r] into n unordered non-empty parts,1we have the number of surjective functions f : [r] →[n] is n!s(r, n).We say that any injective f : X - X is a permutation of X (also a bijection). We mayview apermutation in two ways: (1)it is a bijectivefrom X to X. (2)a reordering of XCycle notation describes the effect of repeatedly applying the permutation on the elements ofthe set. It expresses the permutation as a product of cycles; since distinct cycles are disjoint, thisis referred to as “decomposition into disjoint cycles".Definition 1.11. The Stirling number of the first kind s(r,n) is (-1)(r-n) times the number ofpermutations of [r] with eractly n cycles.The following fact is a direct consequence of Fact 1.7Fact 1.12. The number of permutation of [n] is n!.r. Then In](1] +k [n-Exercise 1.13. (1) Let S(r,n) = (give a Combinakrn.torial proof.)( ) (, ) (-1) e [二 ] - [ ]1.3The Binomial TheoremDefine [rk]f to be the coefficient of the term rk in the polynomial f(r).Fact 1.14. For j =1, 2,., n, let f;(r) = kel, rk where I, is a set of non-negative integers, andlet f(a) =I',=1 fi(r). Then, [rh]f equals the number of solutions (ii,i2,., in) to i+i2+...+in =k, where ije Ij.Fact 1.15. Let fi,.. fn be polynomials and f = fif2...fn. Then,Z[rh]f =[e5]i++in=k,i>4
Fact 1.7. The number of injective functions f : [r] → [n] is (n)r. Proof. We can view the injective function f as a ordered k-tuples (x1, x2, ., xr) with distinct xi ∈ X, so the number of injective functions f : [r] → [n] is (n)r. Definition 1.8 (The Stirling number of the second kind). Let S(r,n) be the number of partition of [r] into n unordered non-empty parts. Exercise 1.9. Prove that S(r, 2) = 2 r − 2 2 = 1 2 Xr−1 i=1 r i . Fact 1.10. The number of surjective functions f : [r] → [n] is n!S(r, n). Proof. Since f is a surjective function if and only if for any i ∈ [n], f −1 (i) 6= ∅ if and only if ∪i∈[n]f −1 (i) = [r], and S(r, n) is the number of partition of [r] into n unordered non-empty parts, we have the number of surjective functions f : [r] → [n] is n!S(r, n). We say that any injective f : X → X is a permutation of X (also a bijection). We may view a permutation in two ways: (1) it is a bijective from X to X. (2) a reordering of X. Cycle notation describes the effect of repeatedly applying the permutation on the elements of the set. It expresses the permutation as a product of cycles; since distinct cycles are disjoint, this is referred to as “decomposition into disjoint cycles”. Definition 1.11. The Stirling number of the first kind s(r, n) is (−1)(r−n) times the number of permutations of [r] with exactly n cycles. The following fact is a direct consequence of Fact 1.7. Fact 1.12. The number of permutation of [n] is n!. Exercise 1.13. (1) Let S(r, n) = r n . Then n k = n − 1 k − 1 + k n − 1 k . (give a Combinatorial proof.) (2) Let s(n, k) = (−1)n−k n k . Then n k = n − 1 k − 1 + (n − 1) n − 1 k 1.3 The Binomial Theorem Define [x k ]f to be the coefficient of the term x k in the polynomial f(x). Fact 1.14. For j = 1, 2, ., n, let fj (x) = P k∈Ij x k where Ij is a set of non-negative integers, and let f(x) = Qn j=1 fj (x). Then, [x k ]f equals the number of solutions (i1, i2, ., in) to i1+i2+.+in = k, where ij ∈ Ij . Fact 1.15. Let f1, ., fn be polynomials and f = f1f2.fn. Then, [x k ]f = X i1+···+in=k,ij≥0 Yn j=1 [x ij ]fj . 4
Theorem1.16(TheBinomial Theorem).For any real r and anypositive integer n, we have(1 +α)" =-Proof 1.Let f = (1+r)n.By Fact 1.14 we have[rh]f equals the number of solutions (ii,i2,.., in)to i +i2 +...+in =k whereijE [0,1], so [rk]f = (n),4Proof 2.By induction on n.When n =1, it is trivial.If the result holds for n -1, then(1+r)n =(1 + a)(1 + a)n-1 = (1 +a) En= (n-)ri = En-l("-I) + (=1))r +1 +rn. Since-(n-) + (n-1) = (n) and () = (n) = 1, we have (1 + r)n = Er=o (")rt.Fact 1.17. (2n) = Er=o (") = En=o (°)(n=)Proof 1. Since (1 +r)2n = (1 + r)n(1 + a)n, by Fact 1.15, we have (2n) = [rn](1 + r)2n =E"=0([r](1+)n)([enj(1 +2)") =E=0 ()() =r= ()?IIProof 2. (It is easy to find a combinatorial proof.)Exercise 1.18 (Vandermonde's Convolution Formula).(t")-2()(")Fact 1.19. (1).=2n-]leallodo(2).n2n-Proof. (1). We see that (1 + r)n = En=o (r). Taking r = 1 and a = -1, we have= 2n12=』allevenallodd(2). Let f(r) = (1 + a)n = Eh=o ak. Then f'(c) = n(1 + a)n-1 = Eh=o k(r)rk-1. Let = 1,thenwe haveEr=ok()=n2n-Definition 1.20.Let ki ≥0 be integers satisfying that ki +k2 +..+km=n.We definen!nk1,k2....,kmki!k2!...km!5
Theorem 1.16 (The Binomial Theorem). For any real x and any positive integer n, we have (1 + x) n = Xn i=0 n i x i . Proof 1. Let f = (1+x) n . By Fact 1.14 we have [x k ]f equals the number of solutions (i1, i2, ., in) to i1 + i2 + . + in = k where ij ∈ {0, 1}, so [x k ]f = n k . Proof 2. By induction on n. When n = 1, it is trivial. If the result holds for n − 1, then (1 + x) n = (1 + x)(1 + x) n−1 = (1 + x) Pn−1 i=0 n−1 i x i = Pn−1 i=1 ( n−1 i + n−1 i−1 )x i + 1 + x n . Since n−1 i + n−1 i−1 = n i and n 0 = n n = 1, we have (1 + x) n = Pn i=0 n i x i . Fact 1.17. 2n n = Pn i=0 n i 2 = Pn i=0 n i n n−i . Proof 1. Since (1 + x) 2n = (1 + x) n (1 + x) n , by Fact 1.15, we have 2n n = [x n ](1 + x) 2n = Pn i=0([x i ](1 + x) n )([x n−i ](1 + x) n ) = Pn i=0 n i n n−i = Pn i=0 n i 2 . Proof 2. (It is easy to find a combinatorial proof.) Exercise 1.18 (Vandermonde’s Convolution Formula). n + m k = X k j=0 n j m k − j . Fact 1.19. (1). X all even k n k = X all odd k n k = 2n−1 . (2). Xn k=0 k n k = n2 n−1 . Proof. (1). We see that (1 + x) n = Pn i=0 n i . Taking x = 1 and x = −1, we have X all even k n k = X all odd k n k = 2n−1 . (2). Let f(x) = (1 + x) n = Pn k=0 x k . Then f 0 (x) = n(1 + x) n−1 = Pn k=0 k n k x k−1 . Let x = 1, then we have Pn k=0 k n k = n2 n−1 . Definition 1.20. Let kj ≥ 0 be integers satisfying that k1 + k2 + · · · + km = n. We define n k1, k2, ., km := n! k1!k2!.km! . 5