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 0<r≤1. Then for any 0<r ≤1, it gives that(n)<()+()()<(1 +r)n+...+ckATaking r = e (0, 1l, we have(1+r)nen)=ak-as desired.1.5InclusionandExclusionThislecture is devoted to Inclusion-Exclusion formula and its applications.Let be a ground set and let Ai, A2,.., An be subsets of 2. Write As = 2A;. Throughoutthis lecture, we use the following notation.Definition 1.34. Let A =S2.For any nonempty subset I [n], letAI=Ai.ielForany integerk≥O,letSk=Z IAil.Te(l)Now we introduce Inclusion-Exclusion formula (in three equivalent forms) and give two proofsasfollowing.Theorem 1.35(Inclusion-ExclusionFormula).Wehave(-1)k+1 Sk[Ar UA2 U...UAnl ->k=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