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
Thefollowing theorem is a generalization of the binomial theorem.Theorem 1.21 (Multinomial Theorem). For any reals ri,., Tm and any positive integern≥ 1, we haveAZ(ri+2++*+m)n(ki,k2,.,k1+k2++km=n,k,≥0Proof. Omit.-Exercise1.22.SupposeEm,ki=nwithk,≥1forall iEm.Thenn-1n-1n+...+ki,k2,....km(k1 - 1. k..... kmki.k2....km.1.4EstimatingBinomial CoefficientsTheorem 1.23.For any integer n ≥1, we havee(")"≤n!≤en (")"(1.1)wheree=lim (1+)n istheEulernumberProof. We haven+1n+In(n!) =Indr=(rInrIni=(n+1)ln(n+1)-ni=1Then it follows that(n+1)n+1n!enReset n = n- 1, we havenn(n - 1)! ≤en-I n!≤neSimilarly we haveIn(n!) ≥In a de = (rlna-a)=nlnn-(n-1),which implies thatn≥岩=e(-as desired.Modifying the above proof, we can obtain the following improvement.6
The following theorem is a generalization of the binomial theorem. Theorem 1.21 (Multinomial Theorem). For any reals x1, ., xm and any positive integer n ≥ 1, we have (x1 + x2 + · · · + xm) n = X k1+k2+···+km=n, kj≥0 n k1, k2, ., km x k1 1 x k2 2 · · · x km m . Proof. Omit. Exercise 1.22. Suppose Pm i=1 ki = n with ki ≥ 1 for all i ∈ m. Then n k1, k2, ., km = n − 1 k1 − 1, k2, ., km + · · · + n − 1 k1, k2, ., km − 1 . 1.4 Estimating Binomial Coefficients Theorem 1.23. For any integer n ≥ 1, we have e n e n ≤ n! ≤ en n e n , (1.1) where e = limn→∞ (1 + 1 n ) n is the Euler number. Proof. We have ln(n!) = Xn i=1 ln i ≤ Z n+1 1 ln x dx = (x ln x − x) x=n+1 x=1 = (n + 1) ln(n + 1) − n. Then it follows that n! ≤ (n + 1)n+1 e n . Reset n = n − 1, we have (n − 1)! ≤ n n e n−1 ⇐⇒ n! ≤ ne n e n . Similarly we have ln(n!) ≥ Z n 1 ln x dx = (x ln x − x) n 1 = n ln n − (n − 1), which implies that n! ≥ n n e n−1 = e n e n , as desired. Modifying the above proof, we can obtain the following improvement. 6
Exercise 1.24. Prove thatn!≤eVn(f(n)Definition 1.25. Define f ~ g for functions f and g, if lim=10g(n)The following formula is well-known.Theorem 1.26 (Stirling's formula.).n! ~V2n(")n.It is easy to show the following two facts.Fact 1.27. Let n be a fia integer. We can view (n) as a function with k e [0,1,2,.,n]. It isincreasing when k ≤[], and decreasing when k > []. Therefore, (r) achievers its marimumat k = [] or [].Fact 1.28. ≤()≤ 2nExercise 1.29. For any even integer n > 0, we have2n2nnV2nn/2If we are allowed to use Stirling's formula, then we can get22nV元VnFact 1.30. (")=≤Exercise 1.31. 1+r ≤e holds for any real r.Theorem 1.32.For any integers1≤k≤n, we have()≤()≤()Proof. Since ≥ " for each 0 ≤i≤k - 1, we have-~(=((++) -() () ("一+)≥ ()k (k-1)...1For theupper bound, sincek!≥e()*>(), byFact 1.30 we have() ≤≤(F)-as desired.We can also prove the following strengtheningTheorem1.33.Foranyintegers1<k<n,)+ (+1
Exercise 1.24. Prove that n! ≤ e √ n n e n . Definition 1.25. Define f ∼ g for functions f and g, if limn→∞ f(n) g(n) = 1. The following formula is well-known. Theorem 1.26 (Stirling’s formula.). n! ∼ √ 2πn( n e ) n . It is easy to show the following two facts. Fact 1.27. Let n be a fix integer. We can view n k as a function with k ∈ {0, 1, 2, ., n}. It is increasing when k ≤ n 2 , and decreasing when k > n 2 . Therefore, n k achievers its maximum at k = n 2 or n 2 . Fact 1.28. 2 n n ≤ n b n 2 c ≤ 2 n Exercise 1.29. For any even integer n > 0, we have 2 n √ 2n ≤ n n/2 ≤ 2 n √ n . If we are allowed to use Stirling’s formula, then we can get n n 2 ∼ r 2 π 2 n √ n . Fact 1.30. n k = (n)k k! ≤ n k k! . Exercise 1.31. 1 + x ≤ e x holds for any real x. Theorem 1.32. For any integers 1 ≤ k ≤ n, we have ( n k ) k ≤ n k ≤ ( en k ) k . Proof. Since n−i k−i ≥ n k for each 0 ≤ i ≤ k − 1, we have n k = n · (n − 1)· · ·(n − k + 1) k · (k − 1)· · · 1 = n k · n − 1 k − 1 · · · n − k + 1 k ≥ n k k . For the upper bound, since k! ≥ e( k e ) k > ( k e ) k , by Fact 1.30 we have n k ≤ n k k! ≤ en k k , as desired. We can also prove the following strengthening. Theorem 1.33. For any integers 1 ≤ k ≤ n, n 0 + n 1 + · · · + n k ≤ en k k . 7
Proof.By thebinomial theorem,we havek≤(1+r)"for any 0k=1which is equivalent to to2\UA=IAInASn...nAI=-1)*Sk>k=0i.e.,2)UJA=AnASn...nAI=(-1)ArlIC[n]8
Proof. By the binomial theorem, we have n 0 + n 1 x + · · · + n k x k ≤ (1 + x) n for any 0 < x ≤ 1. Then for any 0 < x ≤ 1, it gives that n 0 + n 1 + · · · + n k ≤ n 0 x k + n 1 x k−1 + · · · + n k 1 ≤ (1 + x) n x k . Taking x = k n ∈ (0, 1], we have n 0 + n 1 + · · · + n k ≤ (1 + x) n x k ≤ e xn x k = en k k , as desired. 1.5 Inclusion and Exclusion This lecture is devoted to Inclusion-Exclusion formula and its applications. Let Ω be a ground set and let A1, A2, ., An be subsets of Ω. Write Ac i = Ω\Ai . Throughout this lecture, we use the following notation. Definition 1.34. Let A∅ = Ω. For any nonempty subset I ⊆ [n], let AI = \ i∈I Ai . For any integer k ≥ 0, let Sk = X I∈( [n] k ) |AI |. Now we introduce Inclusion-Exclusion formula (in three equivalent forms) and give two proofs as following. Theorem 1.35 (Inclusion-Exclusion Formula). We have |A1 ∪ A2 ∪ . ∪ An| = Xn k=1 (−1)k+1Sk, which is equivalent to to Ω [n i=1 Ai = |A c 1 ∩ A c 2 ∩ . ∩ A c n | = Xn k=0 (−1)kSk, i.e., Ω [n i=1 Ai = |A c 1 ∩ A c 2 ∩ . ∩ A c n | = X I⊆[n] (−1)|I| |AI |. 8
Proof (1).For any subset X 2, we define its characterization function 1x :2 →[0,1) byassigningJi,rex1x(r) =Lo,r$x.Then ren lx(a) = [X]. Let A = Ai U A2 U... U An. Our key observation is that(1A-1A)(1A- 1A2).-(1A-1A,)(r) = 0holds for any r E 2. Next we expand this product into a summation of 2n terms as following:(-1)(I1A)=0 1A() + (-1)|1Ar(a)=0IC[n]ielIC[n], I0holds for any e 2. Summing over all r 2, this gives that[A| + (1)]]/A| =0,IC[n], I+0which implies that[Ai U A2 U .. An| = |A| = Z(-1)]+|Ai| = (-1)+1Ssk=1Ifinishing the proof.Proof (2).It suffices to prove thatIAiuAau.UAn (a) =(-1)++1 lA;()k=1Te(l)holds for all 2. Denote by LHS (resp. RHS) the left (resp. right) side of the above equationAssume that is contained in exactly l subsets, say Ai, A2,-.,Ae. If l = 0, then clearlyLHS = 0 = RHS, so we are done. So we may assume that l ≥ 1. In this case, we have LHS = 1and+.(-1)++1RHS=l-Note that the above equation holds since i=o(-1)i() = (1 -1) = 0. This finishes the proof. Next,wewill demonstrate the power of Inclusion-Exclusionformula by using itto solve severalproblems.Definition 1.36. Let p(n) be the number of integers m e [n] which are relatively primel to n.'Here, "m is relatively prime to n" means that the greatest common divisor of m and n is 1.9
Proof (1). For any subset X ⊆ Ω, we define its characterization function ✶X : Ω → {0, 1} by assigning ✶X(x) = ( 1, x ∈ X 0, x /∈ X. Then P x∈Ω ✶X(x) = |X|. Let A = A1 ∪ A2 ∪ . ∪ An. Our key observation is that (✶A − ✶A1 )(✶A − ✶A2 )· · ·(✶A − ✶An )(x) ≡ 0 holds for any x ∈ Ω. Next we expand this product into a summation of 2n terms as following: X I⊆[n] (−1)|I| ( Y i∈I ✶Ai ) ≡ 0 ⇐⇒ ✶A(x) + X I⊆[n], I6=∅ (−1)|I|✶AI (x) ≡ 0 holds for any x ∈ Ω. Summing over all x ∈ Ω, this gives that |A| + X I⊆[n], I6=∅ (−1)|I| |AI | = 0, which implies that |A1 ∪ A2 ∪ . ∪ An| = |A| = X I⊆[n] I6=∅ (−1)|I|+1|AI | = Xn k=1 (−1)k+1Sk, finishing the proof. Proof (2). It suffices to prove that ✶A1∪A2∪.∪An (x) = Xn k=1 (−1)k+1 X I∈( [n] k ) ✶AI (x) holds for all x ∈ Ω. Denote by LHS (resp. RHS) the left (resp. right) side of the above equation. Assume that x is contained in exactly ` subsets, say A1, A2, · · · , A` . If ` = 0, then clearly LHS = 0 = RHS, so we are done. So we may assume that ` ≥ 1. In this case, we have LHS = 1 and RHS = ` − ` 2 + ` 3 + · · · + (−1)`+1 ` ` = 1. Note that the above equation holds since P` i=0(−1)i ` i = (1 − 1)` = 0. This finishes the proof. Next, we will demonstrate the power of Inclusion-Exclusion formula by using it to solve several problems. Definition 1.36. Let ϕ(n) be the number of integers m ∈ [n] which are relatively prime1 to n. 1Here, “m is relatively prime to n” means that the greatest common divisor of m and n is 1. 9
Theorem 1.37. If we erpress n =pa'pa?..-pat, where pi-..pt are distinct primes, then(n) = nI(1- 1)pi-1Proof. Let A, = [m E[n] : pi|m] for i e [1,2,...,t]. It impliesp(n) =(m E[n] :m± A, forall iE[]}|= [n]\(AiU A2U.UAt)]By Inclusion-Exclusion formula,(n) = (-1)/Ail,IC[]where Ai = NieiA, = [m E [n] : (Iliei Pi)|m] and thus [Ai| = n/ Iliei Pi. We can derive that1)(1-11)p(n) = (-1)I_ n)..1-=n(1-PtIlierPip1P2IC[]Ias desired.Definition 1.38. A permutation g : [n] →[n] is called a derangement of [n] if o(i) +i for allie[n].Theorem 1.39. Let Dn be the family of all derangement of [n]. Then[D, / = n!(-1)k!k=0Proof.LetA, = [all permutations a : [n] → [n] such that o(i) = i]ThenDn = AInASn.--nA andAl= (n-)!By Inclusion-Exclusion formula, we get"(-1))(n -k)!=(-1)=n![Dn| = Z (-1)I/Ar| =(-1)l-1k!b-0IC[n]k=0k=0Ias desired.Remark1.40.WehavethatIDn/ , n!asn→oIt is because = e-1 (by the Taylor series of e" = ),Next we recall the definition of S(n, k) and aim to give a precise formula for it. We know that10
Theorem 1.37. If we express n = p a1 1 p a2 2 · · · p at t , where p1 · · · pt are distinct primes, then ϕ(n) = n Y t i=1 (1 − 1 pi ). Proof. Let Ai = {m ∈ [n] : pi |m} for i ∈ {1, 2, · · · , t}. It implies ϕ(n) = {m ∈ [n] : m /∈ Ai for all i ∈ [t]} = [n]\(A1 ∪ A2 ∪ · · · ∪ At) . By Inclusion-Exclusion formula, ϕ(n) = X I⊆[t] (−1)|I| |AI |, where AI = ∩i∈IAi = {m ∈ [n] : (Q i∈I pi)|m} and thus |AI | = n/ Q i∈I pi . We can derive that ϕ(n) = X I⊆[t] (−1)|I| n Q i∈I pi = n(1 − 1 p1 )(1 − 1 p2 )· · ·(1 − 1 pt ), as desired. Definition 1.38. A permutation σ : [n] → [n] is called a derangement of [n] if σ(i) 6= i for all i ∈ [n]. Theorem 1.39. Let Dn be the family of all derangement of [n]. Then |Dn| = n! Xn k=0 (−1)k k! . Proof. Let Ai = {all permutations σ : [n] → [n] such that σ(i) = i}. Then Dn = A c 1 ∩ A c 2 ∩ · · · ∩ A c n and |AI | = (n − |I|)!. By Inclusion-Exclusion formula, we get |Dn| = X I⊆[n] (−1)|I| |AI | = Xn k=0 (−1)k n k (n − k)! = Xn k=0 (−1)k n! k! = n! Xn k=0 (−1)k k! , as desired. Remark 1.40. We have that |Dn| → n! e as n → ∞. It is because P+∞ k=0 (−1)k k! = e −1 (by the Taylor series of e x = P+∞ k=0 x k k! ). Next we recall the definition of S(n, k) and aim to give a precise formula for it. We know that 10