Ch.1: Introduction

From the lecture notes "Combinatorics, Graphs, Matroids" (University of Bonn, winter term 2025/26) 1.1. Fundamental Counting Rules 1.2. Elementary Counting Coefficients 1.3. Assignments 1.4. Generalized Counting Coefficients 1.5. Permutations 1.6. Further Combinatorial Techniques

109 flashcards · Mathematics · by lakesare

Part of University of Bonn › V3C2: Combinatorics, Graphs, Matroids · 6 courses

[Fundamental Counting Rules] What is an nnn -set?
A finite set with nnn elements, for some n∈Nn \in \mathbb{N}n∈N . Here N\mathbb{N}N includes 0, so the empty set is a 0-set.
[Fundamental Counting Rules] What are the three fundamental counting rules for finite sets?
Sum rule, product rule, bijection rule: ∣⋃i=1kUi∣=∑i=1k∣Ui∣\left|\bigcup_{i=1}^{k} U_i\right| = \sum_{i=1}^{k} |U_i|∣∣⋃i=1kUi∣∣=∑i=1k∣Ui∣ for pairwise disjoint U1,…,UkU_1, \dots, U_kU1,…,Uk ; ∣U1×⋯×Uk∣=∏i=1k∣Ui∣\ |U_1 \times \dots \times U_k| = \prod_{i=1}^{k} |U_i| ∣U1×⋯×Uk∣=∏i=1k∣Ui∣ ; \ a bijection between SSS and TTT gives ∣S∣=∣T∣|S| = |T|∣S∣=∣T∣ .
[Fundamental Counting Rules] AAA and BBB are nnn -sets. How many bijections from AAA to BBB are there?
n!\boldsymbol{n!}n! In particular an nnn -set has n!n!n! permutations (bijections to itself).
[Fundamental Counting Rules] How does the induction on nnn prove that there are n!n!n! bijections between two nnn -sets AAA and BBB ?
Fix x∈Ax \in Ax∈A and split the bijections by the image f(x)=if(x) = if(x)=i : for each of the nnn choices of i∈Bi \in Bi∈B there are (n−1)!(n-1)!(n−1)! of them. Those are the bijections A∖{x}→B∖{i}A \setminus \{x\} \to B \setminus \{i\}A∖{x}→B∖{i} (induction). The sum rule gives n⋅(n−1)!=n!n \cdot (n-1)! = n!n⋅(n−1)!=n! . Base case n=0n = 0n=0 : one bijection, 0!=10! = 10!=1 .
[Fundamental Counting Rules] How many mappings are there from a kkk -set AAA to an nnn -set BBB , and why?
nk\boldsymbol{n^k}nk : the mappings correspond bijectively to B×⋯×BB \times \dots \times BB×⋯×B ( kkk factors). With A={a1,…,ak}A = \{a_1, \dots, a_k\}A={a1,…,ak} , send fff to (f(a1),…,f(ak))(f(a_1), \dots, f(a_k))(f(a1),…,f(ak)) ; then the bijection rule and the product rule.
[Fundamental Counting Rules] What do the notations BAB^ABA and 2A2^A2A denote?
BAB^ABA : the set of all mappings from AAA to BBB . 2A\ 2^A 2A : the power set of AAA (the set of its subsets). They fit the counts: ∣BA∣=∣B∣∣A∣|B^A| = |B|^{|A|}∣BA∣=∣B∣∣A∣ and ∣2A∣=2∣A∣|2^A| = 2^{|A|}∣2A∣=2∣A∣ .
[Fundamental Counting Rules] How many subsets does an nnn -set AAA have, and what is the bijection behind it?
2n\boldsymbol{2^n}2n : send B⊆AB \subseteq AB⊆A to its indicator mapping fB:A→{0,1}f_B : A \to \{0, 1\}fB:A→{0,1} , with fB(x)=1f_B(x) = 1fB(x)=1 if and only if x∈Bx \in Bx∈B . So subsets of AAA correspond to mappings from an nnn -set to a 2-set, of which there are 2n2^n2n .
[Fundamental Counting Rules] What three kinds of answer can "counting" the elements of a set give?
A direct closed formula, a sum, or a recursive formula. Later chapters turn sums and recursions into closed formulas.
[Fundamental Counting Rules] yny_nyn is the number of strings over {0,1,2}\{0, 1, 2\}{0,1,2} of length nnn with an even number of 1s and an odd number of 2s. Which sum formula for yny_nyn do you get by first choosing the positions that hold a 1 or a 2?
yn=∑i=0⌊(n−1)/2⌋(n2i+1)22i\displaystyle \boldsymbol{y_n = \sum_{i=0}^{\lfloor (n-1)/2 \rfloor} \binom{n}{2i+1} 2^{2i}}yn=i=0∑⌊(n−1)/2⌋(2i+1n)22i Even plus odd is odd, so there are 2i+12i + 12i+1 such positions. Filling them with 1s and 2s gives 22i+12^{2i+1}22i+1 strings, and exactly half of them have an odd number of 2s (changing the first symbol flips that parity).
[Fundamental Counting Rules] yny_nyn is the number of strings over {0,1,2}\{0, 1, 2\}{0,1,2} of length nnn with an even number of 1s and an odd number of 2s. Which recursion holds for n≥1n \ge 1n≥1 , and why?
yn=3n−1−yn−1\boldsymbol{y_n = 3^{n-1} - y_{n-1}}yn=3n−1−yn−1 : the last symbol fixes the parities, except when the first n−1n - 1n−1 symbols have an odd number of 1s and an even number of 2s. For every other prefix exactly one last symbol works. Swapping 1 and 2 shows that the bad prefixes number yn−1y_{n-1}yn−1 . E.g. y1=1y_1 = 1y1=1 , y2=2y_2 = 2y2=2 , y3=7y_3 = 7y3=7 .
[Elementary Counting Coefficients] How is the binomial coefficient (nk)\binom{n}{k}(kn) defined (for k,n∈Nk, n \in \mathbb{N}k,n∈N )?
The number of kkk -subsets of an nnn -set. So (nk)=0\binom{n}{k} = 0(kn)=0 for k>nk > nk>n .
[Elementary Counting Coefficients] Why is (nk)=(nn−k)\binom{n}{k} = \binom{n}{n-k}(kn)=(n−kn) for k≤nk \le nk≤n ?
Taking complements is a bijection between the kkk -subsets and the (n−k)(n-k)(n−k) -subsets of an nnn -set.
[Elementary Counting Coefficients] For 1≤k≤n1 \le k \le n1≤k≤n , which recursion expresses (nk)\binom{n}{k}(kn) through binomial coefficients with n−1n - 1n−1 ?
(nk)=(n−1k−1)+(n−1k)\boldsymbol{\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}}(kn)=(k−1n−1)+(kn−1)
[Elementary Counting Coefficients] Why is (nk)=(n−1k−1)+(n−1k)\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}(kn)=(k−1n−1)+(kn−1) for 1≤k≤n1 \le k \le n1≤k≤n ?
Fix an element xxx of an nnn -set MMM : a kkk -subset either contains xxx or not. (n−1k−1)\binom{n-1}{k-1}(k−1n−1) subsets contain xxx (choose the other k−1k - 1k−1 from M∖{x}M \setminus \{x\}M∖{x} ), and (n−1k)\binom{n-1}{k}(kn−1) don't.
[Elementary Counting Coefficients] What is the closed formula for (nk)\binom{n}{k}(kn) , 0≤k≤n0 \le k \le n0≤k≤n ?
(nk)=n!k! (n−k)!\boldsymbol{\binom{n}{k} = \dfrac{n!}{k!\,(n-k)!}}(kn)=k!(n−k)!n!
[Elementary Counting Coefficients] For 1≤k≤n1 \le k \le n1≤k≤n : (nk)=(n−1k−1)+(n−1k)\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}(kn)=(k−1n−1)+(kn−1) .How does this prove (nk)=n!k!(n−k)!\binom{n}{k} = \frac{n!}{k!(n-k)!}(kn)=k!(n−k)!n! ?
Induction on n+kn + kn+k : insert the formula into both terms and add. (n−1)!(k−1)!(n−k)!+(n−1)!k!(n−k−1)!=(n−1)! (k+n−k)k!(n−k)!=n!k!(n−k)!\dfrac{(n-1)!}{(k-1)!(n-k)!} + \dfrac{(n-1)!}{k!(n-k-1)!} = \dfrac{(n-1)!\,(k + n - k)}{k!(n-k)!} = \dfrac{n!}{k!(n-k)!}(k−1)!(n−k)!(n−1)!+k!(n−k−1)!(n−1)!=k!(n−k)!(n−1)!(k+n−k)=k!(n−k)!n!
[Elementary Counting Coefficients] In Pascal's triangle (row nnn , column kkk holds (nk)\binom{n}{k}(kn) ), how does each entry arise from the row above?
It is the sum of the entry directly above it and the entry diagonally left above it. That is the recursion (nk)=(n−1k−1)+(n−1k)\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}(kn)=(k−1n−1)+(kn−1) .
[Elementary Counting Coefficients] What is the row sum ∑k=0n(nk)\displaystyle\sum_{k=0}^{n} \binom{n}{k}k=0∑n(kn) , and why?
2n\boldsymbol{2^n}2n : both sides count all subsets of an nnn -set (left side sorted by size).
[Elementary Counting Coefficients] What is the column sum ∑m=0n(mk)\displaystyle\sum_{m=0}^{n} \binom{m}{k}m=0∑n(km) in Pascal's triangle?
(n+1k+1)\boldsymbol{\binom{n+1}{k+1}}(k+1n+1)
[Elementary Counting Coefficients] Give a combinatorial argument for ∑m=0n(mk)=(n+1k+1)\displaystyle\sum_{m=0}^{n} \binom{m}{k} = \binom{n+1}{k+1}m=0∑n(km)=(k+1n+1) .
Choose k+1k + 1k+1 numbers from {1,…,n+1}\{1, \dots, n+1\}{1,…,n+1} and sort by the largest chosen number m+1m + 1m+1 : the other kkk come from {1,…,m}\{1, \dots, m\}{1,…,m} , in (mk)\binom{m}{k}(km) ways.
[Elementary Counting Coefficients] What is the diagonal sum ∑k=0n(m+kk)\displaystyle\sum_{k=0}^{n} \binom{m+k}{k}k=0∑n(km+k) in Pascal's triangle?
(m+n+1n)\boldsymbol{\binom{m+n+1}{n}}(nm+n+1)
[Elementary Counting Coefficients] Give a combinatorial argument for ∑k=0n(m+kk)=(m+n+1n)\displaystyle\sum_{k=0}^{n} \binom{m+k}{k} = \binom{m+n+1}{n}k=0∑n(km+k)=(nm+n+1) .
Choose nnn numbers from {1,…,m+n+1}\{1, \dots, m+n+1\}{1,…,m+n+1} and sort by the largest number not chosen, m+k+1m + k + 1m+k+1 : all n−kn - kn−k numbers above it are chosen, and kkk of the m+km + km+k numbers below it, in (m+kk)\binom{m+k}{k}(km+k) ways.
[Elementary Counting Coefficients] Binomial theorem. For x,y∈Rx, y \in \mathbb{R}x,y∈R and n∈Nn \in \mathbb{N}n∈N : (x+y)n= ?(x + y)^n = \; ?(x+y)n=?
∑k=0n(nk)xkyn−k\displaystyle \boldsymbol{\sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}}k=0∑n(kn)xkyn−k Proof: expanding (x+y)⋯(x+y)(x + y) \cdots (x + y)(x+y)⋯(x+y) , the coefficient of xkyn−kx^k y^{n-k}xkyn−k is the number of ways to pick xxx from kkk of the nnn factors.
[Elementary Counting Coefficients] What is the Stirling number of the second kind Sn,kS_{n,k}Sn,k ?
The number of ways to partition an nnn -set into kkk nonempty sets. By convention S0,0=1S_{0,0} = 1S0,0=1 .
[Elementary Counting Coefficients] For n>0n > 0n>0 , what are Sn,0S_{n,0}Sn,0 , Sn,1S_{n,1}Sn,1 and Sn,2S_{n,2}Sn,2 (Stirling numbers of the second kind: partitions of an nnn -set into kkk nonempty sets)?
Sn,0=0S_{n,0} = \boldsymbol{0}Sn,0=0 , Sn,1=1\ S_{n,1} = \boldsymbol{1} Sn,1=1 , Sn,2=2n−1−1\ S_{n,2} = \boldsymbol{2^{n-1} - 1} Sn,2=2n−1−1 For Sn,2S_{n,2}Sn,2 : fix an element xxx ; its block is xxx together with any subset of the other n−1n - 1n−1 elements except all of them (the other block must be nonempty).
[Elementary Counting Coefficients] For n,k≥1n, k \ge 1n,k≥1 , which recursion holds for the Stirling numbers of the second kind Sn,kS_{n,k}Sn,k (partitions of an nnn -set into kkk nonempty sets)?
Sn,k=Sn−1,k−1+k Sn−1,k\boldsymbol{S_{n,k} = S_{n-1,k-1} + k\,S_{n-1,k}}Sn,k=Sn−1,k−1+kSn−1,k
[Elementary Counting Coefficients] Why does Sn,k=Sn−1,k−1+k Sn−1,kS_{n,k} = S_{n-1,k-1} + k\,S_{n-1,k}Sn,k=Sn−1,k−1+kSn−1,k hold ( Sn,kS_{n,k}Sn,k : partitions of an nnn -set into kkk nonempty sets)?
Fix an element xxx : either {x}\{x\}{x} is a block, or xxx lies in a block with other elements. {x}\{x\}{x} a block: the rest is a partition of the other n−1n - 1n−1 elements into k−1k - 1k−1 sets. Otherwise: removing xxx leaves a partition into kkk sets, and xxx was in one of those kkk .
[Elementary Counting Coefficients] Compute S4,3S_{4,3}S4,3 , the number of partitions of a 4-set into 3 nonempty sets.
6\boldsymbol{6}6 S4,3=S3,2+3S3,3=3+3S_{4,3} = S_{3,2} + 3 S_{3,3} = 3 + 3S4,3=S3,2+3S3,3=3+3 . Directly: one block has 2 elements, the others are singletons, and the pair can be chosen in (42)\binom{4}{2}(24) ways.
[Elementary Counting Coefficients] What is Pn,kP_{n,k}Pn,k (the number of partitions of the number nnn into kkk parts)?
The number of ways to write nnn as a sum of kkk positive integers, ignoring the order of the summands. e.g. P6,3=3P_{6,3} = 3P6,3=3 : 6=4+1+1=3+2+1=2+2+2\ 6 = 4+1+1 = 3+2+1 = 2+2+2 6=4+1+1=3+2+1=2+2+2 .
[Elementary Counting Coefficients] For n>0n > 0n>0 , what are Pn,0P_{n,0}Pn,0 , Pn,1P_{n,1}Pn,1 and Pn,2P_{n,2}Pn,2 ( Pn,kP_{n,k}Pn,k : ways to write nnn as an unordered sum of kkk positive integers)?
Pn,0=0P_{n,0} = \boldsymbol{0}Pn,0=0 , Pn,1=1\ P_{n,1} = \boldsymbol{1} Pn,1=1 , Pn,2=⌊n/2⌋\ P_{n,2} = \boldsymbol{\lfloor n/2 \rfloor} Pn,2=⌊n/2⌋ For Pn,2P_{n,2}Pn,2 : n=a+bn = a + bn=a+b with a≥b≥1a \ge b \ge 1a≥b≥1 , and bbb can be any of 1,…,⌊n/2⌋1, \dots, \lfloor n/2 \rfloor1,…,⌊n/2⌋ .
[Elementary Counting Coefficients] For n≥k≥1n \ge k \ge 1n≥k≥1 , which recursion holds for Pn,kP_{n,k}Pn,k (ways to write nnn as an unordered sum of kkk positive integers), and why?
Pn,k=Pn−k,k+Pn−1,k−1\boldsymbol{P_{n,k} = P_{n-k,k} + P_{n-1,k-1}}Pn,k=Pn−k,k+Pn−1,k−1 If a summand is 1, removing it gives a partition of n−1n - 1n−1 into k−1k - 1k−1 parts. If all summands are at least 2, subtracting 1 from each gives a partition of n−kn - kn−k into kkk parts.
[Elementary Counting Coefficients] Compute P7,3P_{7,3}P7,3 , the number of ways to write 7 as an unordered sum of 3 positive integers.
4\boldsymbol{4}4 5+1+15+1+15+1+1 , 4+2+14+2+14+2+1 , 3+3+13+3+13+3+1 , 3+2+23+2+23+2+2 . By the recursion: P7,3=P4,3+P6,2=1+3P_{7,3} = P_{4,3} + P_{6,2} = 1 + 3P7,3=P4,3+P6,2=1+3 .
[Elementary Counting Coefficients] What is an ordered partition of a number nnn into kkk summands?
A way to write nnn as a sum of kkk positive integers where the order of the summands matters. 5 has 6 ordered 3-partitions: 3+1+13+1+13+1+1 , 1+3+11+3+11+3+1 , 1+1+31+1+31+1+3 , 2+2+12+2+12+2+1 , 2+1+22+1+22+1+2 , 1+2+21+2+21+2+2 .
[Elementary Counting Coefficients] How many ordered partitions of a positive integer nnn into kkk summands are there?
(n−1k−1)\boldsymbol{\binom{n-1}{k-1}}(k−1n−1)
[Elementary Counting Coefficients] Why are there (n−1k−1)\binom{n-1}{k-1}(k−1n−1) ordered partitions of a positive integer nnn into kkk summands?
Write nnn as nnn ones; an ordered partition is a choice of k−1k - 1k−1 of the n−1n - 1n−1 gaps between them (to put separators ⊕\oplus⊕ in). The blocks between separators have lengths x1,…,xkx_1, \dots, x_kx1,…,xk , the summands.
[Assignments] How many surjective mappings are there from an nnn -set to an rrr -set, and why?
r! Sn,r\boldsymbol{r!\,S_{n,r}}r!Sn,r ( Sn,rS_{n,r}Sn,r : partitions of an nnn -set into rrr nonempty sets) The preimages of a surjective mapping partition the nnn -set into rrr nonempty sets ( Sn,rS_{n,r}Sn,r ways), and these rrr preimages are assigned to the rrr elements bijectively ( r!r!r! ways).
[Assignments] What are the nnn -th falling factorial rn‾r^{\underline{n}}rn and the nnn -th rising factorial rn‾r^{\overline{n}}rn of rrr ?
rn‾=r(r−1)⋯(r−n+1)\boldsymbol{r^{\underline{n}} = r(r-1)\cdots(r-n+1)}rn=r(r−1)⋯(r−n+1) , rn‾=r(r+1)⋯(r+n−1)\quad \boldsymbol{r^{\overline{n}} = r(r+1)\cdots(r+n-1)}rn=r(r+1)⋯(r+n−1) Both have nnn factors.
[Assignments] How many injective mappings are there from an nnn -set to an rrr -set?
rn‾=r(r−1)⋯(r−n+1)\boldsymbol{r^{\underline{n}} = r(r-1)\cdots(r-n+1)}rn=r(r−1)⋯(r−n+1) , the nnn -th falling factorial of rrr . Choose the images one element at a time: rrr choices, then r−1r - 1r−1 , and so on. This is 0 when n>rn > rn>r .
[Assignments] What is a kkk -multiset over an nnn -set AAA ?
A mapping f:A→Nf : A \to \mathbb{N}f:A→N with ∑a∈Af(a)=k\sum_{a \in A} f(a) = k∑a∈Af(a)=k . f(a)f(a)f(a) says how often aaa occurs ( f(a)=0f(a) = 0f(a)=0 allowed). Written {a1,…,ak}\{a_1, \dots, a_k\}{a1,…,ak} , where ai=aja_i = a_jai=aj for i≠ji \ne ji=j is possible.
[Assignments] How many kkk -multisets over an nnn -set are there?
nk‾k!=(n+k−1k)\boldsymbol{\dfrac{n^{\overline{k}}}{k!} = \binom{n+k-1}{k}}k!nk=(kn+k−1) nk‾=n(n+1)⋯(n+k−1)n^{\overline{k}} = n(n+1)\cdots(n+k-1)nk=n(n+1)⋯(n+k−1) is the rising factorial.
[Assignments] Which bijection shows that there are (n+k−1k)\binom{n+k-1}{k}(kn+k−1) kkk -multisets over {1,…,n}\{1, \dots, n\}{1,…,n} ?
{a1,…,ak}\{a_1, \dots, a_k\}{a1,…,ak} with a1≤⋯≤aka_1 \le \dots \le a_ka1≤⋯≤ak goes to the kkk -subset {a1, a2+1, a3+2, …, ak+k−1}\{a_1, \ a_2 + 1, \ a_3 + 2, \ \dots, \ a_k + k - 1\}{a1, a2+1, a3+2, …, ak+k−1} of {1,…,n+k−1}\{1, \dots, n+k-1\}{1,…,n+k−1} . Adding i−1i - 1i−1 to the iii -th element makes the sequence strictly increasing; subtracting it again is the inverse.
[Assignments] For n,r∈Nn, r \in \mathbb{N}n,r∈N , how is rnr^nrn written with Stirling numbers of the second kind Sn,kS_{n,k}Sn,k and falling factorials rk‾=r(r−1)⋯(r−k+1)r^{\underline{k}} = r(r-1)\cdots(r-k+1)rk=r(r−1)⋯(r−k+1) ?
rn=∑k=0nSn,k rk‾\displaystyle \boldsymbol{r^n = \sum_{k=0}^{n} S_{n,k}\, r^{\underline{k}}}rn=k=0∑nSn,krk
[Assignments] For n,r∈Nn, r \in \mathbb{N}n,r∈N : rn=∑k=0nSn,k rk‾\displaystyle r^n = \sum_{k=0}^{n} S_{n,k}\, r^{\underline{k}}rn=k=0∑nSn,krk .How does the proof count?
Count the rnr^nrn mappings from an nnn -set NNN to an rrr -set RRR by their image A⊆RA \subseteq RA⊆R . ∣A∣=k|A| = k∣A∣=k : (rk)\binom{r}{k}(kr) choices of AAA and k! Sn,kk!\,S_{n,k}k!Sn,k surjections onto AAA , and (rk)k!=rk‾\binom{r}{k} k! = r^{\underline{k}}(kr)k!=rk . The sum may stop at nnn or at rrr , since Sn,k=0S_{n,k} = 0Sn,k=0 for k>nk > nk>n and rk‾=0r^{\underline{k}} = 0rk=0 for k>rk > rk>r .
[Assignments] The mappings from an nnn -set NNN to an rrr -set RRR ( nnn balls into rrr bins) are counted in a 4 × 4 table. What do its rows and columns distinguish?
Rows: whether the elements of NNN , and of RRR , are distinguishable. Columns: arbitrary, injective, surjective, bijective mappings. Sn,kS_{n,k}Sn,k : set partitions into kkk blocks, Pn,kP_{n,k}Pn,k : number partitions into kkk parts.
[Assignments] nnn distinguishable balls go into rrr distinguishable bins. How many ways are there in total, with at most one ball per bin, and with no empty bin?
rn\boldsymbol{r^n}rn , rn‾\ \boldsymbol{r^{\underline{n}}} rn , r! Sn,r\ \boldsymbol{r!\,S_{n,r}} r!Sn,r All mappings, injective mappings, surjective mappings from an nnn -set to an rrr -set.
[Assignments] nnn indistinguishable balls go into rrr distinguishable bins. How many ways are there in total, with at most one ball per bin, and with no empty bin?
rn‾n!=(n+r−1n)\boldsymbol{\frac{r^{\overline{n}}}{n!} = \binom{n+r-1}{n}}n!rn=(nn+r−1) , (rn)\ \boldsymbol{\binom{r}{n}} (nr) , (n−1r−1)\ \boldsymbol{\binom{n-1}{r-1}} (r−1n−1) Total: an nnn -multiset over the rrr bins. At most one: choose the nnn occupied bins. No empty bin: the bin contents form an ordered partition of nnn into rrr summands.
[Assignments] nnn distinguishable balls go into rrr indistinguishable bins. How many ways are there in total, with at most one ball per bin, and with no empty bin?
∑k=1rSn,k\displaystyle \boldsymbol{\sum_{k=1}^{r} S_{n,k}}k=1∑rSn,k , \ 1 if r≥nr \ge nr≥n (else 0), Sn,r\ \boldsymbol{S_{n,r}} Sn,r Only the partition of the balls into nonempty groups matters ( Sn,kS_{n,k}Sn,k : partitions of an nnn -set into kkk nonempty sets). With one ball per bin all ways look the same.
[Assignments] nnn indistinguishable balls go into rrr indistinguishable bins. How many ways are there in total, with at most one ball per bin, and with no empty bin?
∑k=1rPn,k\displaystyle \boldsymbol{\sum_{k=1}^{r} P_{n,k}}k=1∑rPn,k , \ 1 if r≥nr \ge nr≥n (else 0), Pn,r\ \boldsymbol{P_{n,r}} Pn,r Only the multiset of nonempty bin sizes matters, a partition of the number nnn ( Pn,kP_{n,k}Pn,k : into kkk parts).
[Assignments] nnn balls go into rrr bins with exactly one ball per bin (a bijection). How many ways are there?
0 if n≠rn \ne rn=r . If n=rn = rn=r : n!n!n! when balls and bins are both distinguishable, and 1 otherwise.
[Assignments] 5 indistinguishable balls go into 3 distinguishable bins, no bin empty. How many ways are there?
6=(42)\boldsymbol{6 = \binom{4}{2}}6=(24) The bin contents form an ordered partition of 5 into 3 summands: 3+1+13+1+13+1+1 , 1+3+11+3+11+3+1 , 1+1+31+1+31+1+3 , 2+2+12+2+12+2+1 , 2+1+22+1+22+1+2 , 1+2+21+2+21+2+2 .
[Generalized Counting Coefficients] How are the falling factorial rk‾r^{\underline{k}}rk and rising factorial rk‾r^{\overline{k}}rk defined for r∈Cr \in \mathbb{C}r∈C and k∈Nk \in \mathbb{N}k∈N ?
rk‾=r(r−1)⋯(r−k+1)\boldsymbol{r^{\underline{k}} = r(r-1)\cdots(r-k+1)}rk=r(r−1)⋯(r−k+1) , rk‾=r(r+1)⋯(r+k−1)\quad \boldsymbol{r^{\overline{k}} = r(r+1)\cdots(r+k-1)}rk=r(r+1)⋯(r+k−1) Products of kkk factors, so r0‾=r0‾=1r^{\underline{0}} = r^{\overline{0}} = 1r0=r0=1 .
[Generalized Counting Coefficients] How is the binomial coefficient (rk)\binom{r}{k}(kr) defined for r∈Cr \in \mathbb{C}r∈C and k∈Zk \in \mathbb{Z}k∈Z ?
(rk)=rk‾k!\boldsymbol{\binom{r}{k} = \dfrac{r^{\underline{k}}}{k!}}(kr)=k!rk for k≥0k \ge 0k≥0 , and 0\boldsymbol{0}0 for k<0k < 0k<0 . rk‾=r(r−1)⋯(r−k+1)r^{\underline{k}} = r(r-1)\cdots(r-k+1)rk=r(r−1)⋯(r−k+1) . e.g. (1/22)=(1/2)(−1/2)2=−18\binom{1/2}{2} = \frac{(1/2)(-1/2)}{2} = -\frac{1}{8}(21/2)=2(1/2)(−1/2)=−81 .
[Generalized Counting Coefficients] What is the polynomial method for proving an identity for all r∈Cr \in \mathbb{C}r∈C ?
Prove it for infinitely many values (e.g. all positive integers rrr ), where both sides are polynomials in rrr : then they are identical. Their difference is a polynomial with infinitely many roots, so it is 0.
[Generalized Counting Coefficients] How does the polynomial method prove (rk)=(r−1k−1)+(r−1k)\binom{r}{k} = \binom{r-1}{k-1} + \binom{r-1}{k}(kr)=(k−1r−1)+(kr−1) for all r∈Cr \in \mathbb{C}r∈C , k∈Zk \in \mathbb{Z}k∈Z ?
For fixed k>0k > 0k>0 both sides are polynomials in rrr of degree kkk , and they agree for every positive integer rrr (counting kkk -subsets). So they agree everywhere. The case k≤0k \le 0k≤0 is direct: for k<0k < 0k<0 all terms are 0; for k=0k = 0k=0 it reads 1=0+11 = 0 + 11=0+1 .
[Generalized Counting Coefficients] Vandermonde identity. For x,y∈Cx, y \in \mathbb{C}x,y∈C and n∈Nn \in \mathbb{N}n∈N : (x+yn)= ?\binom{x+y}{n} = \; ?(nx+y)=?
∑k=0n(xk)(yn−k)\displaystyle \boldsymbol{\sum_{k=0}^{n} \binom{x}{k} \binom{y}{n-k}}k=0∑n(kx)(n−ky)
[Generalized Counting Coefficients] Vandermonde identity: (x+yn)=∑k=0n(xk)(yn−k)\displaystyle\binom{x+y}{n} = \sum_{k=0}^{n} \binom{x}{k} \binom{y}{n-k}(nx+y)=k=0∑n(kx)(n−ky) for x,y∈Cx, y \in \mathbb{C}x,y∈C .How is it proved?
For x,y∈Nx, y \in \mathbb{N}x,y∈N both sides count the nnn -subsets of an (x+y)(x+y)(x+y) -set; then the polynomial method. Split the set into an xxx -set and a yyy -set and sort the nnn -subsets by how many elements kkk they take from the xxx -set. Both sides are polynomials of degree nnn that agree on infinitely many points.
[Generalized Counting Coefficients] For r∈Cr \in \mathbb{C}r∈C and k∈Zk \in \mathbb{Z}k∈Z , how is (−rk)\binom{-r}{k}(k−r) written as a binomial coefficient with positive upper entry?
(−rk)=(−1)k(r+k−1k)\boldsymbol{\binom{-r}{k} = (-1)^k \binom{r+k-1}{k}}(k−r)=(−1)k(kr+k−1)
[Generalized Counting Coefficients] For r∈Cr \in \mathbb{C}r∈C , k∈Zk \in \mathbb{Z}k∈Z : (−rk)=(−1)k(r+k−1k)\binom{-r}{k} = (-1)^k \binom{r+k-1}{k}(k−r)=(−1)k(kr+k−1) .Why does this hold?
(−r)k‾=(−r)(−r−1)⋯(−r−k+1)=(−1)k rk‾\boldsymbol{(-r)^{\underline{k}} = (-r)(-r-1)\cdots(-r-k+1) = (-1)^k\, r^{\overline{k}}}(−r)k=(−r)(−r−1)⋯(−r−k+1)=(−1)krk ; divide by k!k!k! . And rk‾k!=r(r+1)⋯(r+k−1)k!=(r+k−1k)\frac{r^{\overline{k}}}{k!} = \frac{r(r+1)\cdots(r+k-1)}{k!} = \binom{r+k-1}{k}k!rk=k!r(r+1)⋯(r+k−1)=(kr+k−1) .
[Generalized Counting Coefficients] Compute (−1k)\binom{-1}{k}(k−1) for k∈Nk \in \mathbb{N}k∈N .
(−1)k\boldsymbol{(-1)^k}(−1)k (−1k)=(−1)k(kk)\binom{-1}{k} = (-1)^k \binom{k}{k}(k−1)=(−1)k(kk) , or directly (−1)(−2)⋯(−k)k!\frac{(-1)(-2)\cdots(-k)}{k!}k!(−1)(−2)⋯(−k) .
[Generalized Counting Coefficients] What is the alternating partial row sum ∑k=0m(−1)k(nk)\displaystyle\sum_{k=0}^{m} (-1)^k \binom{n}{k}k=0∑m(−1)k(kn) of Pascal's triangle?
(−1)m(n−1m)\boldsymbol{(-1)^m \binom{n-1}{m}}(−1)m(mn−1) Combinatorially: ±\pm± the number of mmm -subsets of {1,…,n−1}\{1, \dots, n-1\}{1,…,n−1} , with sign +++ for even mmm .
[Generalized Counting Coefficients] Negation: (−rk)=(−1)k(r+k−1k)\binom{-r}{k} = (-1)^k \binom{r+k-1}{k}(k−r)=(−1)k(kr+k−1) . \quad Diagonal sum: ∑k=0m(a+kk)=(a+m+1m)\sum_{k=0}^{m} \binom{a+k}{k} = \binom{a+m+1}{m}∑k=0m(ka+k)=(ma+m+1) , valid for all a∈Ca \in \mathbb{C}a∈C .How do these give ∑k=0m(−1)k(nk)=(−1)m(n−1m)\displaystyle\sum_{k=0}^{m} (-1)^k \binom{n}{k} = (-1)^m \binom{n-1}{m}k=0∑m(−1)k(kn)=(−1)m(mn−1) ?
Negation turns each term into (k−n−1k)\binom{k-n-1}{k}(kk−n−1) ; the diagonal sum with a=−n−1a = -n-1a=−n−1 gives (m−nm)\binom{m-n}{m}(mm−n) ; negation again gives (−1)m(n−1m)(-1)^m \binom{n-1}{m}(−1)m(mn−1) . The diagonal sum extends from a∈Na \in \mathbb{N}a∈N to a∈Ca \in \mathbb{C}a∈C by the polynomial method.
[Permutations] What is an nnn -permutation?
A bijection π:{1,…,n}→{1,…,n}\pi : \{1, \dots, n\} \to \{1, \dots, n\}π:{1,…,n}→{1,…,n} .
[Permutations] What is a cycle of a permutation π\piπ of {1,…,n}\{1, \dots, n\}{1,…,n} ?
A set {i1,…,it}\{i_1, \dots, i_t\}{i1,…,it} with π(ij)=ij+1\pi(i_j) = i_{j+1}π(ij)=ij+1 for j<tj < tj<t and π(it)=i1\pi(i_t) = i_1π(it)=i1 . Written (i1,…,it)(i_1, \dots, i_t)(i1,…,it) , with ttt possible choices of the first element. A fixed point is a cycle of length 1.
[Permutations] What is the Stirling number of the first kind sn,ks_{n,k}sn,k ?
The number of nnn -permutations with kkk cycles. By convention s0,0=1s_{0,0} = 1s0,0=1 . Fixed points count as cycles (of length 1).
[Permutations] For n>0n > 0n>0 , what are sn,0s_{n,0}sn,0 and sn,1s_{n,1}sn,1 ( sn,ks_{n,k}sn,k : number of nnn -permutations with kkk cycles)?
sn,0=0s_{n,0} = \boldsymbol{0}sn,0=0 , sn,1=(n−1)!\ s_{n,1} = \boldsymbol{(n-1)!} sn,1=(n−1)! One cycle through all nnn elements: write it starting with 1, then the other n−1n - 1n−1 elements in any order.
[Permutations] For n,k≥1n, k \ge 1n,k≥1 , which recursion holds for the Stirling numbers of the first kind sn,ks_{n,k}sn,k (number of nnn -permutations with kkk cycles)?
sn,k=sn−1,k−1+(n−1) sn−1,k\boldsymbol{s_{n,k} = s_{n-1,k-1} + (n-1)\,s_{n-1,k}}sn,k=sn−1,k−1+(n−1)sn−1,k
[Permutations] Why does sn,k=sn−1,k−1+(n−1) sn−1,ks_{n,k} = s_{n-1,k-1} + (n-1)\,s_{n-1,k}sn,k=sn−1,k−1+(n−1)sn−1,k hold ( sn,ks_{n,k}sn,k : number of nnn -permutations with kkk cycles)?
Either nnn is a fixed point, or nnn sits inside a longer cycle. Fixed point: the rest is an (n−1)(n-1)(n−1) -permutation with k−1k - 1k−1 cycles. Otherwise: deleting nnn from its cycle leaves an (n−1)(n-1)(n−1) -permutation with kkk cycles, and nnn can be put back after any of its n−1n - 1n−1 elements.
[Permutations] What is the nnn -th harmonic number HnH_nHn , and how fast does it grow?
Hn=∑i=1n1i\displaystyle \boldsymbol{H_n = \sum_{i=1}^{n} \frac{1}{i}}Hn=i=1∑ni1 , and Hn∈Θ(ln⁡n)H_n \in \Theta(\ln n)Hn∈Θ(lnn) . More precisely ln⁡n+1n≤Hn≤ln⁡n+1\ln n + \frac{1}{n} \le H_n \le \ln n + 1lnn+n1≤Hn≤lnn+1 for positive nnn (compare with ∫1x dx=ln⁡x\int \frac{1}{x}\,dx = \ln x∫x1dx=lnx ).
[Permutations] For n≥1n \ge 1n≥1 , what is sn,2s_{n,2}sn,2 , the number of nnn -permutations with exactly 2 cycles?
sn,2=(n−1)! Hn−1\boldsymbol{s_{n,2} = (n-1)!\, H_{n-1}}sn,2=(n−1)!Hn−1 Hn−1=1+12+⋯+1n−1H_{n-1} = 1 + \frac{1}{2} + \dots + \frac{1}{n-1}Hn−1=1+21+⋯+n−11 , the harmonic number.
[Permutations] Stirling numbers of the first kind: sn,k=sn−1,k−1+(n−1) sn−1,ks_{n,k} = s_{n-1,k-1} + (n-1)\,s_{n-1,k}sn,k=sn−1,k−1+(n−1)sn−1,k and sn,1=(n−1)!s_{n,1} = (n-1)!sn,1=(n−1)! .How does induction prove sn,2=(n−1)! Hn−1s_{n,2} = (n-1)!\,H_{n-1}sn,2=(n−1)!Hn−1 ?
Divide the recursion for sn,2s_{n,2}sn,2 by (n−1)!(n-1)!(n−1)! : sn,2(n−1)!=(n−2)!(n−1)!+sn−1,2(n−2)!=1n−1+Hn−2=Hn−1\dfrac{s_{n,2}}{(n-1)!} = \dfrac{(n-2)!}{(n-1)!} + \dfrac{s_{n-1,2}}{(n-2)!} = \dfrac{1}{n-1} + H_{n-2} = H_{n-1}(n−1)!sn,2=(n−1)!(n−2)!+(n−2)!sn−1,2=n−11+Hn−2=Hn−1 . Base case n=1n = 1n=1 : both sides are 0.
[Permutations] Compute s4,2s_{4,2}s4,2 , the number of permutations of {1,2,3,4}\{1, 2, 3, 4\}{1,2,3,4} with exactly 2 cycles.
11\boldsymbol{11}11 3! H3=6⋅1163!\,H_3 = 6 \cdot \frac{11}{6}3!H3=6⋅611 . Directly: 8 permutations of shape (3-cycle)(fixed point) and 3 of shape (2-cycle)(2-cycle).
[Permutations] What do the two kinds of Stirling numbers have to do with the bases {r0,r1,r2,… }\{r^0, r^1, r^2, \dots\}{r0,r1,r2,…} and {r0‾,r1‾,r2‾,… }\{r^{\underline{0}}, r^{\underline{1}}, r^{\underline{2}}, \dots\}{r0,r1,r2,…} of the polynomials?
They are the coefficients for changing between the two bases: rn=∑k=0nSn,k rk‾\displaystyle r^n = \sum_{k=0}^{n} S_{n,k}\, r^{\underline{k}}rn=k=0∑nSn,krk \ and \ rn‾=∑k=0n(−1)n−ksn,k rk\displaystyle r^{\underline{n}} = \sum_{k=0}^{n} (-1)^{n-k} s_{n,k}\, r^krn=k=0∑n(−1)n−ksn,krk , for all r∈Cr \in \mathbb{C}r∈C . ( rk‾=r(r−1)⋯(r−k+1)r^{\underline{k}} = r(r-1)\cdots(r-k+1)rk=r(r−1)⋯(r−k+1) .)
[Permutations] For n∈Nn \in \mathbb{N}n∈N and r∈Cr \in \mathbb{C}r∈C , how is the falling factorial rn‾r^{\underline{n}}rn expanded in powers rkr^krk , using Stirling numbers of the first kind sn,ks_{n,k}sn,k ?
rn‾=∑k=0n(−1)n−k sn,k rk\displaystyle \boldsymbol{r^{\underline{n}} = \sum_{k=0}^{n} (-1)^{n-k}\, s_{n,k}\, r^k}rn=k=0∑n(−1)n−ksn,krk
[Permutations] rn‾=∑k=0n(−1)n−k sn,k rk\displaystyle r^{\underline{n}} = \sum_{k=0}^{n} (-1)^{n-k}\, s_{n,k}\, r^krn=k=0∑n(−1)n−ksn,krk , where sn,k=sn−1,k−1+(n−1) sn−1,ks_{n,k} = s_{n-1,k-1} + (n-1)\,s_{n-1,k}sn,k=sn−1,k−1+(n−1)sn−1,k .What is the key step of the proof by induction on nnn ?
Write rn‾=(r−(n−1)) rn−1‾r^{\underline{n}} = (r - (n-1))\, r^{\underline{n-1}}rn=(r−(n−1))rn−1 and expand rn−1‾r^{\underline{n-1}}rn−1 by induction. The factor rrr shifts the index and yields the sn−1,k−1s_{n-1,k-1}sn−1,k−1 terms, the factor −(n−1)-(n-1)−(n−1) yields the (n−1) sn−1,k(n-1)\,s_{n-1,k}(n−1)sn−1,k terms; the recursion combines them. (Set sn,k=0s_{n,k} = 0sn,k=0 for k<0k < 0k<0 ; the recursion still holds.)
[Permutations] What is the type t(π)t(\pi)t(π) of an nnn -permutation π\piπ ?
The formal term 1b12b2⋯nbn1^{b_1} 2^{b_2} \cdots n^{b_n}1b12b2⋯nbn , where bi=bi(π)b_i = b_i(\pi)bi=bi(π) is the number of cycles of length iii (factors with bi=0b_i = 0bi=0 are skipped). e.g. the permutation (1,3)(2)(4,5,6)(7)(1, 3)(2)(4, 5, 6)(7)(1,3)(2)(4,5,6)(7) of {1,…,7}\{1, \dots, 7\}{1,…,7} has type 12 21 311^2\, 2^1\, 3^1122131 .
[Permutations] bi(π)b_i(\pi)bi(π) is the number of cycles of length iii of an nnn -permutation π\piπ . What are ∑i=1ni bi(π)\displaystyle\sum_{i=1}^{n} i\, b_i(\pi)i=1∑nibi(π) and ∑i=1nbi(π)\displaystyle\sum_{i=1}^{n} b_i(\pi)i=1∑nbi(π) ?
∑ii bi(π)=n\displaystyle\sum_i i\, b_i(\pi) = \boldsymbol{n}i∑ibi(π)=n , ∑ibi(π)=\ \ \displaystyle\sum_i b_i(\pi) = i∑bi(π)= the total number of cycles b(π)b(\pi)b(π) .
[Permutations] How many types (cycle-length patterns 1b12b2⋯nbn1^{b_1} 2^{b_2} \cdots n^{b_n}1b12b2⋯nbn ) of nnn -permutations are there, and why?
∑k=0nPn,k\displaystyle \boldsymbol{\sum_{k=0}^{n} P_{n,k}}k=0∑nPn,k , the number of partitions of the number nnn . The type 1b1⋯nbn1^{b_1} \cdots n^{b_n}1b1⋯nbn corresponds to writing nnn as a sum in which iii occurs bib_ibi times. ( Pn,kP_{n,k}Pn,k : unordered sums of kkk positive integers.)
[Permutations] How many nnn -permutations have type 1b12b2⋯nbn1^{b_1} 2^{b_2} \cdots n^{b_n}1b12b2⋯nbn ( bib_ibi cycles of length iii )?
n!b1!⋯bn! 1b12b2⋯nbn\boldsymbol{\dfrac{n!}{b_1! \cdots b_n!\; 1^{b_1} 2^{b_2} \cdots n^{b_n}}}b1!⋯bn!1b12b2⋯nbnn!
[Permutations] There are n!b1!⋯bn! 1b12b2⋯nbn\dfrac{n!}{b_1! \cdots b_n!\; 1^{b_1} 2^{b_2} \cdots n^{b_n}}b1!⋯bn!1b12b2⋯nbnn! permutations of {1,…,n}\{1, \dots, n\}{1,…,n} with bib_ibi cycles of length iii .How does the proof count?
Fill 1,…,n1, \dots, n1,…,n into a fixed pattern of empty cycles ( n!n!n! ways); each permutation arises b1!⋯bn! 1b1⋯nbnb_1! \cdots b_n!\; 1^{b_1} \cdots n^{b_n}b1!⋯bn!1b1⋯nbn times. bi!b_i!bi! : reordering the cycles of length iii . ibi\ i^{b_i} ibi : each cycle of length iii can start with any of its iii elements.
[Permutations] How many permutations of {1,2,3,4}\{1, 2, 3, 4\}{1,2,3,4} consist of two cycles of length 2 (type 222^222 )?
3\boldsymbol{3}3 4!2!⋅22=3\frac{4!}{2! \cdot 2^2} = 32!⋅224!=3 : (1,2)(3,4)\ (1,2)(3,4) (1,2)(3,4) , (1,3)(2,4)(1,3)(2,4)(1,3)(2,4) , (1,4)(2,3)(1,4)(2,3)(1,4)(2,3) .
[Permutations] There are n!b1!⋯bn! 1b1⋯nbn\dfrac{n!}{b_1! \cdots b_n!\; 1^{b_1} \cdots n^{b_n}}b1!⋯bn!1b1⋯nbnn! nnn -permutations with bib_ibi cycles of length iii .Which sum formula for sn,ks_{n,k}sn,k (number of nnn -permutations with kkk cycles) follows?
sn,k=∑n!b1!⋯bn! 1b1⋯nbn\displaystyle \boldsymbol{s_{n,k} = \sum \frac{n!}{b_1! \cdots b_n!\; 1^{b_1} \cdots n^{b_n}}}sn,k=∑b1!⋯bn!1b1⋯nbnn! over all (b1,…,bn)(b_1, \dots, b_n)(b1,…,bn) with ∑ii bi=n\sum_i i\,b_i = n∑iibi=n and ∑ibi=k\sum_i b_i = k∑ibi=k . Dropping the condition ∑ibi=k\sum_i b_i = k∑ibi=k , the same sum equals n!n!n! .
[Further Combinatorial Techniques] Inclusion-exclusion principle. For finite sets A1,…,AnA_1, \dots, A_nA1,…,An : ∣⋃i=1nAi∣= ?\left|\bigcup_{i=1}^{n} A_i\right| = \; ?∣⋃i=1nAi∣=?
∑r=1n(−1)r−1∑1≤i1<⋯<ir≤n∣Ai1∩⋯∩Air∣\displaystyle \boldsymbol{\sum_{r=1}^{n} (-1)^{r-1} \sum_{1 \le i_1 < \dots < i_r \le n} \left| A_{i_1} \cap \dots \cap A_{i_r} \right|}r=1∑n(−1)r−11≤i1<⋯<ir≤n∑∣Ai1∩⋯∩Air∣
[Further Combinatorial Techniques] Inclusion-exclusion: ∣⋃i=1nAi∣=∑r=1n(−1)r−1∑i1<⋯<ir∣Ai1∩⋯∩Air∣\displaystyle\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{r=1}^{n} (-1)^{r-1} \sum_{i_1 < \dots < i_r} \left| A_{i_1} \cap \dots \cap A_{i_r} \right|∣∣i=1⋃nAi∣∣=r=1∑n(−1)r−1i1<⋯<ir∑∣Ai1∩⋯∩Air∣ .How does the proof go?
An element aaa lying in exactly k≥1k \ge 1k≥1 of the sets is counted (kr)\binom{k}{r}(rk) times in the rrr -th inner sum, so ∑r=1k(−1)r−1(kr)=1\sum_{r=1}^{k} (-1)^{r-1} \binom{k}{r} = 1∑r=1k(−1)r−1(rk)=1 time in total. By the binomial theorem, 0=(−1+1)k=∑r=0k(kr)(−1)r=1−∑r=1k(−1)r−1(kr)0 = (-1 + 1)^k = \sum_{r=0}^{k} \binom{k}{r} (-1)^r = 1 - \sum_{r=1}^{k} (-1)^{r-1} \binom{k}{r}0=(−1+1)k=∑r=0k(rk)(−1)r=1−∑r=1k(−1)r−1(rk) .
[Further Combinatorial Techniques] How many fixed-point-free nnn -permutations are there (the derangement number DnD_nDn )?
Dn=n!∑r=0n(−1)rr!\displaystyle \boldsymbol{D_n = n! \sum_{r=0}^{n} \frac{(-1)^r}{r!}}Dn=n!r=0∑nr!(−1)r e.g. D3=2D_3 = 2D3=2 , D4=24−24+12−4+1=9D_4 = 24 - 24 + 12 - 4 + 1 = 9D4=24−24+12−4+1=9 .
[Further Combinatorial Techniques] DnD_nDn = the number of fixed-point-free permutations of {1,…,n}\{1, \dots, n\}{1,…,n} =n!∑r=0n(−1)rr!= \displaystyle n! \sum_{r=0}^{n} \frac{(-1)^r}{r!}=n!r=0∑nr!(−1)r .How is this proved by inclusion-exclusion?
With AiA_iAi = the permutations fixing iii : any rrr of the AiA_iAi intersect in (n−r)!(n - r)!(n−r)! permutations, and there are (nr)\binom{n}{r}(rn) ways to choose them. Dn=n!−∣⋃Ai∣=∑r=0n(−1)r(nr)(n−r)!=∑r=0n(−1)rn!r!D_n = n! - \left|\bigcup A_i\right| = \sum_{r=0}^{n} (-1)^r \binom{n}{r} (n-r)! = \sum_{r=0}^{n} (-1)^r \frac{n!}{r!}Dn=n!−∣⋃Ai∣=∑r=0n(−1)r(rn)(n−r)!=∑r=0n(−1)rr!n! .
[Further Combinatorial Techniques] For large nnn , roughly what fraction of all nnn -permutations are fixed-point-free?
1e\boldsymbol{\dfrac{1}{e}}e1 ∑r=0n(−1)rr!→e−1\sum_{r=0}^{n} \frac{(-1)^r}{r!} \to e^{-1}∑r=0nr!(−1)r→e−1 as n→∞n \to \inftyn→∞ .
[Further Combinatorial Techniques] How does the number of ways to write nnn as a sum of odd positive integers compare with the number of ways to write nnn as a sum of different positive integers (order ignored)?
They are equal. e.g. n=6n = 6n=6 : 5+1\ 5+1 5+1 , 3+33+33+3 , 3+1+1+13+1+1+13+1+1+1 , 1+⋯+11+\dots+11+⋯+1 \ vs. 6\ 6 6 , 5+15+15+1 , 4+24+24+2 , 3+2+13+2+13+2+1 .
[Further Combinatorial Techniques] For each nnn : the number of partitions of nnn into odd parts equals the number of partitions of nnn into different parts.How does the proof use inclusion-exclusion? ( p(n)p(n)p(n) is the number of all partitions of nnn .)
Both numbers are p(n)p(n)p(n) minus a union: partitions in which some iii occurs at least twice, resp. in which some even number 2i2i2i occurs. For any i1<⋯<iri_1 < \dots < i_ri1<⋯<ir , both intersections have p ⁣(n−2∑j=1rij)p\!\left(n - 2\sum_{j=1}^{r} i_j\right)p(n−2∑j=1rij) elements, so inclusion-exclusion gives the same result for both.
[Further Combinatorial Techniques] p(m)p(m)p(m) is the number of partitions of mmm . Why do the partitions of nnn in which each of i1,…,iri_1, \dots, i_ri1,…,ir occurs at least twice number p ⁣(n−2∑jij)p\!\left(n - 2\sum_j i_j\right)p(n−2∑jij) , and likewise those in which each of 2i1,…,2ir2i_1, \dots, 2i_r2i1,…,2ir occurs?
Remove two copies of each iji_jij , resp. one copy of each 2ij2i_j2ij : either way 2∑jij2\sum_j i_j2∑jij is removed, and what remains is an arbitrary partition of n−2∑jijn - 2\sum_j i_jn−2∑jij .
[Further Combinatorial Techniques] What does the principle of double counting say about a relation R⊆S×TR \subseteq S \times TR⊆S×T ?
Counting the pairs of RRR by their first or by their second element gives the same number: ∑s∈S∣{t∈T:(s,t)∈R}∣=∑t∈T∣{s∈S:(s,t)∈R}∣\displaystyle\sum_{s \in S} |\{t \in T : (s, t) \in R\}| = \sum_{t \in T} |\{s \in S : (s, t) \in R\}|s∈S∑∣{t∈T:(s,t)∈R}∣=t∈T∑∣{s∈S:(s,t)∈R}∣
[Further Combinatorial Techniques] About how many divisors does a number in {1,…,n}\{1, \dots, n\}{1,…,n} have on average?
About Hn=∑i=1n1iH_n = \sum_{i=1}^{n} \frac{1}{i}Hn=∑i=1ni1 , so Θ(ln⁡n)\Theta(\ln n)Θ(lnn) .
[Further Combinatorial Techniques] How does double counting show that the numbers in {1,…,n}\{1, \dots, n\}{1,…,n} have about Hn=∑i=1n1iH_n = \sum_{i=1}^{n} \frac{1}{i}Hn=∑i=1ni1 divisors on average?
Count the pairs (s,t)(s, t)(s,t) with t∣st \mid st∣s by ttt instead of sss : each ttt divides ⌊n/t⌋\lfloor n/t \rfloor⌊n/t⌋ of the numbers. So the average is 1n∑t=1n⌊nt⌋\frac{1}{n} \sum_{t=1}^{n} \lfloor \frac{n}{t} \rfloorn1∑t=1n⌊tn⌋ , which lies in [Hn−1,Hn][H_n - 1, H_n][Hn−1,Hn] since nt−1<⌊nt⌋≤nt\frac{n}{t} - 1 < \lfloor \frac{n}{t} \rfloor \le \frac{n}{t}tn−1<⌊tn⌋≤tn .
[Further Combinatorial Techniques] GGG is a graph and δG(v)\delta_G(v)δG(v) is the set of edges incident to vvv . How does double counting give ∑v∈V(G)∣δG(v)∣=2∣E(G)∣\sum_{v \in V(G)} |\delta_G(v)| = 2|E(G)|∑v∈V(G)∣δG(v)∣=2∣E(G)∣ ?
Double count the relation v∈ev \in ev∈e between vertices and edges: each edge contains exactly 2 vertices.
[Further Combinatorial Techniques] What is the upper bound on the number of edges of a simple graph on nnn vertices without a cycle of length 4?
⌊n4(1+4n−3)⌋\boldsymbol{\left\lfloor \frac{n}{4} \left(1 + \sqrt{4n - 3}\right) \right\rfloor}⌊4n(1+4n−3)⌋
[Further Combinatorial Techniques] A simple graph GGG on nnn vertices without a cycle of length 4 has at most ⌊n4(1+4n−3)⌋\left\lfloor \frac{n}{4} (1 + \sqrt{4n - 3}) \right\rfloor⌊4n(1+4n−3)⌋ edges.What does the proof double count, and which inequality comes out?
Pairs (vertex uuu , pair {v,w}\{v, w\}{v,w} of neighbors of uuu ): ∑u(deg⁡u2)≤(n2)\displaystyle \sum_{u} \binom{\deg u}{2} \le \binom{n}{2}u∑(2degu)≤(2n) . Counted by {v,w}\{v, w\}{v,w} : each pair has at most one common neighbor, since two common neighbors would form a 4-cycle. ( deg⁡u=∣δG(u)∣\deg u = |\delta_G(u)|degu=∣δG(u)∣ , the number of edges at uuu .)
[Further Combinatorial Techniques] In a graph with nnn vertices and mmm edges, ∑udeg⁡u=2m\sum_u \deg u = 2m∑udegu=2m .Why is ∑u(deg⁡u)2≥4m2n\displaystyle\sum_{u} (\deg u)^2 \ge \frac{4m^2}{n}u∑(degu)2≥n4m2 ?
Write deg⁡u=2mn−α(u)\deg u = \frac{2m}{n} - \alpha(u)degu=n2m−α(u) ; then ∑uα(u)=0\sum_u \alpha(u) = 0∑uα(u)=0 , so ∑u(deg⁡u)2=4m2n+∑uα(u)2\sum_u (\deg u)^2 = \frac{4m^2}{n} + \sum_u \alpha(u)^2∑u(degu)2=n4m2+∑uα(u)2 . The cross term −4mn∑uα(u)-\frac{4m}{n} \sum_u \alpha(u)−n4m∑uα(u) vanishes, and ∑uα(u)2≥0\sum_u \alpha(u)^2 \ge 0∑uα(u)2≥0 .
[Further Combinatorial Techniques] A simple graph with nnn vertices and mmm edges and no 4-cycle satisfies ∑u(deg⁡u2)≤(n2)\sum_u \binom{\deg u}{2} \le \binom{n}{2}∑u(2degu)≤(2n) , and every graph satisfies ∑u(deg⁡u)2≥4m2n\sum_u (\deg u)^2 \ge \frac{4m^2}{n}∑u(degu)2≥n4m2 .How do these give m≤n4(1+4n−3)m \le \frac{n}{4}(1 + \sqrt{4n-3})m≤4n(1+4n−3) ?
The first gives ∑u(deg⁡u)2≤n(n−1)+2m\sum_u (\deg u)^2 \le n(n-1) + 2m∑u(degu)2≤n(n−1)+2m , so 4m2n≤n(n−1)+2m\frac{4m^2}{n} \le n(n-1) + 2mn4m2≤n(n−1)+2m ; solve this quadratic inequality for mmm . 4m2−2nm−n2(n−1)≤04m^2 - 2nm - n^2(n-1) \le 04m2−2nm−n2(n−1)≤0 gives m≤2n+4n2+16n2(n−1)8=n4(1+4n−3)m \le \frac{2n + \sqrt{4n^2 + 16n^2(n-1)}}{8} = \frac{n}{4}\left(1 + \sqrt{4n-3}\right)m≤82n+4n2+16n2(n−1)=4n(1+4n−3) .
[Further Combinatorial Techniques] Generalized pigeonhole principle. NNN is an nnn -set, RRR an rrr -set with n>rn > rn>r , and f:N→Rf : N \to Rf:N→R . What is guaranteed?
Some a∈Ra \in Ra∈R has ∣f−1(a)∣≥⌊n−1r⌋+1|f^{-1}(a)| \ge \lfloor \frac{n-1}{r} \rfloor + 1∣f−1(a)∣≥⌊rn−1⌋+1 . In particular some aaa has ∣f−1(a)∣≥2|f^{-1}(a)| \ge 2∣f−1(a)∣≥2 . Otherwise n=∑a∈R∣f−1(a)∣≤r⌊n−1r⌋≤n−1n = \sum_{a \in R} |f^{-1}(a)| \le r \lfloor \frac{n-1}{r} \rfloor \le n - 1n=∑a∈R∣f−1(a)∣≤r⌊rn−1⌋≤n−1 .
[Further Combinatorial Techniques] a1,…,ana_1, \dots, a_na1,…,an are positive integers. Why is some sum of consecutive terms ak+⋯+ala_k + \dots + a_lak+⋯+al a multiple of nnn ?
The n+1n + 1n+1 prefix sums ∑i=1lai\sum_{i=1}^{l} a_i∑i=1lai ( l=0,…,nl = 0, \dots, nl=0,…,n ) have only nnn possible remainders mod nnn , so two of them agree; their difference is the wanted sum.
[Further Combinatorial Techniques] nnn different numbers a1,…,ana_1, \dots, a_na1,…,an are chosen from {1,…,2n−2}\{1, \dots, 2n - 2\}{1,…,2n−2} . Why is one of them a multiple of another?
Write ai=2kibia_i = 2^{k_i} b_iai=2kibi with bib_ibi odd: only n−1n - 1n−1 odd numbers lie in {1,…,2n−2}\{1, \dots, 2n-2\}{1,…,2n−2} , so two ai,aja_i, a_jai,aj share the odd part, and the one with the larger power of 2 is a multiple of the other.