Important formulas in combinatorics

Question

Motivation:

The poster for the conference celebrating Noga Alon's 60th birthday, fifteen formulas describing some of Alon's work are presented. (See this post, for the poster, and cash prizes offered for identifying the formulas.) This demonstrates that sometimes (but certainly not always) a major research progress, even areas, can be represented by a single formula. Naturally, following Alon's poster, I thought about representing other people's works through formulas. (My own work, Doron Zeilberger's, etc. Maybe I will pursue this in some future posts.) But I think it will be very useful to collect major formulas representing major research in combinatorics.

The Question

The question collects important formulas representing major progress in combinatorics.

The rules are:

Rules

1) one formula per answer

2) Present the formula explicitly (not just by name or by a link or reference), and briefly explain the formula and its importance, again not just link or reference. (But then you may add links and references.)

3) Formulas should represent important research level mathematics. (So, say $\sum {{n} \choose {k}}^2 = {{2n} \choose {n}}$ is too elementary.)

4) The formula should be explicit as possible, moving from the formula to the theory it represent should also be explicit, and explaining the formula and its importance at least in rough terms should be feasible.

5) I am a little hesitant if classic formulas like $V-E+F=2$ are qualified.

An important distinction:

Most of the formulas represent definite results, namely these formulas will not become obsolete by new discoveries. (Although refined formulas are certainly possible.) A few of the formulas, that I also very much welcome, represent state of the art regarding important combinatorial parameters. For example, the best known upper and lower bounds for diagonal Ramsey's numbers. In the lists and pictures below an asterisk is added to those formulas.

The Formulas (so far)

In order to make the question a more useful source, I list all the formulas in categories with links to answer (updated Feb. 6 '17).

Basic enumeration: The exponential formula; inclusion exclusion; Burnside and Polya; Lagrange inversion; generating function for Fibonacci; generating function for Catalan; Stirling formula; Enumeration and algebraic combinatorics: The hook formula; Sums of tableaux numbers squared, Plane partitions; MacMahon Master Theorem; Alternating sign matrices; Erdos-Szekeres; Ramanujan-Hardy asymptotic formula for the number of partitions; $\zeta(3)$; Shuffles; umbral compositional identity; Jack polynomials; Roger-Ramanujan; Littlewood-Ricardson;

Geometric combinatorics: Dehn-Somerville relations; Zaslavsky's formula; Erhard polynomials; Minkowski's theorem. Graph theory: Tutte's golden identity; Chromatic number of Kneser's graph; (NEW)Tutte's formula for rooted planar maps ; matrix-tree formula; Hoffman bound; Expansion and eigenvalues; Shannon capacity of the pentagon; Probability: Self avoiding planar walks; longest monotone sequences (average); longest monotone sequences (distribution); Designs: Fisher inequality; Permanents: VanderWaerden conjecture; Coding theory: MacWilliams formula; Extremal combinatorics: Erdos-Sauer bound; Ramsey theory: Diagonal Ramsey numbers (); Infinitary combinatorics: Shelah's formula (); A formula in choiceless set theory. Additive combinatorics: sum-product estimates (*); Algorithms: QuickSort.

(Larger formulas): Series multisection; Faà di Bruno's formula; Jacobi triple product formula; A formula related to Alon's Combinatorial Nullstellensatz; The combinatorics underlying iterated derivatives (infinitesimal Lie generators) for compositional inversion and flow maps for vector fields (also related to the enumerative geometry of associahedra); some mysterious identities involving mock modular forms and partial theta functions;

Formulas added after October 2015: Hall and Rota Mobius function formula; Kruskal-Katona theorem; Best known bounds for 3-AP free subsets of $[n]$ (*);

After October 2016: Abel's binomial identity; Upper and lower bounds for binary codes;

Answer 1

Lagrange Inversion (Lagrange–Bürmann formula) plays an important role in combinatorics. There is a dedicated MO discussion of its applications (in combinatorics and beyond). In particular, see my answer there for its application for generating functions.

Answer 2

The umbral compositional identity

$$ (x)_{\frac{}{n}}= Lah_n((x)_{\frac{\bullet}{}})$$

and the inverse relation

$$ (-1)^n(x)_{\frac{n}{}}= Lah_n(-(x)_{\frac{}{\bullet}})$$

as explained combinatorially by Joni, Rota, and Sagan in From Sets to Functions: Three Elementary Examples, where $((x)_{\frac{}{\bullet}})^n=(x)_{\frac{}{n}}$ is a rising factorial polynomial; $((x)_{\frac{\bullet}{}})^n = (x)_{\frac{n}{}}$, a falling factorial polynomial; and $Lah_n(x)= n! \; \sum_{k=0}^n \binom{n-1}{k-1} \; \frac{x^k}{k!}$, a Lah polynomial. For a nice, short, geometric tutorial on the Whitney numbers Rota alludes to in the paper (coined by Rota), see Josh Cooper's math webpage.

This illustrates Rota and associates' influential program to interpret what are essentially identities of finite operator calculus / umbral calculus using combinatorial constructs--posets, lattices, cycles, Mobius inversion, etc. (Rota's combinatorial interpretation of the Dobinski formula is also an early illustration.)

A further umbral composition with the Bell / Touchard polynomials, $\phi_n(x)$, gives $GS2_{n,j}(y)$, the generalized Stirling numbers of the second kind for positive integer values of $y$ that underlie the normal ordering representation of the Lie derivative rep for the Witt-Lie algebra:

$$ [-y\;(-\phi.(x)/y)_{\frac{\bullet}{}}]^n = \sum_{k=0}^n S1_{n,k} \; (-y)^{n-k} \sum_{j=0}^k S2_{k,j} \; x^j = \sum_{j=0}^n \;GS2_{n,j}(y) \; x^j = RT_n(y,x)\; \; $$

with

$$(x^{1+y}D)^n = x^{ny}\; RT(y,:xD:)$$

where $(:xD:)^n = x^nD^n$ and $D=d/dx \, .$ These coefficients can be interpreted as enumerating forests of m-ary trees as well as other combinatorial structures. $y=-1,0,1$ give generators for $SL2$.

The generalized Stirling numbers of the first kind comprise the inverse matrix for that of $GS2_{n.j}(y)$ and are readily deduced from either the matrix rep of $GS2$ or through direct umbral compositional inversion, noting that $(\phi.(x))_{\frac{n}{}}= x^n = \phi_n((x)_{\frac{\bullet}{}}) \; ,$

$$(-y\phi.(-x/y) )_{\frac{n}{}} = \sum_{k=0}^n S1_{n,k}\; (-y)^k \sum_{j=0}^k S2_{k,j} \; (-x/y)^j = \sum_{j=0}^n \;GS1_{n,j}(y) \; x^j \; .$$

The generalized Dobinski relation immediately leads to other formulas for these numbers.

This rich interplay between umbral calculus and analytic combinatorics has a long history stretching from Scherk, Blissard, Cayley, and Sylvester to modern times with Rota and Flajolet, among many others.

Answer 3

Two more:

The number of positive integer solutions to $x^2 + y\leq z$ (here $x, y$ are the unknown), with $y$ prime, is $$r(z) \sim \frac{2}{3}\frac{z^{3/2}}{\log z}.$$ See here.

Let $S$ be an infinite subset of positive integers, and the number of elements of $S$ less or equal to $x$ is asymptotically equal to $a x^b / (\log x)^c$ with $0<a, 0<b<1, c\geq 0$. Then the number of positive integer solutions to $x + y\leq z$ (here $x, y\in S$ are the unknown) is asymptotically equal to $$r(z)\sim\frac{a^2b z^{2b}}{(\log z)^{2c}}\cdot \frac{\Gamma(b)\Gamma(b+1)}{\Gamma(2b+1)}.$$

This covers both sums of two primes and sums of two squares. See here.

Answer 4

The asymptotic formula of the average number of comparisons used by the Quick Sort algorithm.

\begin{align*} Q_n=2n(\ln n + \gamma -2)+2\ln n+2\gamma+1+O\left(\frac{1}{n}\right)\tag{1} \end{align*}

Volume 3 of Knuth's classic The Art of Computer Programming is titled Sorting and Searching. It presents a wealth of applications of these two fundamental combinatorial themes and one gem is C.A.R. Hoare's Quicksort algorithm.

Quicksort is the standard sorting procedure in UNIX systems and has been cited as we can read in this paper by J.A. Fill as one of the ten algorithms with the greatest influence on the development and practice of science and engineering in the $20$th century.

Here's the algorithm according to Quick sort - Average complexity by J. Cichon.

Algorithm: Let $Q_n$ denote the average number of comparisons over all permutations of $n$ pairwise different elements stored in an array of size $n$. Since $Q_0$ and $Q_1$ are clearly zero, we may assume that $n\geq 2$. We select a pivot element and need $n-1$ comparisons with all remaining elements. The pivot divides the array in a left and a right part. The left part can be of any size $k$ from $0$ to $n-1$, with $k$ equiprobable. This leads to the recursion formula (Quick Sort Equation):

\begin{align*} Q_n=(n-1)+\frac{1}{n}\sum_{k=0}^{n-1}\left(Q_k+Q_{n-1-k}\right) \end{align*} or due to symmetry \begin{align*} Q_n=(n-1)+\frac{2}{n}\sum_{k=0}^{n-1}Q_k \end{align*}

A nice closed formula of $Q_n$ in terms of Harmonic numbers is stated in J. Cichon's paper:

\begin{align*} Q_n=(n+1)(4H_{n+1}-2H_n-4) \end{align*}

The Quick Sort algorithm and the asymptotic formula (1) showing order $n\ln n$ can be seen as one representative of a whole class of related sorting algorithms all of them with great importance and wide applicability.

Answer 5

In a wider context, there is a well-known list of 17 formulas (selected by Ian Stewart) that changed the course of history, see https://www.businessinsider.com/17-equations-that-changed-the-world-2014-3?IR=T

Answer 6

Minkowski theorem (of 1896, by Hermann Minkowski) is sometimes mentioned as the cornerstone of the geometry of numbers. It gives an upper bound on the volume of closed convex sets (symmetric w.r.t. origin) in $\mathbb{R}^n$ that do not contain an arrow with integer coordinates.

Considering the real vector space $\mathbb{R}^n$, a lattice of points $L$ in $\mathbb{R}^n$ of determinant $\mathrm{det}(L)$, and a closed convex set $S$ in $\mathbb{R}^n$ that is symmetric w.r.t. the zero vector and of volume at least $2^n \mathrm{det}(L)$, the theorem states that $S$ contains at least one nonzero point of $L$.