{"schemaVersion":"proofanvil.formula-drill-faces.v1","courseId":"enumerative-combinatorics","cards":[{"id":"counting-principles/basic-rules/sum-rule","section":"Basic rules","prompt":"

Sum rule

","answer":"

If AAA and BBB are disjoint finite sets, ∣A∪B∣=∣A∣+∣B∣|A \\cup B| = |A| + |B|∣A∪B∣=∣A∣+∣B∣. More generally the size of a disjoint union is the sum of the sizes.

"},{"id":"counting-principles/basic-rules/product-rule","section":"Basic rules","prompt":"

Product rule

","answer":"

If a choice is made in rrr stages and stage jjj always has njn_jnj​ options, whatever was chosen before, there are n1n2⋯nrn_1 n_2 \\cdots n_rn1​n2​⋯nr​ outcomes. In particular ∣A×B∣=∣A∣ ∣B∣|A \\times B| = |A|\\,|B|∣A×B∣=∣A∣∣B∣.

"},{"id":"counting-principles/basic-rules/bijection-principle","section":"Basic rules","prompt":"

Bijection principle

","answer":"

Two finite sets have the same size exactly when there is a bijection between them. To count a set, build a bijection to a set you can already count.

"},{"id":"counting-principles/basic-rules/double-counting","section":"Basic rules","prompt":"

Double counting

","answer":"

Count one set in two different ways and set the answers equal. Most binomial identities have a proof of this kind.

"},{"id":"counting-principles/basic-rules/subsets-of-an-n-set","section":"Basic rules","prompt":"

Subsets of an nnn-set

","answer":"
2n2^n2n

Each element is either in or out: a bijection with words in {0,1}n\\{0,1\\}^n{0,1}n.

"},{"id":"counting-principles/words-functions-and-arrangements/words-of-length-k-over-n-letters","section":"Words, functions and arrangements","prompt":"

Words of length kkk over nnn letters

","answer":"
nkn^knk

The same count as all functions [k]→[n][k] \\to [n][k]→[n].

"},{"id":"counting-principles/words-functions-and-arrangements/falling-factorial","section":"Words, functions and arrangements","prompt":"

Falling factorial

","answer":"
nk‾=n(n−1)⋯(n−k+1)=n!(n−k)!\\begin{gathered} n^{\\underline{k}} = n(n-1)\\cdots(n-k+1) \\\\ = \\frac{n!}{(n-k)!} \\end{gathered}nk​=n(n−1)⋯(n−k+1)=(n−k)!n!​​

Words of length kkk with no repeated letter, or injections [k]→[n][k] \\to [n][k]→[n].

"},{"id":"counting-principles/words-functions-and-arrangements/permutations-of-n","section":"Words, functions and arrangements","prompt":"

Permutations of [n][n][n]

","answer":"
n!n!n!

Bijections [n]→[n][n] \\to [n][n]→[n]. By convention 0!=10! = 10!=1.

"},{"id":"counting-principles/words-functions-and-arrangements/circular-arrangements","section":"Words, functions and arrangements","prompt":"

Circular arrangements

","answer":"
n!n=(n−1)!(n≥1)\\frac{n!}{n} = (n-1)! \\quad (n \\ge 1)nn!​=(n−1)!(n≥1)

Seatings of nnn people around a round table, counted up to rotation.

"},{"id":"counting-principles/pigeonhole-principle/pigeonhole-principle","section":"Pigeonhole principle","prompt":"

Pigeonhole principle

","answer":"

If n+1n+1n+1 objects are placed in nnn boxes, some box holds at least two of them.

"},{"id":"counting-principles/pigeonhole-principle/generalized-pigeonhole","section":"Pigeonhole principle","prompt":"

Generalized pigeonhole

","answer":"
⌈N/k⌉\\left\\lceil N/k \\right\\rceil⌈N/k⌉

If NNN objects are placed in kkk boxes, some box holds at least ⌈N/k⌉\\lceil N/k \\rceil⌈N/k⌉ of them, and some box holds at most ⌊N/k⌋\\lfloor N/k \\rfloor⌊N/k⌋.

"},{"id":"counting-principles/pigeonhole-principle/erdo-s-szekeres-theorem","section":"Pigeonhole principle","prompt":"

Erdős–Szekeres theorem

","answer":"

Every sequence of rs+1rs+1rs+1 distinct real numbers has an increasing subsequence of length r+1r+1r+1 or a decreasing subsequence of length s+1s+1s+1. The bound rs+1rs+1rs+1 cannot be lowered.

"},{"id":"binomial-coefficients/binomial-coefficients/binomial-coefficient","section":"Binomial coefficients","prompt":"

Binomial coefficient

","answer":"
(nk)=n!k! (n−k)!=nk‾k!\\binom{n}{k} = \\frac{n!}{k!\\,(n-k)!} = \\frac{n^{\\underline{k}}}{k!}(kn​)=k!(n−k)!n!​=k!nk​​

The number of kkk-element subsets of an nnn-set; 000 when k<0k<0k<0 or k>nk>nk>n.

"},{"id":"binomial-coefficients/binomial-coefficients/binomial-theorem","section":"Binomial coefficients","prompt":"

Binomial theorem

","answer":"
(x+y)n=∑k=0n(nk)xkyn−k(x+y)^n = \\sum_{k=0}^{n} \\binom{n}{k} x^k y^{n-k}(x+y)n=k=0∑n​(kn​)xkyn−k
"},{"id":"binomial-coefficients/binomial-coefficients/symmetry","section":"Binomial coefficients","prompt":"

Symmetry

","answer":"
(nk)=(nn−k)\\binom{n}{k} = \\binom{n}{n-k}(kn​)=(n−kn​)

Choosing the kkk elements in is choosing the n−kn-kn−k left out.

"},{"id":"binomial-coefficients/binomial-coefficients/pascal-s-rule","section":"Binomial coefficients","prompt":"

Pascal's rule

","answer":"
(nk)=(n−1k−1)+(n−1k)(n≥1)\\binom{n}{k} = \\binom{n-1}{k-1} + \\binom{n-1}{k} \\quad (n \\ge 1)(kn​)=(k−1n−1​)+(kn−1​)(n≥1)

Split on whether element nnn is chosen.

"},{"id":"binomial-coefficients/binomial-coefficients/absorption","section":"Binomial coefficients","prompt":"

Absorption

","answer":"
k(nk)=n(n−1k−1)k\\binom{n}{k} = n\\binom{n-1}{k-1}k(kn​)=n(k−1n−1​)

Count committees of size kkk with a chair.

"},{"id":"binomial-coefficients/binomial-coefficients/row-sums","section":"Binomial coefficients","prompt":"

Row sums

","answer":"
∑k=0n(nk)=2n∑k=0n(−1)k(nk)=0(n≥1)\\begin{gathered} \\sum_{k=0}^{n} \\binom{n}{k} = 2^n \\\\ \\sum_{k=0}^{n} (-1)^k \\binom{n}{k} = 0 \\quad (n \\ge 1) \\end{gathered}k=0∑n​(kn​)=2nk=0∑n​(−1)k(kn​)=0(n≥1)​
"},{"id":"binomial-coefficients/identities/vandermonde-s-identity","section":"Identities","prompt":"

Vandermonde's identity

","answer":"
(m+nk)=∑j=0k(mj)(nk−j)\\binom{m+n}{k} = \\sum_{j=0}^{k} \\binom{m}{j}\\binom{n}{k-j}(km+n​)=j=0∑k​(jm​)(k−jn​)
"},{"id":"binomial-coefficients/identities/sum-of-squares","section":"Identities","prompt":"

Sum of squares

","answer":"
∑k=0n(nk)2=(2nn)\\sum_{k=0}^{n} \\binom{n}{k}^2 = \\binom{2n}{n}k=0∑n​(kn​)2=(n2n​)

Vandermonde with m=nm = nm=n and symmetry.

"},{"id":"binomial-coefficients/identities/hockey-stick","section":"Identities","prompt":"

Hockey stick

","answer":"
∑i=kn(ik)=(n+1k+1)\\sum_{i=k}^{n} \\binom{i}{k} = \\binom{n+1}{k+1}i=k∑n​(ki​)=(k+1n+1​)

Split on the largest element of a (k+1)(k+1)(k+1)-subset of [n+1][n+1][n+1].

"},{"id":"binomial-coefficients/identities/weighted-row-sum","section":"Identities","prompt":"

Weighted row sum

","answer":"
∑k=0nk(nk)=n 2n−1\\sum_{k=0}^{n} k\\binom{n}{k} = n\\,2^{n-1}k=0∑n​k(kn​)=n2n−1
"},{"id":"binomial-coefficients/multinomials-lattice-paths-and-general-exponents/multinomial-coefficient","section":"Multinomials, lattice paths and general exponents","prompt":"

Multinomial coefficient

","answer":"
(nk1,k2,…,km)=n!k1! k2!⋯km!where k1+⋯+km=n\\begin{gathered} \\binom{n}{k_1, k_2, \\ldots, k_m} = \\frac{n!}{k_1!\\,k_2! \\cdots k_m!} \\\\ \\text{where } k_1 + \\cdots + k_m = n \\end{gathered}(k1​,k2​,…,km​n​)=k1​!k2​!⋯km​!n!​where k1​+⋯+km​=n​

Words with kik_iki​ copies of letter iii; for example MISSISSIPPI has 11!1! 4! 4! 2!\\frac{11!}{1!\\,4!\\,4!\\,2!}1!4!4!2!11!​ rearrangements.

"},{"id":"binomial-coefficients/multinomials-lattice-paths-and-general-exponents/multinomial-theorem","section":"Multinomials, lattice paths and general exponents","prompt":"

Multinomial theorem

","answer":"
(x1+⋯+xm)n=∑k1+⋯+km=n(nk1,…,km)x1k1⋯xmkm\\begin{gathered} (x_1 + \\cdots + x_m)^n \\\\ = \\sum_{k_1 + \\cdots + k_m = n} \\binom{n}{k_1, \\ldots, k_m} x_1^{k_1} \\cdots x_m^{k_m} \\end{gathered}(x1​+⋯+xm​)n=k1​+⋯+km​=n∑​(k1​,…,km​n​)x1k1​​⋯xmkm​​​
"},{"id":"binomial-coefficients/multinomials-lattice-paths-and-general-exponents/lattice-paths-from-0-0-to-a-b","section":"Multinomials, lattice paths and general exponents","prompt":"

Lattice paths from (0,0)(0,0)(0,0) to (a,b)(a,b)(a,b)

","answer":"
(a+ba)\\binom{a+b}{a}(aa+b​)

Paths of unit east and north steps: choose which aaa of the a+ba+ba+b steps go east.

"},{"id":"binomial-coefficients/multinomials-lattice-paths-and-general-exponents/generalized-binomial-coefficient","section":"Multinomials, lattice paths and general exponents","prompt":"

Generalized binomial coefficient

","answer":"
(αk)=α(α−1)⋯(α−k+1)k!(1+x)α=∑k≥0(αk)xk\\begin{gathered} \\binom{\\alpha}{k} = \\frac{\\alpha(\\alpha-1)\\cdots(\\alpha-k+1)}{k!} \\\\ (1+x)^{\\alpha} = \\sum_{k \\ge 0} \\binom{\\alpha}{k} x^k \\end{gathered}(kα​)=k!α(α−1)⋯(α−k+1)​(1+x)α=k≥0∑​(kα​)xk​

For any real or complex α\\alphaα, as a formal power series.

"},{"id":"binomial-coefficients/multinomials-lattice-paths-and-general-exponents/negative-exponent","section":"Multinomials, lattice paths and general exponents","prompt":"

Negative exponent

","answer":"
(−nk)=(−1)k(n+k−1k)\\binom{-n}{k} = (-1)^k \\binom{n+k-1}{k}(k−n​)=(−1)k(kn+k−1​)
"},{"id":"compositions-distributions/compositions-and-multisets/composition","section":"Compositions and multisets","prompt":"

Composition

","answer":"

A composition of nnn into kkk parts is an ordered list (a1,…,ak)(a_1, \\ldots, a_k)(a1​,…,ak​) of positive integers with sum nnn. A weak composition allows zero parts.

"},{"id":"compositions-distributions/compositions-and-multisets/compositions-of-n-into-k-parts","section":"Compositions and multisets","prompt":"

Compositions of nnn into kkk parts

","answer":"
(n−1k−1)(n,k≥1)\\binom{n-1}{k-1} \\quad (n, k \\ge 1)(k−1n−1​)(n,k≥1)

Stars and bars: choose k−1k-1k−1 of the n−1n-1n−1 gaps between nnn stars.

"},{"id":"compositions-distributions/compositions-and-multisets/all-compositions-of-n-1","section":"Compositions and multisets","prompt":"

All compositions of n≥1n \\ge 1n≥1

","answer":"
2n−12^{n-1}2n−1
"},{"id":"compositions-distributions/compositions-and-multisets/weak-compositions-of-n-into-k-parts","section":"Compositions and multisets","prompt":"

Weak compositions of nnn into kkk parts

","answer":"
(n+k−1k−1)(k≥1)\\binom{n+k-1}{k-1} \\quad (k \\ge 1)(k−1n+k−1​)(k≥1)

Nonnegative integer solutions of x1+⋯+xk=nx_1 + \\cdots + x_k = nx1​+⋯+xk​=n.

"},{"id":"compositions-distributions/compositions-and-multisets/solutions-with-lower-bounds-x-i-a-i","section":"Compositions and multisets","prompt":"

Solutions with lower bounds xi≥aix_i \\ge a_ixi​≥ai​

","answer":"
(n−∑iai+k−1k−1)\\binom{n - \\sum_i a_i + k - 1}{k-1}(k−1n−∑i​ai​+k−1​)

Integer solutions of x1+⋯+xk=nx_1 + \\cdots + x_k = nx1​+⋯+xk​=n with each xi≥aix_i \\ge a_ixi​≥ai​. Substitute yi=xi−aiy_i = x_i - a_iyi​=xi​−ai​; the count is 000 when ∑iai>n\\sum_i a_i > n∑i​ai​>n.

"},{"id":"compositions-distributions/compositions-and-multisets/multisets","section":"Compositions and multisets","prompt":"

Multisets

","answer":"
( ⁣(nk) ⁣)=(n+k−1k)\\left(\\!\\binom{n}{k}\\!\\right) = \\binom{n+k-1}{k}((kn​))=(kn+k−1​)

kkk-element multisets from an nnn-set: weak compositions of kkk into nnn parts.

"},{"id":"compositions-distributions/the-twelvefold-way-k-balls-into-n-boxes/labeled-balls-labeled-boxes","section":"The twelvefold way: kkk balls into nnn boxes","prompt":"

Labeled balls, labeled boxes

","answer":"
any: nkat most one per box: nk‾no empty box: n! S(k,n)\\begin{gathered} \\text{any: } n^k \\\\ \\text{at most one per box: } n^{\\underline{k}} \\\\ \\text{no empty box: } n!\\,S(k,n) \\end{gathered}any: nkat most one per box: nk​no empty box: n!S(k,n)​

Functions, injections and surjections [k]→[n][k] \\to [n][k]→[n].

"},{"id":"compositions-distributions/the-twelvefold-way-k-balls-into-n-boxes/unlabeled-balls-labeled-boxes","section":"The twelvefold way: kkk balls into nnn boxes","prompt":"

Unlabeled balls, labeled boxes

","answer":"
any: (n+k−1k)at most one per box: (nk)no empty box: (k−1n−1)\\begin{gathered} \\text{any: } \\binom{n+k-1}{k} \\\\ \\text{at most one per box: } \\binom{n}{k} \\\\ \\text{no empty box: } \\binom{k-1}{n-1} \\end{gathered}any: (kn+k−1​)at most one per box: (kn​)no empty box: (n−1k−1​)​
"},{"id":"compositions-distributions/the-twelvefold-way-k-balls-into-n-boxes/labeled-balls-unlabeled-boxes","section":"The twelvefold way: kkk balls into nnn boxes","prompt":"

Labeled balls, unlabeled boxes

","answer":"
any: ∑j=0nS(k,j)at most one per box: [k≤n]no empty box: S(k,n)\\begin{gathered} \\text{any: } \\sum_{j=0}^{n} S(k,j) \\\\ \\text{at most one per box: } [k \\le n] \\\\ \\text{no empty box: } S(k,n) \\end{gathered}any: j=0∑n​S(k,j)at most one per box: [k≤n]no empty box: S(k,n)​

S(k,j)S(k,j)S(k,j) is a Stirling number of the second kind; [k≤n][k \\le n][k≤n] is 111 if k≤nk \\le nk≤n and 000 otherwise.

"},{"id":"compositions-distributions/the-twelvefold-way-k-balls-into-n-boxes/unlabeled-balls-unlabeled-boxes","section":"The twelvefold way: kkk balls into nnn boxes","prompt":"

Unlabeled balls, unlabeled boxes

","answer":"
any: ∑j=0npj(k)at most one per box: [k≤n]no empty box: pn(k)\\begin{gathered} \\text{any: } \\sum_{j=0}^{n} p_j(k) \\\\ \\text{at most one per box: } [k \\le n] \\\\ \\text{no empty box: } p_n(k) \\end{gathered}any: j=0∑n​pj​(k)at most one per box: [k≤n]no empty box: pn​(k)​

pj(k)p_j(k)pj​(k) is the number of partitions of kkk into exactly jjj parts.

"},{"id":"inclusion-exclusion/the-principle/inclusion-exclusion","section":"The principle","prompt":"

Inclusion–exclusion

","answer":"
∣A1∪⋯∪An∣=∑∅≠S⊆[n](−1)∣S∣+1∣AS∣where AS=⋂i∈SAi\\begin{gathered} \\left|A_1 \\cup \\cdots \\cup A_n\\right| \\\\ = \\sum_{\\emptyset \\ne S \\subseteq [n]} (-1)^{|S|+1} \\left|A_S\\right| \\\\ \\text{where } A_S = \\bigcap_{i \\in S} A_i \\end{gathered}∣A1​∪⋯∪An​∣=∅=S⊆[n]∑​(−1)∣S∣+1∣AS​∣where AS​=i∈S⋂​Ai​​
"},{"id":"inclusion-exclusion/the-principle/counting-elements-with-none-of-the-properties","section":"The principle","prompt":"

Counting elements with none of the properties

","answer":"
∣U∖(A1∪⋯∪An)∣=∑S⊆[n](−1)∣S∣∣AS∣where A∅=U\\begin{gathered} \\left|U \\setminus (A_1 \\cup \\cdots \\cup A_n)\\right| \\\\ = \\sum_{S \\subseteq [n]} (-1)^{|S|} \\left|A_S\\right| \\\\ \\text{where } A_\\emptyset = U \\end{gathered}∣U∖(A1​∪⋯∪An​)∣=S⊆[n]∑​(−1)∣S∣∣AS​∣where A∅​=U​
"},{"id":"inclusion-exclusion/the-principle/symmetric-form","section":"The principle","prompt":"

Symmetric form

","answer":"
∑j=0n(−1)j(nj)Nj\\sum_{j=0}^{n} (-1)^j \\binom{n}{j} N_jj=0∑n​(−1)j(jn​)Nj​

When ∣AS∣=Nj|A_S| = N_j∣AS​∣=Nj​ depends only on j=∣S∣j = |S|j=∣S∣, this counts the elements with none of the properties.

"},{"id":"inclusion-exclusion/the-principle/subset-inversion","section":"The principle","prompt":"

Subset inversion

","answer":"
f(T)=∑S⊆Tg(S)  ⟺  g(T)=∑S⊆T(−1)∣T∖S∣f(S)\\begin{gathered} f(T) = \\sum_{S \\subseteq T} g(S) \\\\ \\iff g(T) = \\sum_{S \\subseteq T} (-1)^{|T \\setminus S|} f(S) \\end{gathered}f(T)=S⊆T∑​g(S)⟺g(T)=S⊆T∑​(−1)∣T∖S∣f(S)​

Möbius inversion on the Boolean lattice; inclusion–exclusion is a special case.

"},{"id":"inclusion-exclusion/standard-applications/derangements","section":"Standard applications","prompt":"

Derangements

","answer":"
Dn=n!∑j=0n(−1)jj!D_n = n! \\sum_{j=0}^{n} \\frac{(-1)^j}{j!}Dn​=n!j=0∑n​j!(−1)j​

Permutations of [n][n][n] with no fixed point: D0,…,D6=1,0,1,2,9,44,265D_0, \\ldots, D_6 = 1, 0, 1, 2, 9, 44, 265D0​,…,D6​=1,0,1,2,9,44,265.

"},{"id":"inclusion-exclusion/standard-applications/derangement-recurrences","section":"Standard applications","prompt":"

Derangement recurrences

","answer":"
Dn=(n−1)(Dn−1+Dn−2)(n≥2)Dn=nDn−1+(−1)n(n≥1)\\begin{gathered} D_n = (n-1)(D_{n-1} + D_{n-2}) \\quad (n \\ge 2) \\\\ D_n = n D_{n-1} + (-1)^n \\quad (n \\ge 1) \\end{gathered}Dn​=(n−1)(Dn−1​+Dn−2​)(n≥2)Dn​=nDn−1​+(−1)n(n≥1)​
"},{"id":"inclusion-exclusion/standard-applications/derangements-and-e","section":"Standard applications","prompt":"

Derangements and eee

","answer":"
Dn=⌊n!e+12⌋(n≥1)D_n = \\left\\lfloor \\frac{n!}{e} + \\frac{1}{2} \\right\\rfloor \\quad (n \\ge 1)Dn​=⌊en!​+21​⌋(n≥1)

So a random permutation has no fixed point with probability tending to 1/e1/e1/e.

"},{"id":"inclusion-exclusion/standard-applications/surjections-k-n","section":"Standard applications","prompt":"

Surjections [k]→[n][k] \\to [n][k]→[n]

","answer":"
∑j=0n(−1)j(nj)(n−j)k=n! S(k,n)\\sum_{j=0}^{n} (-1)^j \\binom{n}{j} (n-j)^k = n!\\,S(k,n)j=0∑n​(−1)j(jn​)(n−j)k=n!S(k,n)
"},{"id":"inclusion-exclusion/standard-applications/euler-s-totient","section":"Standard applications","prompt":"

Euler's totient

","answer":"
φ(m)=m∏p∣m(1−1p)\\varphi(m) = m \\prod_{p \\mid m} \\left(1 - \\frac{1}{p}\\right)φ(m)=mp∣m∏​(1−p1​)

Integers in [m][m][m] coprime to mmm; the product runs over the distinct primes dividing mmm.

"},{"id":"set-partitions-permutations/set-partitions/stirling-number-of-the-second-kind","section":"Set partitions","prompt":"

Stirling number of the second kind

","answer":"

S(n,k)S(n,k)S(n,k) is the number of partitions of [n][n][n] into kkk nonempty unlabeled blocks. S(0,0)=1S(0,0) = 1S(0,0)=1 and S(n,0)=0S(n,0) = 0S(n,0)=0 for n≥1n \\ge 1n≥1.

"},{"id":"set-partitions-permutations/set-partitions/recurrence","section":"Set partitions","prompt":"

Recurrence

","answer":"
S(n,k)=S(n−1,k−1)+k S(n−1,k)(n≥1)S(n,k) = S(n-1,k-1) + k\\,S(n-1,k) \\quad (n \\ge 1)S(n,k)=S(n−1,k−1)+kS(n−1,k)(n≥1)

Element nnn is either a block by itself or joins one of kkk blocks.

"},{"id":"set-partitions-permutations/set-partitions/explicit-formula","section":"Set partitions","prompt":"

Explicit formula

","answer":"
S(n,k)=1k!∑j=0k(−1)j(kj)(k−j)nS(n,k) = \\frac{1}{k!} \\sum_{j=0}^{k} (-1)^j \\binom{k}{j} (k-j)^nS(n,k)=k!1​j=0∑k​(−1)j(jk​)(k−j)n

Uses the convention 00=10^0 = 100=1.

"},{"id":"set-partitions-permutations/set-partitions/powers-to-falling-factorials","section":"Set partitions","prompt":"

Powers to falling factorials

","answer":"
xn=∑k=0nS(n,k) xk‾x^n = \\sum_{k=0}^{n} S(n,k)\\, x^{\\underline{k}}xn=k=0∑n​S(n,k)xk​
"},{"id":"set-partitions-permutations/set-partitions/small-cases","section":"Set partitions","prompt":"

Small cases

","answer":"
S(n,2)=2n−1−1(n≥1)S(n,n−1)=(n2)\\begin{gathered} S(n,2) = 2^{n-1} - 1 \\quad (n \\ge 1) \\\\ S(n,n-1) = \\binom{n}{2} \\end{gathered}S(n,2)=2n−1−1(n≥1)S(n,n−1)=(2n​)​
"},{"id":"set-partitions-permutations/set-partitions/bell-numbers","section":"Set partitions","prompt":"

Bell numbers

","answer":"
Bn=∑k=0nS(n,k)Bn+1=∑k=0n(nk)Bk\\begin{gathered} B_n = \\sum_{k=0}^{n} S(n,k) \\\\ B_{n+1} = \\sum_{k=0}^{n} \\binom{n}{k} B_k \\end{gathered}Bn​=k=0∑n​S(n,k)Bn+1​=k=0∑n​(kn​)Bk​​

All partitions of [n][n][n]: B0,…,B6=1,1,2,5,15,52,203B_0, \\ldots, B_6 = 1, 1, 2, 5, 15, 52, 203B0​,…,B6​=1,1,2,5,15,52,203.

"},{"id":"set-partitions-permutations/permutations-and-cycles/stirling-number-of-the-first-kind","section":"Permutations and cycles","prompt":"

Stirling number of the first kind

","answer":"

The unsigned number c(n,k)c(n,k)c(n,k) counts permutations of [n][n][n] with exactly kkk cycles. c(0,0)=1c(0,0) = 1c(0,0)=1 and c(n,0)=0c(n,0) = 0c(n,0)=0 for n≥1n \\ge 1n≥1.

"},{"id":"set-partitions-permutations/permutations-and-cycles/recurrence","section":"Permutations and cycles","prompt":"

Recurrence

","answer":"
c(n,k)=c(n−1,k−1)+(n−1) c(n−1,k)(n≥1)\\begin{gathered} c(n,k) = c(n-1,k-1) \\\\ + (n-1)\\,c(n-1,k) \\quad (n \\ge 1) \\end{gathered}c(n,k)=c(n−1,k−1)+(n−1)c(n−1,k)(n≥1)​

Element nnn is a fixed point, or is inserted after one of the other n−1n-1n−1 elements in its cycle.

"},{"id":"set-partitions-permutations/permutations-and-cycles/rising-factorial","section":"Permutations and cycles","prompt":"

Rising factorial

","answer":"
xn‾=x(x+1)⋯(x+n−1)=∑k=0nc(n,k) xk\\begin{gathered} x^{\\overline{n}} = x(x+1)\\cdots(x+n-1) \\\\ = \\sum_{k=0}^{n} c(n,k)\\, x^k \\end{gathered}xn=x(x+1)⋯(x+n−1)=k=0∑n​c(n,k)xk​
"},{"id":"set-partitions-permutations/permutations-and-cycles/falling-factorial-signed-stirling-numbers","section":"Permutations and cycles","prompt":"

Falling factorial (signed Stirling numbers)

","answer":"
xn‾=x(x−1)⋯(x−n+1)=∑k=0n(−1)n−kc(n,k) xk\\begin{gathered} x^{\\underline{n}} = x(x-1)\\cdots(x-n+1) \\\\ = \\sum_{k=0}^{n} (-1)^{n-k} c(n,k)\\, x^k \\end{gathered}xn​=x(x−1)⋯(x−n+1)=k=0∑n​(−1)n−kc(n,k)xk​

For n≥0n \\ge 0n≥0, with x0‾=1x^{\\underline{0}} = 1x0​=1. The signed numbers s(n,k)=(−1)n−kc(n,k)s(n,k) = (-1)^{n-k} c(n,k)s(n,k)=(−1)n−kc(n,k) invert the S(n,k)S(n,k)S(n,k): ∑kS(n,k) s(k,m)\\sum_{k} S(n,k)\\, s(k,m)∑k​S(n,k)s(k,m) is 111 if n=mn = mn=m and 000 otherwise.

"},{"id":"set-partitions-permutations/permutations-and-cycles/small-cases","section":"Permutations and cycles","prompt":"

Small cases

","answer":"
c(n,1)=(n−1)!(n≥1)c(n,n−1)=(n2)∑kc(n,k)=n!\\begin{gathered} c(n,1) = (n-1)! \\quad (n \\ge 1) \\\\ c(n,n-1) = \\binom{n}{2} \\\\ \\sum_{k} c(n,k) = n! \\end{gathered}c(n,1)=(n−1)!(n≥1)c(n,n−1)=(2n​)k∑​c(n,k)=n!​
"},{"id":"set-partitions-permutations/permutations-and-cycles/permutations-of-a-given-cycle-type","section":"Permutations and cycles","prompt":"

Permutations of a given cycle type

","answer":"
n!∏iimi mi!\\frac{n!}{\\prod_{i} i^{m_i}\\, m_i!}∏i​imi​mi​!n!​

Permutations of [n][n][n] with mim_imi​ cycles of length iii, where ∑ii mi=n\\sum_i i\\,m_i = n∑i​imi​=n.

"},{"id":"set-partitions-permutations/permutations-and-cycles/lah-numbers","section":"Permutations and cycles","prompt":"

Lah numbers

","answer":"
L(n,k)=(n−1k−1)n!k!(n,k≥1)xn‾=∑k=1nL(n,k) xk‾(n≥1)\\begin{gathered} L(n,k) = \\binom{n-1}{k-1}\\frac{n!}{k!} \\quad (n, k \\ge 1) \\\\ x^{\\overline{n}} = \\sum_{k=1}^{n} L(n,k)\\, x^{\\underline{k}} \\quad (n \\ge 1) \\end{gathered}L(n,k)=(k−1n−1​)k!n!​(n,k≥1)xn=k=1∑n​L(n,k)xk​(n≥1)​

Partitions of [n][n][n] into kkk nonempty linearly ordered blocks.

"},{"id":"integer-partitions/partitions-and-ferrers-diagrams/integer-partition","section":"Partitions and Ferrers diagrams","prompt":"

Integer partition

","answer":"

A partition of nnn is a way to write nnn as a sum of positive integers where order does not matter, usually listed as λ1≥λ2≥⋯≥λk\\lambda_1 \\ge \\lambda_2 \\ge \\cdots \\ge \\lambda_kλ1​≥λ2​≥⋯≥λk​. The Ferrers diagram has a row of λi\\lambda_iλi​ dots for each part.

"},{"id":"integer-partitions/partitions-and-ferrers-diagrams/values-of-p-n","section":"Partitions and Ferrers diagrams","prompt":"

Values of p(n)p(n)p(n)

","answer":"
p(1),…,p(10)=1,2,3,5,7,11,15,22,30,42p(1), \\ldots, p(10) = 1, 2, 3, 5, 7, 11, 15, 22, 30, 42p(1),…,p(10)=1,2,3,5,7,11,15,22,30,42

By convention p(0)=1p(0) = 1p(0)=1.

"},{"id":"integer-partitions/partitions-and-ferrers-diagrams/parts-recurrence","section":"Partitions and Ferrers diagrams","prompt":"

Parts recurrence

","answer":"
pk(n)=pk−1(n−1)+pk(n−k)p_k(n) = p_{k-1}(n-1) + p_k(n-k)pk​(n)=pk−1​(n−1)+pk​(n−k)

pk(n)p_k(n)pk​(n) counts partitions of nnn into exactly kkk parts: either a part equals 111, or subtract 111 from every part.

"},{"id":"integer-partitions/partitions-and-ferrers-diagrams/conjugation","section":"Partitions and Ferrers diagrams","prompt":"

Conjugation

","answer":"

Reflecting a Ferrers diagram across its diagonal swaps rows and columns. It is a bijection between partitions of nnn into exactly kkk parts and partitions of nnn with largest part kkk.

"},{"id":"integer-partitions/partitions-and-ferrers-diagrams/self-conjugate-partitions","section":"Partitions and Ferrers diagrams","prompt":"

Self-conjugate partitions

","answer":"

The partitions of nnn equal to their own conjugate are equinumerous with the partitions of nnn into distinct odd parts, by unrolling each diagonal hook.

"},{"id":"integer-partitions/generating-functions-for-partitions/all-partitions","section":"Generating functions for partitions","prompt":"

All partitions

","answer":"
∑n≥0p(n) xn=∏i≥111−xi\\sum_{n \\ge 0} p(n)\\, x^n = \\prod_{i \\ge 1} \\frac{1}{1-x^i}n≥0∑​p(n)xn=i≥1∏​1−xi1​
"},{"id":"integer-partitions/generating-functions-for-partitions/parts-at-most-k","section":"Generating functions for partitions","prompt":"

Parts at most kkk

","answer":"
∑n≥0p≤k(n) xn=∏i=1k11−xi\\sum_{n \\ge 0} p_{\\le k}(n)\\, x^n = \\prod_{i=1}^{k} \\frac{1}{1-x^i}n≥0∑​p≤k​(n)xn=i=1∏k​1−xi1​

p≤k(n)p_{\\le k}(n)p≤k​(n) counts partitions of nnn with every part at most kkk (k≥1k \\ge 1k≥1); by conjugation it also counts partitions of nnn into at most kkk parts.

"},{"id":"integer-partitions/generating-functions-for-partitions/euler-distinct-parts-equal-odd-parts","section":"Generating functions for partitions","prompt":"

Euler: distinct parts equal odd parts

","answer":"
∏i≥1(1+xi)=∏i≥111−x2i−1\\prod_{i \\ge 1} (1 + x^i) = \\prod_{i \\ge 1} \\frac{1}{1 - x^{2i-1}}i≥1∏​(1+xi)=i≥1∏​1−x2i−11​
"},{"id":"integer-partitions/generating-functions-for-partitions/pentagonal-number-theorem","section":"Generating functions for partitions","prompt":"

Pentagonal number theorem

","answer":"
∏i≥1(1−xi)=∑j=−∞∞(−1)jxj(3j−1)/2\\prod_{i \\ge 1} (1 - x^i) = \\sum_{j = -\\infty}^{\\infty} (-1)^j x^{j(3j-1)/2}i≥1∏​(1−xi)=j=−∞∑∞​(−1)jxj(3j−1)/2
"},{"id":"integer-partitions/generating-functions-for-partitions/recurrence-for-p-n","section":"Generating functions for partitions","prompt":"

Recurrence for p(n)p(n)p(n)

","answer":"
p(n)=∑j≠0(−1)j+1 p ⁣(n−j(3j−1)2)(n≥1)=p(n−1)+p(n−2)−p(n−5)−⋯\\begin{gathered} p(n) = \\sum_{j \\ne 0} (-1)^{j+1}\\, p\\!\\left(n - \\tfrac{j(3j-1)}{2}\\right) \\quad (n \\ge 1) \\\\ = p(n-1) + p(n-2) - p(n-5) - \\cdots \\end{gathered}p(n)=j=0∑​(−1)j+1p(n−2j(3j−1)​)(n≥1)=p(n−1)+p(n−2)−p(n−5)−⋯​

Terms with a negative argument are 000, and p(0)=1p(0) = 1p(0)=1.

"},{"id":"integer-partitions/generating-functions-for-partitions/partitions-inside-an-a-b-box","section":"Generating functions for partitions","prompt":"

Partitions inside an a×ba \\times ba×b box

","answer":"
∑λ⊆a×bq∣λ∣=(a+ba) ⁣q=∏i=1a1−qb+i1−qi\\begin{gathered} \\sum_{\\lambda \\subseteq a \\times b} q^{|\\lambda|} = \\binom{a+b}{a}_{\\!q} \\\\ = \\prod_{i=1}^{a} \\frac{1 - q^{b+i}}{1 - q^{i}} \\end{gathered}λ⊆a×b∑​q∣λ∣=(aa+b​)q​=i=1∏a​1−qi1−qb+i​​

At most aaa parts, each at most bbb. At q=1q = 1q=1 this is (a+ba)\\binom{a+b}{a}(aa+b​), the lattice paths tracing the boundary.

"},{"id":"generating-functions/ordinary-generating-functions/ordinary-generating-function","section":"Ordinary generating functions","prompt":"

Ordinary generating function

","answer":"

The OGF of (an)n≥0(a_n)_{n \\ge 0}(an​)n≥0​ is the formal power series A(x)=∑n≥0anxnA(x) = \\sum_{n \\ge 0} a_n x^nA(x)=∑n≥0​an​xn. The notation [xn]A(x)[x^n]A(x)[xn]A(x) means the coefficient ana_nan​.

"},{"id":"generating-functions/ordinary-generating-functions/product-is-convolution","section":"Ordinary generating functions","prompt":"

Product is convolution

","answer":"
[xn] A(x)B(x)=∑k=0nakbn−k[x^n]\\, A(x)B(x) = \\sum_{k=0}^{n} a_k b_{n-k}[xn]A(x)B(x)=k=0∑n​ak​bn−k​

Counts pairs of structures whose sizes add to nnn.

"},{"id":"generating-functions/ordinary-generating-functions/partial-sums-and-derivatives","section":"Ordinary generating functions","prompt":"

Partial sums and derivatives

","answer":"
A(x)1−x=∑n(∑k≤nak)xnxA′(x)=∑nn anxn\\begin{gathered} \\frac{A(x)}{1-x} = \\sum_{n} \\Big(\\sum_{k \\le n} a_k\\Big) x^n \\\\ xA'(x) = \\sum_{n} n\\,a_n x^n \\end{gathered}1−xA(x)​=n∑​(k≤n∑​ak​)xnxA′(x)=n∑​nan​xn​
"},{"id":"generating-functions/ordinary-generating-functions/geometric-series-and-its-powers","section":"Ordinary generating functions","prompt":"

Geometric series and its powers

","answer":"
11−x=∑n≥0xn1(1−x)k=∑n≥0(n+k−1k−1)xn(k≥1)\\begin{gathered} \\frac{1}{1-x} = \\sum_{n \\ge 0} x^n \\\\ \\frac{1}{(1-x)^k} = \\sum_{n \\ge 0} \\binom{n+k-1}{k-1} x^n \\quad (k \\ge 1) \\end{gathered}1−x1​=n≥0∑​xn(1−x)k1​=n≥0∑​(k−1n+k−1​)xn(k≥1)​
"},{"id":"generating-functions/ordinary-generating-functions/sequences-of-a-class","section":"Ordinary generating functions","prompt":"

Sequences of a class

","answer":"
11−B(x)=∑m≥0B(x)m\\frac{1}{1 - B(x)} = \\sum_{m \\ge 0} B(x)^m1−B(x)1​=m≥0∑​B(x)m

Ordered lists of any length of objects counted by BBB, when B(0)=0B(0) = 0B(0)=0.

"},{"id":"generating-functions/recurrences/fibonacci-numbers","section":"Recurrences","prompt":"

Fibonacci numbers

","answer":"
∑n≥0Fnxn=x1−x−x2Fn=ϕn−ψn5,ϕ,ψ=1±52\\begin{gathered} \\sum_{n \\ge 0} F_n x^n = \\frac{x}{1 - x - x^2} \\\\ F_n = \\frac{\\phi^n - \\psi^n}{\\sqrt{5}}, \\quad \\phi, \\psi = \\frac{1 \\pm \\sqrt{5}}{2} \\end{gathered}n≥0∑​Fn​xn=1−x−x2x​Fn​=5​ϕn−ψn​,ϕ,ψ=21±5​​​

F0=0F_0 = 0F0​=0, F1=1F_1 = 1F1​=1, Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}Fn​=Fn−1​+Fn−2​.

"},{"id":"generating-functions/recurrences/linear-recurrences","section":"Recurrences","prompt":"

Linear recurrences

","answer":"

If an=c1an−1+⋯+cdan−da_n = c_1 a_{n-1} + \\cdots + c_d a_{n-d}an​=c1​an−1​+⋯+cd​an−d​ for all n≥dn \\ge dn≥d, then A(x)=P(x)/(1−c1x−⋯−cdxd)A(x) = P(x)/(1 - c_1 x - \\cdots - c_d x^d)A(x)=P(x)/(1−c1​x−⋯−cd​xd) with deg⁡P<d\\deg P < ddegP<d. When cd≠0c_d \\ne 0cd​=0 and 1−c1x−⋯−cdxd=∏i=1d(1−rix)1 - c_1 x - \\cdots - c_d x^d = \\prod_{i=1}^{d} (1 - r_i x)1−c1​x−⋯−cd​xd=∏i=1d​(1−ri​x) with distinct rir_iri​, partial fractions give an=∑iαirina_n = \\sum_i \\alpha_i r_i^nan​=∑i​αi​rin​.

"},{"id":"generating-functions/catalan-numbers/catalan-numbers","section":"Catalan numbers","prompt":"

Catalan numbers

","answer":"
Cn=1n+1(2nn)=(2nn)−(2nn+1)C_n = \\frac{1}{n+1}\\binom{2n}{n} = \\binom{2n}{n} - \\binom{2n}{n+1}Cn​=n+11​(n2n​)=(n2n​)−(n+12n​)

C0,…,C6=1,1,2,5,14,42,132C_0, \\ldots, C_6 = 1, 1, 2, 5, 14, 42, 132C0​,…,C6​=1,1,2,5,14,42,132. The difference form is the reflection principle.

"},{"id":"generating-functions/catalan-numbers/recurrence-and-generating-function","section":"Catalan numbers","prompt":"

Recurrence and generating function

","answer":"
Cn+1=∑k=0nCkCn−kC(x)=∑n≥0Cnxn=1−1−4x2x\\begin{gathered} C_{n+1} = \\sum_{k=0}^{n} C_k C_{n-k} \\\\ C(x) = \\sum_{n \\ge 0} C_n x^n = \\frac{1 - \\sqrt{1 - 4x}}{2x} \\end{gathered}Cn+1​=k=0∑n​Ck​Cn−k​C(x)=n≥0∑​Cn​xn=2x1−1−4x​​​

From C(x)=1+x C(x)2C(x) = 1 + x\\,C(x)^2C(x)=1+xC(x)2.

"},{"id":"generating-functions/catalan-numbers/what-c-n-counts","section":"Catalan numbers","prompt":"

What CnC_nCn​ counts

","answer":"

Dyck paths of length 2n2n2n (up and down steps that never go below the axis), balanced strings of nnn pairs of parentheses, rooted ordered full binary trees with nnn internal nodes (every internal node has exactly two children), and triangulations of a convex (n+2)(n+2)(n+2)-gon.

"},{"id":"exponential-generating-functions/exponential-generating-functions/exponential-generating-function","section":"Exponential generating functions","prompt":"

Exponential generating function

","answer":"

The EGF of (an)n≥0(a_n)_{n \\ge 0}(an​)n≥0​ is A^(x)=∑n≥0anxnn!\\hat{A}(x) = \\sum_{n \\ge 0} a_n \\frac{x^n}{n!}A^(x)=∑n≥0​an​n!xn​. It suits labeled structures, where the nnn atoms carry the labels 1,…,n1, \\ldots, n1,…,n.

"},{"id":"exponential-generating-functions/exponential-generating-functions/product-is-the-labeled-product","section":"Exponential generating functions","prompt":"

Product is the labeled product

","answer":"
n! [xn] A^(x)B^(x)=∑k=0n(nk)akbn−kn!\\,[x^n]\\, \\hat{A}(x)\\hat{B}(x) = \\sum_{k=0}^{n} \\binom{n}{k} a_k b_{n-k}n![xn]A^(x)B^(x)=k=0∑n​(kn​)ak​bn−k​

Split the labels into the kkk used by the first structure and the rest.

"},{"id":"exponential-generating-functions/exponential-generating-functions/exponential-formula","section":"Exponential generating functions","prompt":"

Exponential formula

","answer":"
G^(x)=exp⁡ ⁣(C^(x))\\hat{G}(x) = \\exp\\!\\big(\\hat{C}(x)\\big)G^(x)=exp(C^(x))

If every structure is a set of connected labeled components counted by C^\\hat{C}C^ (with c0=0c_0 = 0c0​=0), then all structures are counted by exp⁡(C^)\\exp(\\hat{C})exp(C^).

"},{"id":"exponential-generating-functions/exponential-generating-functions/sets-lists-and-cycles","section":"Exponential generating functions","prompt":"

Sets, lists and cycles

","answer":"
sets: expermutations: 11−xcycles: log⁡11−x\\begin{gathered} \\text{sets: } e^x \\\\ \\text{permutations: } \\frac{1}{1-x} \\\\ \\text{cycles: } \\log\\frac{1}{1-x} \\end{gathered}sets: expermutations: 1−x1​cycles: log1−x1​​

The EGFs of sets (an=1a_n = 1an​=1), permutations (an=n!a_n = n!an​=n!) and cyclic orders (an=(n−1)!a_n = (n-1)!an​=(n−1)! for n≥1n \\ge 1n≥1).

"},{"id":"exponential-generating-functions/standard-egfs/set-partitions","section":"Standard EGFs","prompt":"

Set partitions

","answer":"
∑nS(n,k)xnn!=(ex−1)kk!∑nBnxnn!=eex−1\\begin{gathered} \\sum_{n} S(n,k)\\frac{x^n}{n!} = \\frac{(e^x - 1)^k}{k!} \\\\ \\sum_{n} B_n \\frac{x^n}{n!} = e^{e^x - 1} \\end{gathered}n∑​S(n,k)n!xn​=k!(ex−1)k​n∑​Bn​n!xn​=eex−1​
"},{"id":"exponential-generating-functions/standard-egfs/permutations-by-cycles","section":"Standard EGFs","prompt":"

Permutations by cycles

","answer":"
∑n,kc(n,k) ykxnn!=(1−x)−y\\sum_{n,k} c(n,k)\\, y^k \\frac{x^n}{n!} = (1-x)^{-y}n,k∑​c(n,k)ykn!xn​=(1−x)−y
"},{"id":"exponential-generating-functions/standard-egfs/derangements","section":"Standard EGFs","prompt":"

Derangements

","answer":"
∑nDnxnn!=e−x1−x\\sum_{n} D_n \\frac{x^n}{n!} = \\frac{e^{-x}}{1-x}n∑​Dn​n!xn​=1−xe−x​
"},{"id":"exponential-generating-functions/standard-egfs/involutions","section":"Standard EGFs","prompt":"

Involutions

","answer":"
∑nInxnn!=ex+x2/2\\sum_{n} I_n \\frac{x^n}{n!} = e^{x + x^2/2}n∑​In​n!xn​=ex+x2/2

InI_nIn​ counts permutations with σ2=id\\sigma^2 = \\mathrm{id}σ2=id: cycles of length 111 or 222.

"},{"id":"exponential-generating-functions/standard-egfs/ordered-set-partitions","section":"Standard EGFs","prompt":"

Ordered set partitions

","answer":"
∑n(∑kk! S(n,k))xnn!=12−ex\\sum_{n} \\Big(\\sum_{k} k!\\,S(n,k)\\Big) \\frac{x^n}{n!} = \\frac{1}{2 - e^x}n∑​(k∑​k!S(n,k))n!xn​=2−ex1​

Sequences of nonempty blocks, the Fubini numbers.

"},{"id":"exponential-generating-functions/trees-and-lagrange-inversion/cayley-s-formula","section":"Trees and Lagrange inversion","prompt":"

Cayley's formula

","answer":"
nn−2n^{n-2}nn−2

Labeled trees on n≥1n \\ge 1n≥1 vertices; Prüfer codes give the bijection.

"},{"id":"exponential-generating-functions/trees-and-lagrange-inversion/rooted-labeled-trees","section":"Trees and Lagrange inversion","prompt":"

Rooted labeled trees

","answer":"
T(x)=x eT(x)n! [xn] T(x)=nn−1\\begin{gathered} T(x) = x\\, e^{T(x)} \\\\ n!\\,[x^n]\\,T(x) = n^{n-1} \\end{gathered}T(x)=xeT(x)n![xn]T(x)=nn−1​
"},{"id":"exponential-generating-functions/trees-and-lagrange-inversion/lagrange-inversion","section":"Trees and Lagrange inversion","prompt":"

Lagrange inversion

","answer":"
T(x)=x φ(T(x))  ⟹  [xn] T(x)k=kn [tn−k] φ(t)n\\begin{gathered} T(x) = x\\,\\varphi\\big(T(x)\\big) \\\\ \\implies [x^n]\\, T(x)^k = \\frac{k}{n}\\, [t^{n-k}]\\, \\varphi(t)^n \\end{gathered}T(x)=xφ(T(x))⟹[xn]T(x)k=nk​[tn−k]φ(t)n​

For φ(0)≠0\\varphi(0) \\ne 0φ(0)=0 and 1≤k≤n1 \\le k \\le n1≤k≤n. With φ(t)=(1+t)2\\varphi(t) = (1+t)^2φ(t)=(1+t)2 it gives the Catalan numbers.

"}]}