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!



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.

The Symmetric Group

\(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:

Two line notation

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*}\]

One line notation

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*}\]

Cycle Notation

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*}\]


Useful facts about the Symmetric group


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*}\]

Ordered Lists

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*}\]

Falling Factorial

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.

Rising Factorial

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.

Combinations/Binomial Coefficients

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*}\]

Generalized Binomial Coefficients

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.

Catalan Numbers

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*}\]

Stars and Bars

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.

Variant 1: Strict

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.

Variant 2: Unrestricted

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:

Stirling Numbers of the First Kind

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.

Stirling Numbers of the Second Kind

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.


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:

Strong Compositions

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.

Weak 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.

Integer Partitions

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*}\]

Generating Functions

Solving Recurrences

Usually given or put in the form of \(a_n = f(a_{n-1}, a_{n-2}, \cdots)\)

The secret sauce:

  1. Declare your generating function \(A(x) = \displaystyle\sum_{n\geq 0} a_n x^n\)
  2. Multiply the recurrence through by \(x^n\).
  3. “Integrate out” by summing over all values of \(n\) for which the recurrence is valid.
  4. Write everything you see in terms of \(A(x), A'(x)\), or other polynomials in \(x\).
  5. Solve for \(A(x)\) to get some analytic function.
  6. (Optional) Produce a closed-form formula for \(a_n\) by expanding the analytic function as a power series, or using coefficient extraction: \[\begin{align*} a_n = \frac{1}{n!} {\left.{{\frac{\partial ^n A(x)}{\partial x^n}\,}}\right|_{x=0}} \end{align*}\]

Sequences, Sums, and Closed Forms

Table of Ordinary Generating Functions

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!}\)

Table of Exponential Generating Functions

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!}\)

Table of Sequences

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}\)

Operations on Generating Functions

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.

Ordinary Generating Functions

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}\)

Exponential Generating Functions

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\)



Some Known Generating Functions

\[\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)\).

Worked Examples


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.

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.

An Example Calculation

Compute the Mobius function for each element of the divisibility poset of \(n=90\).

The Divisibility Poset on n=90

Mobius Inversion

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*}\]

The 12-fold Way

\([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:

  1. Unrestricted, labeled \([n]\), labeled \([k]\)
    1. Words of length \(n\) from an alphabet of size \([k]\), with repetition allowed.
      1. \(k\) choices for first letter, \(k\) for second, etc
    2. For each of \(n\) balls, choose with replacement one of \(k\) bins as its target.
  2. Injective, labeled \([n]\), labeled \([k]\)
    1. Words of length \(n\) from an alphabet of size \([k]\) with no repetition (all letters unique).
    2. For each of \(n\) balls, choose without replacement one of \(k\) bins as its target
  3. Surjective, labeled \([n]\), labeled \([k]\)
    1. Words of length \(n\) from an alphabet of size \([k]\), where every letter appears at least once.
      1. Partition \(n\) slots into \(k\) groups, then assign letter \(a\) to one of the \(k\) group, letter \(b\) to one of the remaining \(k-1\) groups, etc
    2. Distribute \(n\) balls into \(k\) bins where each bin has at least one ball.
  4. Unrestricted, unlabeled \([n]\), labeled \([k]\)
    1. Number of ways to choose with replacement \(k\) symbols to appear in a word of length \(n\). Alternatively, all words of length \(n\) with letters choisen from \([k]\) with replacement, where we identify together all words that are anagrams of each other.
    2. Lay \(n\) indstinguishable balls out in a line, then place \(k-1\) dividers to form \(k\) compartments. Put all balls falling in the first compartment into bin 1, all in the second compartment to bin 2, etc.
      1. Use stars and bars
  5. Injective, unlabeled \([n]\), labeled \([k]\)


Dictionary of 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*}\]