Combinatorics
A Review
D. Zack Garza
University of Georgiadzackgarza@gmail.com
Last updated: 2020-10-24
Last updated: 2020-10-24
Note that the theory is important for Combinatorics – knowing what definitions are and what various expressions count – but it is a very problem-driven subject. It is worth delineating exactly what kinds of problems are tractable, and which are more difficult and require more subtle methods. However, the ultimate skill in this course is to know when to apply which tool to a given problem, how to translate problems into things you know how to count, and how to seamlessly move back and forth between various combinatorial interpretations.
Problems are the best practice!
\(\left\{{a, b, c, \cdots}\right\} = \left\{{b, c, a, \cdots}\right\} = \left\{{c, b, a, \cdots}\right\} = \cdots\) is a set, a structure which contains some finite number of unique elements, and there is a-priori notion of “order” or an indexing operation (i.e. there is no distinguished “first” element, etc).
If \(S\) is a set, then \(\# S\) denotes the size of the set, i.e. a count of the number of elements contained in \(S\).
\([a, b, c] \neq [b, c, a]\) is an ordered list (also called a \(k{\hbox{-}}\)tuple), a structure of not-necessarily unique elements from some set in which there is a well-defined order/indexing operation.
For any given \(n\), there is essentially one set of size \(n\), the set \([n] = \left\{{1,2,\cdots n}\right\}\). It is a theorem that every set admits a well-ordering, and a consequence of this is that any set \(S\) of countable size \(n\) admits a bijective map \(S \to [n]\). So \(S \cong [n]\) in the category of Sets, “up to relabeling” of elements.
But be careful! \([n]\) comes with its own labeling and its own ordering \(1 \leq 2 \leq \cdots\), and so should perhaps be regarded as an ordered list with unique elements instead. As a set, we can order the elements any way and obtain the same set.
\(S_n\) denotes the symmetric group on \(n\) elements; each element of this group is a bijective function \([n]\to[n]\). Combinatorialists really love this group, and it secretly shows up in most counting problems.
A permutation \(\sigma\) is an element of \(S_n\), We can specify a bijection by describing where it sends every element, so for example, define \[\begin{align*}\begin{aligned} \sigma: [5] &\to [5] &\\ \\ \sigma(1) &= 3 \implies &1 \mapsto 3 \\ \sigma(2) &= 4 \implies &2 \mapsto 4 \\ \sigma(3) &= 5 \implies &3 \mapsto 5 \\ \sigma(4) &= 2 \implies &4 \mapsto 2 \\ \sigma(5) &= 1 \implies &5 \mapsto 1 \\ \end{aligned}\end{align*}\] There are several more concise notations equivalent to the above specification:
Write \(1\cdots n\), and under each number, write where it is sent to under \(\sigma\): \[\begin{align*} \left( \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 2 & 1 \end{array}\right) \end{align*}\] In general, we write \[\begin{align*} \left( \begin{array}{cccc} 1 & 2 & \cdots & n \\ \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{array}\right) \end{align*}\]
Noting that in the above notation, we’ll always write \(1\cdots n\) in the top row, we can just omit it and implicitly agree that the \(k{\hbox{-}}\)th position denotes where the integer \(k\) is mapped to: \[\begin{align*} [3,4,5,2,1] = 34521 \end{align*}\]
In general, we write a concatenated list of numbers \[\begin{align*} \sigma(1)\sigma(2) \cdots \sigma(n) \end{align*}\]
Since \(S_n\) is a finite group, we know that every element will have finite order. So for some given number \(i\), we can look at the iterates \(\sigma(i), \sigma^2(i) = \sigma(\sigma(i)), \sigma^3(i), \cdots\) and there will be some \(k\) for which \(\sigma^k(i) = i\). This sequence of images is called a cycle, and it turns out that we can recover our permutation entirely from exhaustively recording the cycles.
The algorithm: start with \(1\), then compute all \(\sigma^i(1)\). Write the resulting numbers in parentheses, then take the smallest number you haven’t seen yet, open a new parenthesis, and repeat until all numbers \(1 \cdots n\) appear somewhere. Finally, if any set of parentheses contains only a single number (so \(\sigma(i) = i\) after only 1 iteration), omit it.
Our example: \[\begin{align*} (1,3,5)(2,4) \end{align*}\] which reads as “1 maps to 3, 3 maps to 5, 5 maps to 1” and “2 maps to 4, 4 maps to 2”.
In general, we write \[\begin{align*} (1, \sigma(1), \sigma^2(1), \cdots, \sigma^{k}(1))~(a_1, \sigma(a_1), \sigma^2(a_1), \cdots, \sigma^{k_1}(a_1)) ~ \cdots \end{align*}\]
Observations/notes:
We can count the number of bijections from an \(n\) element set to itself: \[\begin{align*} \#\left\{{\text{Permutations of } [n]}\right\} = {\left\lvert {S_n} \right\rvert} = n! \end{align*}\]
If \(\#\Sigma = k\) is some set (which we’ll regard as “formal symbols”), we can count the number of ordered lists: \[\begin{align*} \# \left\{{\text{Length $k$ lists over $\Sigma$}}\right\} = n^k \end{align*}\]
Let \[\begin{align*}\begin{aligned} n^{\underline k} &\mathrel{\vcenter{:}}=\prod_{i=0}^{k-1}(n - i) \\ &= n(n-1)\cdots (n-k+1) \\ &= \frac{n!}{(n-k)!} \end{aligned}\end{align*}\] be the falling factorial, which is a product with exactly \(n\) terms.
Let \[\begin{align*}\begin{aligned} n^{\overline k} &\mathrel{\vcenter{:}}=\prod_{i=0}^{k-1}(n+i) \\ &=n(n+1) \cdots (n+k-1) \\&= \frac{(n+k-1)!}{(n-1)!} \\ \\&= (n+k-1)^{\underline k} \end{aligned}\end{align*}\] be the rising factorial, which is a product with exactly \(n\) terms.
Counts the number of ways to form a \(k{\hbox{-}}\)element subset of a set of \(n\) items: \[\begin{align*} \begin{aligned} \#\left\{{k{\hbox{-}}\text{element subsets of } [n]}\right\} = {n \choose k} &\mathrel{\vcenter{:}}=\frac{n!}{k!(n-k!)} \\ &= {n \choose n-k} \\ \\ &= \frac{n^{\underline k}}{k!} \end{aligned} \end{align*}\]
We can extend the “choose” notation and thus the binomial formula to rational powers by defining \[\begin{align*} {r \choose k} = \frac{1}{k!} \prod_{i=0}^{k-1} (r - i) = \frac{r(r-1)(r-2)\cdots(r-k+1)}{k!}\\ (x+y)^r = \sum_{k\geq 0} {r\choose k} x^ky^{n-k} \end{align*}\]
Note that this allows us to expand things such as \(\sqrt{x+y} = (x+y)^\frac{1}{2}\) in an infinite sum: \[\begin{align*} \sqrt { 1 + x } = 1 + \frac { 1 } { 2 } x - \frac { 1 } { 8 } x ^ { 2 } + \frac { 1 } { 16 } x ^ { 3 } - \frac { 5 } { 128 } x ^ { 4 } + \frac { 7 } { 256 } x ^ { 5 } - \cdots \end{align*}\]
We can thus count the number of \(k{\hbox{-}}\)element multisets of an \(n{\hbox{-}}\)element set: \[\begin{align*}\begin{aligned} \#\left\{{\text{Multisets of $[n]$ of size $k$} }\right\} &= \left(\!\!{n\choose k}\!\!\right) \\ &\mathrel{\vcenter{:}}={{n+k-1}\choose k} \\ &= {{n+k-1}\choose n-1} \\ \\ &= \frac{n^{\overline k}}{k!} \end{aligned}\end{align*}\]
Multisets can be put in bijection with unrestricted stars and bars arrangements, see next section.
Consider the problem of counting the number of \(n\times n\) lattice paths that don’t go above the diagonal. Since every such path has to have a “first hitting time” for the diagonal, we can enumerate these using a recurrence relation. Let \(C_n\) be the number of such paths. If the first hit occurs on the \(k\)th diagonal, then there were \(C_k\) paths leading there and \(C_{n-k}\) paths to the top-right corner. This yields \[\begin{align*} C_{n+1} = \sum_{i=0}^n C_i C_{n-i} \end{align*}\] and using generating functions, it can be shown that \[\begin{align*} C_n = \frac{1}{n+1}{2n \choose n} \end{align*}\]
A useful conceptual counting problem, as many other problems can be encoded as some version of this. The idea is we have an alphabet \(\Sigma = \left\{{\star, \mathrel{\Big|}}\right\}\) (“star” and “bar”), and we’d like to form certain words containing exactly \(n\) copies of \(\star\) and \(k\) copies of \(\mathrel{\Big|}\).
There are two variants: we’ll say a configuration of stars and bars is strict if a bar does not occur as the first or last symbol, and there are no two adjacent bars.
This can be counted as \[\begin{align*} \#\left\{{\text{strict configurations of $n$ stars and $k-1$ bars}}\right\} = {n-1 \choose k-1} \end{align*}\]
Lay out \(n\) stars, which have \(n-1\) gaps between them. From these gaps, choose any \(k-1\) of them (without replacement) to contain bars.
With no restrictions of the configuration, we can count \[\begin{align*} \#\left\{{\text{unrestricted configurations of $n$ stars and $k-1$ bars}}\right\} = {n+k-1 \choose k-1} \end{align*}\]
Since we just need to form an arbitrary word from \(n\) stars and \(k-1\) bars, simply place \(n + (k-1)\) blanks, choose \(k-1\) of them (without replacement) to be bars, and place stars everywhere else.
We can give an alternative proof:
Lay out \(n\) stars, then from the \(n-1\) gaps, choose \(k-1\) gaps with replacement to contain bars. This can be done in \(\left(\!\!{n-1 \choose k-1}\!\!\right) = {n+k-1 \choose k-1}\) ways.
Some remarks:
For a given \(n\), consider permutations \(\sigma \in S_n\). It can be written as a product of disjoint cycles in cycle notation, so one can ask how many permutations have exactly \(k\) disjoint cycles. In other words, we have \[\begin{align*} \sigma = \overbrace{(a_1b_1\cdots)(a_2b_2\cdots)\cdots(a_kb_k\cdots)}^{k \text{ cycles}} \in S_n \end{align*}\] in cycle notation, where we include cycles of length 1 (i.e. fixed points). We can thus count \[\begin{align*} \#\left\{{\text{permutations of $[n]$ with exactly $k$ disjoint cycles}}\right\} \mathrel{\vcenter{:}}= c(n, k) = \genfrac{[}{]}{0pt}{}{n}{k} \end{align*}\] the unsigned Stirling number of the first kind.
In other applications, there is a signed Stirling number of the first kind which are related by \[\begin{align*} s(n, k) \mathrel{\vcenter{:}}=(-1)^{n-k}c(n, k), \quad {\left\lvert {s(n,k)} \right\rvert} = c(n, k) \end{align*}\] These yield the coefficients of \(x^n\) in the falling factorial \(x^{\underline n} = x(x-1)\cdots(x-n+1)\).
There isn’t a particularly nice closed form expression for \(c(n, k)\), so the main computational tool is the following recurrence relation they satisfy: \[\begin{align*} \genfrac{[}{]}{0pt}{}{n}{k} = (n-1){\genfrac{[}{]}{0pt}{}{n-1}{k}} + \genfrac{[}{]}{0pt}{}{n-1}{k-1} \end{align*}\]
Either \(n\) is a fixed point (i.e. in a cycle by itself) or it is not.
If \(n\) is a fixed point, we can delete the cycle \((n)\) from \(\sigma\) to obtain a permutation of \([n-1]\) with \(k-1\) cycles. Conversely, we can lift any permutation of \([n-1]\) with \(k-1\) cycles to a permutation of \([n]\) by just adding the cycle \((n)\), which can only be done in one way, yielding the second term
Otherwise, \(n\) appears in a cycle with other elements. We can delete it to obtain a permutation of \([n-1]\) which still has \(k\) cycles; conversely, given such a permutation, consider the operation of multiplying \(\sigma\) by the transposition \((n~i)\) where \(1\leq i\leq n-1\). This has the effect of inserting \(n\) into the cycle containing \(i\), and in fact puts it right before \(i\), i.e. \[\begin{align*} (a_1 a_2 \cdots a_{k}~ i ~ a_{k+1} \cdots a_m)(n~i) = (a_1 a_2 \cdots a_{k}~ n ~ i ~ a_{k+1} \cdots a_m). \end{align*}\] There are exactly \(n-1\) choices for \(i\), and each one yields a way to insert \(n\) into an existing cycle, yielding the first term.
A set partition of \([n]\) into \(k\) parts is a collection \(S_1, S_2, \cdots S_k\) where
We can then count \[\begin{align*} \#\left\{{\text{Set partitions of $[n]$ into $k$ parts}}\right\} \mathrel{\vcenter{:}}= S(n, k) = \genfrac\{\}{0pt}{}{n}{k}, \end{align*}\] which is referred to as the Stirling number of the second kind. Although there is a closed-form formula for it, it is not particularly nice – the primary method of computing it comes from a recurrence relation it satisfies: \[\begin{align*} \genfrac\{\}{0pt}{}{n}{k} = k\genfrac\{\}{0pt}{}{n-1}{k} + \genfrac\{\}{0pt}{}{n-1}{k-1} \end{align*}\]
The following proof illustrates a valuable technique: :::{.proof} When forming a set partition of \([n]\) into \(k\) parts, there are two disjoint cases: either \(n\) is in a singleton set, or it is not.
If \(n\) a singleton, throw that part away. What remains is a partition of \(n-1\) into \(k-1\) parts. Conversely, given any partition of \(n-1\) into \(k-1\) parts, we can add the part \(\left\{{n}\right\}\) to obtain a partition of \(n\) into \(k\) parts where \(n\) is a singleton. This yields the second term.
If it is not, \(n\) is some \(S_i\) with at least 1 other element. Letting \(S'_i = S_i - \left\{{n}\right\} \neq \emptyset\) we get a partition of \(n-1\) into \(k\) parts. Conversely, given any partition of \(n-1\) into \(k\) parts, we can form a partition of \(n\) into \(k\) parts where \(n\) is not a singleton by adding \(n\) to any part. Note that there are \(k\) choices for which part to add \(n\) to, yielding the first term. :::
In general, a composition is a way of writing \(n\) as a sum of positive integers, i.e. \(n = a_1 + a_2 + \cdots\) where \(a_i \in {\mathbb{Z}}\). There are infinitely many of these, so to count anything, we need to place various restrictions:
A composition of \(n\) into \(k\) parts is an ordered list \([a_1, a_2, \cdots a_k]\) such that \(\sum_{i=1}^k a_i = n\) and for each \(i\) we have \(0 < a_i \leq n\). Note that we do not allow any \(a_i\) to be zero now.
These can be counted as \[\begin{align*} \mathrm{comp}(n, k) = \#\left\{{\text{compositions of $n$ into $k$ parts}}\right\} = \left(\!\!{n+1 \choose k-1}\!\!\right) = {n+k-1 \choose k} \end{align*}\] where \(\left(\!\!{a \choose b}\!\!\right)\) is the multinomial coefficient. This follows from by a bijection with strict stars and bars configurations. Note that distinct lists yields distinct compositions.
A weak composition of \(n\) into \(k\) parts is an ordered list \([a_1, a_2, \cdots a_k]\) such that \(\sum_{i=1}^k a_i = n\) and for each \(i\) we have \(0 \leq a_i \leq n\). (Note that we allow some \(a_i\) to be zero.)
These can be counted as \[\begin{align*} \mathrm{comp}_W(n, k) = \#\left\{{\text{weak compositions of $n$ into $k$ parts}}\right\} = {n-1 \choose n-k}, \end{align*}\] which follows from a bijection with unrestricted stars and bars configurations. Note that distinct lists yields distinct compositions.
An integer partition of \(n\) into \(k\) parts is a strong composition of \(n\) into \(k\) parts where we identify any compositions that differ by a permutation of of parts. In other words, it is a set of integers \([a_1, a_2, \cdots a_k]\) such that \(\sum_{i=1}^k a_i = n\) and for each \(i\), we have \(1 \leq a_i \leq n\).
Example: The strong compositions of 4 are
from sage.all import *
print(sorted(list(Compositions(4)), key=len))\[\begin{align*} \left[\text{\texttt{[4]}}, \text{\texttt{[1,{ }3]}}, \text{\texttt{[2,{ }2]}}, \text{\texttt{[3,{ }1]}}, \text{\texttt{[1,{ }1,{ }2]}}, \text{\texttt{[1,{ }2,{ }1]}}, \text{\texttt{[2,{ }1,{ }1]}}, \text{\texttt{[1,{ }1,{ }1,{ }1]}}\right] .\end{align*}\]
while the integer partitions are
from sage.all import *
print(sorted(list(Partitions(4)), key=len))\[\begin{align*} \left[{\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}} \raisebox{-.6ex}{$\begin{array}[b]{*{4}c}\cline{1-4} \lr{\phantom{x}}&\lr{\phantom{x}}&\lr{\phantom{x}}&\lr{\phantom{x}}\\\cline{1-4} \end{array}$} }, {\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}} \raisebox{-.6ex}{$\begin{array}[b]{*{3}c}\cline{1-3} \lr{\phantom{x}}&\lr{\phantom{x}}&\lr{\phantom{x}}\\\cline{1-3} \lr{\phantom{x}}\\\cline{1-1} \end{array}$} }, {\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}} \raisebox{-.6ex}{$\begin{array}[b]{*{2}c}\cline{1-2} \lr{\phantom{x}}&\lr{\phantom{x}}\\\cline{1-2} \lr{\phantom{x}}&\lr{\phantom{x}}\\\cline{1-2} \end{array}$} }, {\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}} \raisebox{-.6ex}{$\begin{array}[b]{*{2}c}\cline{1-2} \lr{\phantom{x}}&\lr{\phantom{x}}\\\cline{1-2} \lr{\phantom{x}}\\\cline{1-1} \lr{\phantom{x}}\\\cline{1-1} \end{array}$} }, {\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}} \raisebox{-.6ex}{$\begin{array}[b]{*{1}c}\cline{1-1} \lr{\phantom{x}}\\\cline{1-1} \lr{\phantom{x}}\\\cline{1-1} \lr{\phantom{x}}\\\cline{1-1} \lr{\phantom{x}}\\\cline{1-1} \end{array}$} }\right] .\end{align*}\]
Note that \([3,1]\) and \([1,3]\) are distinct as compositions of 4 into 2 parts, but are identified as partitions of 4 into 2 parts.
These are generally difficult to count, but we can define \[\begin{align*}\begin{aligned} \# \left\{{\text{Integer partitions of $n$ into $k$ parts}}\right\} &\mathrel{\vcenter{:}}= p(n, k) \\ \# \left\{{\text{Integer partitions of $n$ into any number of parts}}\right\} &\mathrel{\vcenter{:}}= p(n). \end{aligned}\end{align*}\]
Integer partitions are in bijective correspondence with Ferrer’s diagrams, which provide many useful ways of extracting information via diagram operations. The most important operation is conjugation, which is flipping a diagram about its main diagonal. This operation can be used to prove the following bijections between types of integer partitions:
\[\begin{align*}\begin{aligned} \#\left\{{\text{Exactly $k$ parts}}\right\} &= \#\left\{{\text{Largest part $= k$}}\right\}\\ \#\left\{{\text{Any number of parts, where every part is $\leq k$}}\right\} &= \#\left\{{\text{At most $k$ parts}}\right\} \\ \#\left\{{\text{Any number of distinct, odd parts}}\right\} &= \#\left\{{\text{Self-conjugate partitions}}\right\} \end{aligned}\end{align*}\]
Usually given or put in the form of \(a_n = f(a_{n-1}, a_{n-2}, \cdots)\)
The secret sauce:
| Sequence | OGF | Sum |
|---|---|---|
| \([1, 1, 1, \cdots]\) | \(\frac 1 {1-x}\) | \(\displaystyle\sum_{n\geq 0}1x^n\) |
| \([1, -1, 1, \cdots]\) | \(\frac 1 {1+x}\) | \(\displaystyle\sum_{n\geq 0}(-1)^nx^n\) |
| \([r, r^2, r^3, \cdots]\) | \(\frac 1 {1-rx}\) | \(\displaystyle\sum_{n\geq 0}r^nx^n\) |
| \([1, 0, 1, \cdots]\) | \(\frac 1 {1-x^2}\) | \(\displaystyle\sum_{n\geq 0}1x^{2n}\) |
| \([1, 0, 0, 1, \cdots]\) | \(\frac 1 {1-x^3}\) | \(\displaystyle\sum_{n\geq 0}1x^{3n}\) |
| \([1, 2, 3, 4, \cdots]\) | \({\frac{\partial }{\partial x}\,}\frac 1 {1-x} = \left(\frac{1}{1-x}\right)^2\) | \(\displaystyle\sum_{n\geq 0}(n+1)x^{n}\) |
| \([0, 1, 2, 3, \cdots]\) | \(x{\frac{\partial }{\partial x}\,}\frac 1 {1-x} = x\left(\frac{1}{1-x}\right)^2\) | \(\displaystyle\sum_{n\geq 0}nx^{n}\) |
| \([1,{c \choose 1}, {c \choose 2}, \cdots]\) | \((1+x)^c\) | \(\displaystyle\sum_{n\geq 0}{c \choose n}x^n\) |
| \([1, {c+1 \choose 1}, {c+2 \choose 2}, \cdots]\) | \(\left( \frac 1 {1-x} \right)^c\) | \(\displaystyle\sum_{n \geq 0}{n+c \choose n} x^n\) |
| \([0,\cdots 0, {c \choose c}, {c+1 \choose c}, \cdots]\) | \(x^c \left(\frac{1}{1-x}\right)^{c+1}\) | \(\displaystyle\sum_{n\geq c}{n \choose c}x^n\) |
| \([1, A(x), A(x)^2, \cdots ]\) | \(\frac {1}{1-A(x)}\) | \(\displaystyle\sum_{n\geq 0} A(x)^n {x^n}\) |
| \([\sum_{i=0}^0 a_i, \sum_{i=0}^1 a_i, \sum_{i=0}^2 a_i, \cdots ]\) | \(\frac{A(x)}{1-x}\) | \(\displaystyle\sum_{n\geq 0} \left(\sum_{i=0}^n a_n\right) \frac{x^n}{n!}\) |
| Sequence | EGF | Sum |
|---|---|---|
| \([1, 1, 1, \cdots]\) | \(e^x\) | \(\displaystyle\sum_{n\geq 0}1 \frac {x^n} {n!}\) |
| \([r, r^2, r^3, \cdots]\) | \(e^{rx}\) | \(\displaystyle\sum_{n\geq 0}r^n\frac {x^n} {n!}\) |
| \([1, 0, 1, \cdots]\) | \(\cosh(x)\) | \(\displaystyle\sum_{n\geq 0}1 \frac {x^{2n}} {n!}\) |
| \([1, 0, 0, 1, \cdots]\) | \(?\) | \(\displaystyle\sum_{n \geq 0} 1\frac{x^{2n}}{(2n)!}\) |
| \([0, 1, 2, 3, \cdots]\) | \(xe^x\) | \(\displaystyle\sum_{n\geq 1}n \frac {x^n} {n!}\) |
| \([1,{c \choose 1}, {c \choose 2}, \cdots]\) | \((1+x)^c\) | \(\displaystyle\sum_{n\geq 0}{c \choose n}\frac {x^n} {n!}\) |
| \([0,\cdots 0, {c \choose c}, {c+1 \choose c}, \cdots]\) | \(x^c \left(\frac{1}{1-x}\right)^{c+1}\) | \(\displaystyle\sum_{n\geq c}{n \choose c}\frac {x^n} {n!}\) |
| \([1, {c+1 \choose 1}, {c+2 \choose 2}, \cdots]\) | \(\left( \frac 1 {1-x} \right)^c\) | \(\displaystyle\sum_{n \geq 0}{n+c \choose n} \frac {x^n} {n!}\) |
| \([0, 0!, 1!, 2!, \cdots ]\) | \(\ln \frac{1}{1-x}\) | \(\displaystyle\sum_{n \geq 0}(n-1)! \frac{x^n}{n!}\) |
| \([1, A(x), A(x)^2, \cdots ]\) | \(e^{A(x)}\) | \(\displaystyle\sum_{n\geq 0} A(x)^n \frac{x^n}{n!}\) |
| Sequence \(a_n = \cdots\) | OGF | EGF |
|---|---|---|
| \(\indic{n=k}\) | \(x^k\) | \(\frac{x^k}{k!}\) |
| \(\indic{n \geq 0} ({\mathbb{N}})\) | \(\frac 1 {1-x}\) | \(e^x\) |
| \(\indic{n \geq 1} ({\mathbb{N}}_{\geq 1})\) | \(\frac x {1-x}\) | \(e^x - 1\) |
| \(\indic{n \geq 2} ({\mathbb{N}}_{\geq 2})\) | \(\frac {x^2} {1-x}\) | \(e^x - 1 - x\) |
| \(\indic{n \geq k}\) | \(\frac {x^k} {1-x}\) | \(e^x - \displaystyle\sum_{n=0}^k \frac{x^n}{n!} =\displaystyle\sum_{n=k+1}^\infty \frac{x^n}{n!}\) |
| \(\indic{n \leq k}\) | \(1+x+x^2+\cdots +x^k\) | \(1 + x + \frac{x^2}{2} + \cdots +\frac{x^k}{k!}\) |
| \(\indic{n\text{ even}}\) | \(\frac{1}{1-x^2}\) | \(\cosh(x)\) |
| \(\indic{n\text{ odd}}\) | \(\frac{x}{1-x^2}\) | \(\sinh(x)\) |
| \(\indic{n = k, k^2, \cdots}\) | \(\frac 1 {1-x^k}\) | \(e^{kx}\) |
| \({n \choose c}\) | \(x^c \left(\frac{1}{1-x}\right)^{c+1}\) | \(\frac{1}{c!}x^ce^x\) |
| \({n+c \choose n}\) | \(??\) | \(\left( \frac 1 {1-x} \right)^c\) |
| \({c \choose n}\) | \(?\) | \((1+x)^c\) |
| \(n!\) | \(\emptyset\) | \(\frac{1}{1-x}\) |
A linear ordered partition of \([n]\) (say, into 2 blocks) is a set partition \[\begin{align*}[n] = S_1 {\coprod}S_2\end{align*}\] where \[\begin{align*}x\in S_1 \implies \forall y\in S_2, x \leq y.\end{align*}\] In other words, \(S_1 = [1, 2, \cdots, m]\) and \(S_2 = [m+1, m+2, \cdots, n]\). The linear part denotes the inequality, while the ordered part denotes the fact that we are labeling the \(S_i\) with ordered numbers, choosing which \(S_i\) to call “1”, “2”, and so on.
An arbitrary ordered partition of \([n]\) (again into 2 parts) is a set partition as above, where we no longer require the inequality. The ordered portion again denotes the labels on the \(S_i\), so we have \([S_1, S_2] \neq [S_2, S_1]\) and distinguish these as ordered partitions.
| OGF Operation | Effect | Sum |
|---|---|---|
| \(xA(x)\) | Right shift | \(\displaystyle\sum_{n\geq 0}a_{n} x^{n+1} = \displaystyle\sum_{n\geq 1}a_{n-1} x^{n}\) |
| \(x^{-1}(A(x) - a_0)\) | Left shift | \(\displaystyle\sum_{n\geq 0}a_{n+1} x^{n}\) |
| \({\frac{\partial }{\partial x}\,}A(x)\) | Multiply by index, then left shift | \(\displaystyle\sum_{n\geq 1}n a_n x^{n-1} = \displaystyle\sum_{n\geq 0}(n+1) a_{n+1}x^n\) |
| \(x{\frac{\partial }{\partial x}\,}A(x)\) | Multiply by index | \(\displaystyle\sum_{n\geq 0}n a_n x^n\) |
| \(\displaystyle\int A(x)\) | Divide by index, then right shift | \(\displaystyle\sum_{n\geq 0}\frac 1 {n+1} a^{n}x^{n+1} = \displaystyle\sum_{n\geq 1}\frac 1 n a_{n-1} x^{n}\) |
| \(\displaystyle\int x^{-1}(A(x) - a_0)\) | Divide by index | \(\displaystyle\sum_{n\geq 1} \frac{1}{n} a_n x^n\) |
| \(C(x) = A(x)B(x)\) | Convolution / Sum over ways to split into 2 linear parts | \(\displaystyle\sum_{n\geq 0} \left( \displaystyle\sum_{i+j=n} a_i b_j\right)x^n\) |
| \(D(x) = A(x)B(x)C(x)\) | Convolution / Sum over ways to split into 3 linear parts | \(\displaystyle\sum_{n\geq 0} \left( \displaystyle\sum_{i+j+k=n} a_i b_j c_k\right) {x^n}\) |
| \(F(x) = A(B(x))\) | Partition into any number of linearly ordered blocks, put a \(B\) structure within each block, and an \(A\) structure on the collection of blocks | \(\displaystyle\sum_{n\geq 0} a_n {\left( \displaystyle\sum_{m\geq 0} b_m \frac{x^m}{m!}\right)^n}\) |
| EGF Operation | Effect | Sum |
|---|---|---|
| \(xA(x)\) | Index multiply, then right shift | \(\displaystyle\sum_{n\geq 0}a_{n} \frac{x^{n+1}}{n!} = \displaystyle\sum_{n\geq 1}n a_{n-1} \frac{x^n}{n!}\) |
| \(x^{-1}(A(x) - a_0)\) | Index divide, then left shift | \(\displaystyle\sum_{n\geq 0}a_{n+1} \frac{x^n}{n!}\) |
| \({\frac{\partial }{\partial x}\,}A(x)\) | Left shift | \(\displaystyle\sum_{n\geq 1}n a_n \frac{x^{n-1}}{n!} = \displaystyle\sum_{n\geq 0}a_{n+1} \frac{x^n}{n!}\) |
| \(\displaystyle\int A(x)\) | Right shift | \(\displaystyle\sum_{n\geq 0}\frac {a^{n}} {n+1} \frac{x^{n+1}}{n!} = \displaystyle\sum_{n\geq 1} a_{n-1} \frac{x^n}{n!}\) |
| \(x{\frac{\partial }{\partial x}\,}A(x)\) | Index multiply | \(\displaystyle\sum_{n\geq 0}n a_{n} \frac{x^n}{n!}\) |
| \(\displaystyle\int x^{-1}(A(x) - a_0)?\) | Index divide | \(\displaystyle\sum_{n\geq 1} \frac{a_n}{n} \frac{x^n}{n!}\) |
| \(C(x) = A(x)B(x)\) | Convolution / Sum over ways to split into 2 arbitrary blocks | \(\displaystyle\sum_{n\geq 0} \left( \displaystyle\sum_{i+j=n} a_i b_j\right) \frac{x^n}{n!}\) |
| \(D(x) = A(x)B(x)C(x)\) | Convolution / Sum over ways to split into 3 arbitrary blocks | \(\displaystyle\sum_{n\geq 0} \left( \displaystyle\sum_{i+j+k=n} a_i b_j c_k\right) \frac{x^n}{n!}\) |
| \(F(x) = A(B(x))\) | Partition into any number of ordered blocks, put a \(B\) structure within each block, and an \(A\) structure on the collection of blocks | \(\displaystyle\sum_{n\geq 0} a_n {\left( \displaystyle\sum_{m\geq 0} b_m \frac{x^m}{m!}\right)^n}\frac{1}{n!}\) |
| Operation | OGF | EGF |
|---|---|---|
| Right Shift | \(xA(x)\) | \(\displaystyle\int_0^x A(x)\) |
| Left Shift | \(x^{-1}(A(x) - a_0)\) | \({\frac{\partial }{\partial x}\,} A(x)\) |
| Index Multiply | \(x{\frac{\partial }{\partial x}\,}A(x)\) | \(A(x)\) |
| Index Divide | \(\displaystyle\int_0^x x^{-1}(A(x) - a_0)\) | |
| \(A(x)B(x)\) | 2 linearly ordered blocks, \(A{\hbox{-}}\)structure on block 1, \(B{\hbox{-}}\)structure on block 2 | 2 arbitrary ordered blocks, \(A{\hbox{-}}\)structure on block 1, \(B{\hbox{-}}\)structure on block 2 |
| \(A(x)B(x)C(x)\) | 3 linearly ordered blocks, \(A{\hbox{-}}\)structure on block 1, \(B{\hbox{-}}\)structure on block 2, \(C{\hbox{-}}\)structure on block 3 | 3 arbitrary ordered blocks, \(A{\hbox{-}}\)structure on block 1, \(B{\hbox{-}}\)structure on block 2, \(C{\hbox{-}}\)structure on block 3 |
| \(\displaystyle \prod_{i=1}^k A_i(x)\) | \(k\) linearly ordered blocks, an \(A_i\) structure on block \(i\) | \(k\) arbitrary ordered blocks, an \(A_i\) structure on block \(i\) |
| \(A(x)^k\) | \(k\) linearly ordered blocks, an \(A\) structure on every block | \(k\) arbitrary ordered blocks, an \(A\) structure on every block |
| \(\displaystyle\sum_{i=1}^\infty A(x)^i = A(x) + A(x)^2 + \cdots\) | Any # of linearly ordered blocks, an \(A\) structure on every block | Any # of ordered blocks, an \(A\) structure on every block |
| \(B(A(x))\) | Any # of linearly ordered blocks, \(A{\hbox{-}}\)structure on each block, \(B{\hbox{-}}\)structure on collection of blocks | Any # of arbitrary ordered blocks, an \(A{\hbox{-}}\)structure on each block, \(B{\hbox{-}}\)structure on collection of blocks |
Note that
| Structure | Sequence | OGF | EGF |
|---|---|---|---|
| Be exactly \(n\) | \([0, 0, \cdots 0, 1, 0, \cdots]\) | \(x^n\) | \(\frac {x^n} {n!}\) |
| Be a natural number \(\geq 0\) | \([1,1,1,\cdots]\) | \(\frac 1 {1-x}\) | \(e^x\) |
| Be a natural number \(\geq 1\) | \([0,1,1,\cdots]\) | \(\frac x {1-x}\) | \(e^x - 1\) |
| Be an even number | \([1,0,1,0\cdots]\) | \(\frac 1 {1-x^2}\) | \(\cosh(x)\) |
| Be an odd positive number | \([0,1,0,1,\cdots]\) | \(\frac x {1-x^2}\) | \(\sinh(x)\) |
| Be an odd number or zero | \([1,1,0,1,\cdots]\) | \(\frac x {1-x^2} + 1\) | \(\sinh(x)+1\) |
| Be an even positive number | \([0,0,1,0\cdots]\) | \(\frac 1 {1-x^2} - 1\) | \(\cosh(x) - 1\) |
| Be a multiple of \(k\) | \([1,0,\cdots 0,1,0,\cdots]\) | \(\frac 1 {1-x^k}\) | \(1 + \frac{x^k}{k!} + \frac{x^{2k}}{(2k)!} + \cdots\) |
Note
\[\begin{align*}\begin{aligned} \sum_{n\geq 0} \genfrac\{\}{0pt}{}{n}{k} x^n &= \frac{x^k}{(1-x)(1-2x)\cdots(1-kx)} =& x^k\prod_{i=1}^k \frac 1 {1-ix} \\ \sum_{n\geq 0} k! \genfrac\{\}{0pt}{}{n}{k} \frac{x^n}{n!} &= (e^x-1)(e^x-1)\cdots(e^x-1) =& (e^x-1)^k \\ \sum_{n\geq 0} \#\left\{{\text{${\mathbb{N}}$ Partitions}}\right\} x^n &= \frac{1}{(1-x)(1-x^2)(1-x^3)\cdots} =& \prod_{i=1}^\infty \frac 1 {1-x^i} \\ \sum_{n\geq 0} \#\left\{{\text{${\mathbb{N}}$ Partitions, only odd parts}}\right\} x^n &= \frac{1}{(1-x)(1-x^3)(1-x^5)\cdots} =& \prod_{i=1}^\infty \frac{1}{1-x^{2i-1}} \\ \sum_{n\geq 0} \#\left\{{\text{${\mathbb{N}}$ Partitions, only even parts}}\right\} x^n &= \frac{1}{(1-x^2)(1-x^4)(1-x^6)\cdots} =& \prod_{i=1}^\infty \frac{1}{1-x^{2i}} \\ \sum_{n\geq 0} \#\left\{{\text{${\mathbb{N}}$ Partitions, distinct parts}}\right\} x^n &= {(1+x)(1+x^2)(1+x^3)\cdots} =& \prod_{i=1}^{\infty} {1+x^i} \\ \sum_{n\geq 0} \#\left\{{\text{${\mathbb{N}}$ Partitions, \# parts $\leq k$}}\right\} x^n &= \frac{1}{(1-x)(1-x^2)\cdots(1-x^k)} =& \prod_{i=1}^{k} \frac 1 {1-x^i} &\\ \sum_{n\geq 0} \#\left\{{\text{${\mathbb{N}}$ Partitions, largest part $= k$}}\right\} x^n &= \frac{x^k}{(1-x)(1-x^2)\cdots(1-x^k)} =& \frac{x^k}{1-x^k}\prod_{i=1}^{k-1} \frac 1 {1-x^i} \\ \ \end{aligned} \end{align*}\]
Note that conjugation is useful for obtaining equivalent formulas involve \(p(n, k)\).
A poset (partially-ordered set) is a pair \((S, \preceq)\) where \(\preceq\) is a relation on \(S\) that is
Notice that this behaves very much like \(({\mathbb{Z}}, \leq)\), so we’ll often used \(\leq\) to denote the relation. However, there is an important distinction – there may be incomparable elements, i.e. pairs \(a,b \in S\) such that neither \(a\leq b\) or \(b\leq a\) holds. This is why the order is “partial”. Also note that it makes sense in this setting to write things like \(a< b\), which just means \(a\leq b\) and \(a\neq b\).
If every two elements are comparable, \(\preceq\) is called total order and \((S, \preceq)\) is called a chain.
Weakening this condition slightly, if for every two elements \(x,y\in S\) there exists some \(s\in S\) such that \(s\leq x\) and \(s \leq y\), we say \(S\) is a directed poset.
An open section of a poset is defined as \[\begin{align*}S_\alpha = \left\{{s \in S {~\mathrel{\Big|}~}s < \alpha}\right\}.\end{align*}\] A closed section is defined as \[\begin{align*}\overline{S_\alpha} = \left\{{s \in S {~\mathrel{\Big|}~}s \leq \alpha}\right\}.\end{align*}\] The complement of a section is given by \[\begin{align*} S_x^c = \left\{{s\in S {~\mathrel{\Big|}~}s \geq a}\right\} \\ \overline{S_x}^c = \left\{{s\in S {~\mathrel{\Big|}~}s > a}\right\} \end{align*}\]
We can define the notions of an open interval from \(\alpha\) to \(\beta\), closed interval, and half-open intervals respectively: \[\begin{align*} (\alpha, \beta) &\mathrel{\vcenter{:}}=\left\{{s\in S {~\mathrel{\Big|}~}\alpha < s < \beta}\right\}\\ [\alpha, \beta] &\mathrel{\vcenter{:}}=\left\{{s\in S {~\mathrel{\Big|}~}\alpha \leq s \leq \beta}\right\}\\ (\alpha, \beta] &\mathrel{\vcenter{:}}=\left\{{s\in S {~\mathrel{\Big|}~}\alpha < s \leq \beta}\right\}\\ [\alpha, \beta) &\mathrel{\vcenter{:}}=\left\{{s\in S {~\mathrel{\Big|}~}\alpha \leq s < \beta}\right\}. \end{align*}\]
We say that \(y\) covers \(x\) if \[\begin{align*} x \in S_y \text{ (so $x < y$) and } (x,y) = \emptyset. \end{align*}\] In other words, this says that \(y\) is a least upper bound for \(x\).
If \(S_x = \emptyset\), \(x\) is said to be a minimal element. Similarly, if \(\overline{S_y} = S\), \(y\) is said to be a maximal element.
In a subtle distinction, if \(x \in S_s\) for every \(s\in S\), then \(x\) is unique and is said to be the minimum element and denoted \(\mathbf 0\). Similarly, if \(S_y = S-\left\{{y}\right\}\), then \(y\) is said to be a (not necessarily unique) maximal element and is denoted \(\mathbf 1\).
A Hasse diagram for a poset \((S, \leq)\) is an graph obtained by letting the verticies of \(G\) be the elements of \(S\), connecting a directed edge from \(x\to y\) iff \(y\) covers \(x\), arranging this graph so all arrows point upwards and incomparable elements are lined up horizontally.
These are generally written without vertex labels or edge directions, yielding an undirected graph on \(\# S\) vertices.
\((D(12), \mathrel{\Big|})\): the divisors of 12 ordered by divisibility
\((\mathcal{P}([n]), \subseteq)\): Subsets of \([3]\) ordered by inclusion.
A subset of a poset \(U \subseteq S\) is called an upper set if it “absorbs” everything above it with respect to the partial order, i.e. \[\begin{align*} u\in U \implies \forall s\in S, \quad s \geq u \implies s \in U, \end{align*}\]
or in other words, \(\overline{S_u^c} \subseteq U\)
and similarly, \(L\) is called a lower set if it absorbs everything below it: \[\begin{align*} l \in L \implies \forall s\in S, \quad s \leq u \implies s \in U \end{align*}\] so \(\overline{S_u} \subseteq L\)
A subset \(L \subseteq S\) is an order ideal if it is a non-empty directed lower set.
Given any poset, we can define the incidence algebra \[\begin{align*} {\mathbb{A}}(P) = \left\{{f: P \times P \to {\mathbb{R}}{~\mathrel{\Big|}~}f(x,y) = 0 \iff x \not\leq y }\right\}, \end{align*}\] which are all of the functions on pairs of elements in the poset that take some values on comparable elements and are just zero otherwise.
This is an algebra because it is a vector space over \({\mathbb{R}}\), and has a bilinear product: \[\begin{align*} (f \ast g)(x, y) = \sum_{t\in[x,y]}f(x,t) g(t, y) \end{align*}\]
Under this product,
Moreover, if \(f(x,x) \neq 0\), then \(f^{-1}\) exists such that \(f\ast f^{-1} = \delta\), so we can define \(\mu = \zeta^{-1}\), which can be shown has the formula \[\begin{align*} \mu(x,y) = (-1)\sum_{ t \in [x,y)}\zeta(x, t) \end{align*}\] One thus computes this function inductively up a Hasse diagram.
Compute the Mobius function for each element of the divisibility poset of \(n=90\).
Note that from the above calculation, we find that for the divisibility poset, \[\begin{align*} \mu(a, b) = \begin{cases} (-1)^k & \frac b a \text{ is a product of k distinct primes} \\ 0 & \text{otherwise} \end{cases} \end{align*}\]
In general, there is a Mobius inversion formula: \[\begin{align*} g ( x ) = \sum _ { x y \leq \pi } f ( y ) \quad \forall x \in P \quad \Longleftrightarrow \quad f ( x ) = \sum _ { x y \leq \pi } \mu ( y , x ) g ( y ) \quad \forall x \in P \end{align*}\]
which says that if we know that \(g\) on every element and we also know that it’s some linear combination of values of \(f\) (where we don’t necessarily know what any single \(f(x)\) is), we can actually solve for a single \(f(x)\) and write it as a (weighted) linear combination of values of \(g\).
If we write the incidence matrix of the poset as \(A\), this equivalently says \[\begin{align*} g(\mathbf{x}) = A f(\mathbf{x}) \implies f(\mathbf{x}) = A^{-1}g(\mathbf{x}) = Mg(\mathbf{x}) \end{align*}\]
where \(M = [\mu(x_i, x_j)]\) is the “Gram matrix” of values of the Mobius function.
Some notes on lists:
Bonus: It can be shown using ordinary generating functions that \[\begin{align*} \genfrac{[}{]}{0pt}{}{n}{k} = \frac { 1 } { k ! } \ln ^ { k } \left( \frac { 1 } { 1 - z } \right). \end{align*}\]
Bonus: a closed formula for the Stirling numbers of the second kind is given by \[\begin{align*} \genfrac\{\}{0pt}{}{n}{k} = \sum _ { i = 0 } ^ { k } \frac { ( - 1 ) ^ { k - i } } { k ! } \left( \begin{array} { l } { k } \\ { i } \end{array} \right) i ^ { n }, \end{align*}\] which can be found by using the recurrence to solve for an ordinary generating function, then using partial fraction decomposition and some gnarly algebraic manipulations. With a bit more work, you can show \[\begin{align*} \sum_k \genfrac\{\}{0pt}{}{n}{k} = \frac 1 e \sum_{i=0}^\infty \frac{i^n}{i!}. \end{align*}\]
| \([n]\) labeled? | \([k]\) labeled? | \([n] \to [k]\) | \([n] \hookrightarrow[k]\) | \([n] \twoheadrightarrow[k]\) |
|---|---|---|---|---|
| Yes | Yes | \(k^n\) | \(\begin{cases}n^{\underline k} & n \leq k \\ 0 & n > k \end{cases}\) | \(\begin{cases}k!~S(n,k) & k \leq n \\ 0 & k > n \end{cases}\) |
| No | Yes | \(\left(\!\!{k\choose n}\!\!\right) = \frac {k^{\overline n}} {k!}\) | \(\begin{cases}{k\choose n} & n \leq k\\ ~0 & n > k\end{cases}\) | \(\begin{cases} \mathrm{comp}_W(n, k) & k \leq n \\ 0 & k > n \end{cases}\) |
| Yes | No | \(\sum_{i=1}^k S(n, i)\) | \(\begin{cases}1 & n \leq k \\ 0 & n > k \end{cases}\) | \(\begin{cases}S(n,k) & k \leq n \\ 0 & k > n \end{cases}\) |
| No | No | \(\sum_{i=1}^k p_i(n)\) | \(\begin{cases}1 & n \leq k \\ 0 & n > k \end{cases}\) | \(\begin{cases}p_k(n) & k \leq n \\ 0 & k > n \end{cases}\) |
Some Interpretations:
When doing combinatorial problems, it’s often useful to have a “dictionary” in mind: some go-to interpretations of what any given combinatorial quantity might signify. These are particularly useful when you’d like to prove identities by counting both sides in different ways.
\[\begin{align*} n! &\qquad \text{Strings of length $n$ over an alphabet of size $n$ with no duplicates,}\\ &\qquad \text{Ways to arrange $n$ distinct objects in a line, or}\\ &\qquad \text{Number of functions $[n] \to [n]$ that are injective and surjective}\\ &\qquad \text{Ways to place $n$ labeled balls into $n$ labeled bins, each bin has $\leq 1$ ball}\\ n^{\underline k} = n(n-1)\cdots(n-k+1) &\qquad \text{Strings of length $k$ over an alphabet of size $n$ with no duplicates, or} \\ &\qquad \text{}\\ \end{align*}\]