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

The Hook Formula. If $\lambda$ is a partition of $n$ then the number of standard Young tableaux of shape $\lambda$ is

$$f^\lambda = \frac{n!}{\prod_{\alpha \in [\lambda]} h_\alpha} $$

where $h_\alpha$ is the hook-length of the box $\alpha$ in the Young diagram $[\lambda]$ of $\lambda$, as shown below for $(5,4,2,1)$. The special case $\lambda = (n,n)$ gives the Catalan numbers:

$$f^{(n,n)} = C_n = \frac{(2n)!}{(n+1)!n!} = \frac{1}{n+1} \binom{2n}{n}. $$

If $m_k>m_{k-1}>\dots>m_1$ are hook-lengths in the first column of Young diagram $\lambda$, i.e. lengths of rows are $0<m_1\leqslant m_2-1 \leqslant m_3-2\leqslant \dots \leqslant m_k-(k-1)$, then equivalent form is $$ f^{\lambda}=\frac{n!}{\prod m_i!}\prod_{1\leqslant i<j\leqslant k} (m_j-m_i). $$
This formula for $f^{\lambda}$ was established by G. Frobenius (Uber die charaktere der symmetrischer gruppe, Preuss. &ad. Wk. sitz. (1900), 516–534.) and A. Young (Quantitative substitutional analysis II, Proc. London Math. Sot., Ser. 1, 35 (1902), 361–397). Equivalence follows from the observation that product of hook lengths in $j$-th row equals $m_j!/\prod_{i<j} (m_j-m_i)$.

The Hook Formula was first proved by Frame, Robinson and Thrall. It is important as a unifying result in enumerative combinatorics. It also gave another early indication (after Nakayama's Conjecture) of the importance of hooks, $p$-cores and $p$-quotients to the representation theory of the symmetric group.

Answer 2

The exponential formula Can be phrased as

All = exp(Connected)

In a more precise way, if you have a class $\mathcal{C}$ of labelled graphs which is locally finite i.e. for every finite set $F$ and $k\in \mathbb{N}$
$$ S(n,k)=\operatorname{card}(\mathcal{C}(F,k))<+\infty $$ where $\mathcal{C}(F,k)$ stands for the subclass of graphs with $F$ as labels and $k$ connected components ($S(n,k)$ is supposed to depend only on $n=\operatorname{card}(F)$). If, moreover, the class $\mathcal{C}$ is closed by

1. relabeling
2. connected components (i.e. $\Gamma\in \mathcal{C}$ iff all connected components of $\Gamma$ are in $\mathcal{C}$)
3. disjoint union

then $$ \sum_{n,k\geq 0}S(n,k)\frac{x^n}{n!}y^k=e^{y(\sum_{n\geq 1}S(n,1)\frac{x^n}{n!})}\qquad (1). $$ This formula has many applications and variants in combinatorics as the computation of the GF of the Bell, Stirling numbers, number of cycles, graphs of endofunctions (with or without constraints), set partitions and the analog for unlabelled graphs to cite only a few.

All the matrices $S(n,k)$ possess the Sheffer property i.e. the EGF of the k-th column is (up to a scalar) the k-th power of the EGF of the first (for $k=1$). It is equivalent to formula (1).

Matrices having the Sheffer property (not only provided by classes of labelled graphs) form an infinite dimensional Lie group generated by vector fields on the line (see Tom Copeland's answer). Connections of this group can be seen in combinatorial physics, statistics on graphs and over categories.

A usual, useful and (almost) immediate generalisation. In fact, we have
$$ S(n,k)=\operatorname{card}(\mathcal{C}(F,k))=\sum_{\gamma\in \mathcal{C}(F,k)} \mathbf{1}(\gamma) $$ where $\mathbf{1}$ is the constant (equal to $1$) function on the class $\mathcal{C}$, and one can, for free (i.e. with the same proof), replace $\mathbf{1}$ by any $\mathbb{Q}$-algebra valued multiplicative statistics, "$c$" i.e. such that $$ c(\gamma_1\sqcup \gamma_2)=c(\gamma_1)c(\gamma_2);\ c(\mathcal{C}_\emptyset)=1 $$ (where $\mathcal{C}_\emptyset$ is the empty graph and $\sqcup$ stands for the disjoint union).

Then, with
$$ S_c(n,k)=\sum_{\gamma\in \mathcal{C}(F,k)} c(\gamma) $$ (again, the sum is supposed to depend only on $n=\operatorname{card}(F)$), one still has $$ \sum_{n,k\geq 0}S_c(n,k)\frac{x^n}{n!}y^k=e^{y(\sum_{n\geq 1}S_c(n,1)\frac{x^n}{n!})} $$

Examples with the polynomial algebra $\mathbb{Q}[X]$ ($X$ is the alphabet $X=\{x_i\}_{i\geq 1}$)

• With the class of permutation graphs and the $\mathbb{Q}[X]$-valued multiplicative statistics $$ c(\pi)=\prod_{k\geq 1} x_k^{c_k(\pi)} $$ (where $c_k(\pi)$ is the number of $k$-cycles in $\pi$), one gets the cycle index formulas for the symmetric groups $$ \sum_{n=0}^\infty \frac{z^n}{n!} \sum_{\pi \in \mathfrak{S}_n} c(\pi) = \prod_{j=1}^\infty \exp \bigl( \frac{x_j}{j}z^j \bigr)\ . $$ (see Mark's comment below).
• With the class of set partitions (the set of graphs of equivalences on $[1,n]$ will be denoted $\mathcal{P}_n$ and $\mathcal{P}=\cup_{n\geq 0}\mathcal{P}_n$) and the $\mathbb{Q}[X]$-valued multiplicative statistics $$ c(\pi)=\prod_{k\geq 1} x_k^{c_k(\pi)} $$ (where $c_k(\pi)$ is the number of $k$-blocks in $\pi\in \mathcal{P}$), one gets similar formulas $$ \sum_{n=0}^\infty \frac{z^n}{n!} \sum_{\pi \in \mathcal{P}_n} c(\pi) = \prod_{j=1}^\infty \exp \bigl( \frac{x_j}{j!}z^j \bigr) $$

One can also use the same machinery for classes of graphs of endofunctions with constraints (as idempotent endofunctions and the like).

The analytic part of the exponential formula can be viewed as a particular case of Faà di Bruno's formula which itself can be traced back to the work of Arbogast (Louis-François-Antoine) and Newton–Girard's formulas. It is equivalent to Witt's formulas. Modern achievements are Riddell's formulas for labelled and unlabelled graphs.

Answer 3

MacMahon's formula for the number $M(a,b,c)$ of plane partitions that fit in an $a \times b \times c$ box:

$$ M(a,b,c) = \prod_{i=1}^{a} \prod_{j=1}^{b} \prod_{k=1}^{c} \frac{i+j+k-1}{i+j+k-2} $$

For more details, see https://en.wikipedia.org/wiki/Plane_partition#MacMahon_formula. This is arguably one of the most unexpected and beautiful formulas in algebraic combinatorics. Note that nothing like this holds when we move from plane partitions to "solid partitions" or beyond.

Answer 4

$$ \left[\prod_{i=1}^n x_i^{d_i}\right]f(x_1,\dots,x_n)=\sum_{a_i\in A_i}\frac{f(a_1,\dots,a_n)}{\prod_{i=1}^n\prod_{b\in A_i\setminus a_i} (a_i-b)},\, \deg f\leq \sum d_i,\, |A_i|=d_i+1. $$ This is the formula which proves Alon's Combinatorial Nullstellensatz. Here $f(x_1,\dots,x_n)$ is polynomial of degree at most $d_1+\dots+d_n$, $A_i$ are subsets of the ground field of given sizes $|A_i|=d_i+1$. CN claims that when $f$ does vanish on $\prod A_i$, coefficient of $\prod x_i^{d_i}$ of $f$ also vanishes. This claim follows from the formula immediately.

As well as MacMahon Master Theorem it allows to get a quick proof of Dixon's identity $$ [x^{2n}y^{2n}z^{2n}](x-y)^{2n}(y-z)^{2n}(z-x)^{2n}=(-1)^n\frac{(3n)!}{n! n! n!}. $$

Just apply the formula to the polynomial $$ f(x,y,z)=\prod_{i=-(n-1)}^n (x-y-i)(y-z-i)(x-z-i) $$ (the trick is that it has the same coefficient of $x^{2n}y^{2n}z^{2n}$ as $(x-y)^{2n}(y-z)^{2n}(z-x)^{2n}$) and sets $A_1=A_2=A_3=\{0,1,\dots,2n\}$. The only non-zero summand in RHS corresponds to $x=0, y=n, z=2n$ and may be easily calculated.

As for the history, this formula was rediscovered several times. It appeared in recent papers by Schauz (Algebraically solvable problems: describing polynomials as equivalent to explicit solutions, Electron. J. Combin. 15 (2008)), Lason (A generalization of Combinatorial Nullstellensatz, Electron. J. Combin. 17 (2010)) and Karasev and Petrov (Partitions of nonzero elements of a finite field into pairs, Israel J. Math. 192 (2012)). But as I've learnt from Vladislav Volkov it actually goes back even to C. G. Jacobi (Theoremata nova algebraica circa systema duarum aequationem inter duas variabiles propositarum, J. Reine Angew. Math. 14 (1835), 281-288), it is a special case of Euler-Jacobi formula for complete intersections (grid $\prod A_i$ is a typical complete intersection). My hope is that other cases of Euler-Jacobi (and beyond) formula also may have applications in combinatorics.

Answer 5

Let $f_i$ be the components of the $f$-vector of a simplicial polytope in $d$ dimensions: $f_i=$ the number of faces of dimension $i$. The Dehn-Sommerville equations express linear relations among the $f_i$. The equations can be phrased in several forms. Here is one: $$ f_{k-1} = \sum_{i=k}^d (-1)^{d-i} \binom{i}{k} f_{i-1}\;. $$ The usual convention is that $f_{-1}=f_d=1$. For $k=0$ and $d=3$, the equation becomes $$ f_{-1} = -f_{-1} + f_0 - f_1 + f_2 \;, $$ i.e., $V-E+F=2$. For arbitrary $d$ and $k=0$, the equation yields the Euler characteristic $\chi$.

For $k=1$ and $d=3$, the equation evaluates to $$f_0 = f_0 - 2f_1 + 3 f_2 \;,$$ i.e., $2E = 3F$, because "simplicial" means the faces are triangles.

History. According to the Wikipedia article,

"For polytopes of dimension 4 and 5, [the equations] were found by Max Dehn in 1905. Their general form was established by Duncan Sommerville in 1927."

Answer 6

Given a complex matrix $A=(a_{i,j})_{m \times m}$ and an $m$-tuple of non-negative integers $(k_1,\cdots,k_m)$, denote by $G(k_1,\cdots,k_m)$ the coefficient of $\prod_{i=1}^{m} x_i^{k_i}$ in the product $\prod_{i=1}^{m} (\sum_{j=1}^{m} a_{i,j}x_j)^{k_i}$.

The MacMahon Master Theorem is a useful, deep and elegant formula for the generating function of the $G(k_1,\cdots,k_m)$'s:

$$\sum_{(k_1,\dots,k_m)} G(k_1,\dots,k_m) \, t_1^{k_1}\cdots t_m^{k_m} \, = \, \frac{1}{\det (I_m - TA)},$$ where $T=\text{Diag}(t_1,\cdots,t_m)$.

Its importance was initially in the field of enumerative combinatorics, where it was used to count permutations and other functions (it got its name due to trivializing many such counting problems). For example, taking $a_{i,j} = 1-\delta_{i,j}$, the coefficient $G(1,\cdots,1)$ counts permutations with no fixed points. The formula can also be used to establish combinatorial identities, such as Dixon's beautiful one.

Although I. J. Good proved the formula using a generalization of Lagrange Inversion (which deserves to appear in this thread also), this is not merely some special case. It has a nicer theory and several quantum generalizations.

Just to emphasize the combinatorial aspect, I will mention that there are combinatorial proofs of the MacMahon Master Theorem. One such proof uses a Möbius function on permutations to prove that $\det (I_m - TA) \left( \sum_{(k_1,\dots,k_m)} G(k_1,\dots,k_m) \, t_1^{k_1}\cdots t_m^{k_m} \right) = 1$. It is due to Foata and can be found as a guided exercise in "The Art Of Computer Programming, Vol III", subsection 5.1.2, exercise 20. Another (somewhat similar) proof uses a sign-reversing involution (a very powerful idea) and a graph-theoretic interpretation. A reference is section 4.19 of these notes.

Answer 7

Not sure if this fits, but I find a proof of the Jacobi triple product formula in the form $$ \prod_{n>0}(1+q^{n-\frac{1}{2}}z)(1+q^{n-\frac{1}{2}}z^{-1})=\left(\sum_{l\in\mathbb{Z}}q^{l^2/2}z^l\right)\prod_{n>0}(1-q^n)^{-1} $$ based on the idea of Dirac sea extremely significant and thought-provoking. Wikipedia cites (13.3) of Peter J. Cameron's Combinatorics: Topics, Techniques, Algorithms where it is attributed to Borcherds.

Answer 8

$$\frac {1!~4!~7! \dots (3n-2)!}{n! (n+1)! (n+2)!\dots (2n-1)!}$$

This remarkable formula counts the number of alternating sign matrices of order $n$ as well as, monotone triangles, descending plane partitions whose parts do not exceed $n$, and various other important combinatorial entities. (See also this item on the online encyclopedia of integer sequences.)

Alternating sign matrices are $n$ by $n$ matrices with entries $+1$ $-1$ and $0$ such that each row and column the non-zero entries alternate in signs, and first non zero entry is $+1$. They were defined by Mills, Robbins, and Rumsey who conjectured their number. The formula was first proved by Zeilberger.

Answer 9

Matrix-tree Theorem. Let $G$ be a graph of size $n$, let $\lambda_{1}\geq \ldots\geq \lambda_{n}$ be the eigenvalues of its Laplacian matrix. Then the number of spanning trees of $G$ is $$ \frac{\lambda_{1}\lambda_{2}\ldots \lambda_{n-1}}{n} $$

Answer 10

The Tutte golden identity $$ {\chi}_T({\phi}+2)=({\phi}+2)\; {\phi}^{3\,V(T)-10}\, ({\chi}_T({\phi}+1))^2 $$ relates the value of the chromatic polynomial $\chi$ of any planar triangulation $T$ at $\phi +2$ and the square of the value at $\phi +1$, where $\phi =\frac{1+\sqrt 5}{2}$ is the golden ratio. $V(T)$ in the formula denotes the number of the vertices of the triangulation.

Tutte used this identity to give an elegant proof that ${\chi}_T({\phi}+2)>0$, a fact interesting in connection to the $4$-color theorem. [Reference: W.T. Tutte, More about chromatic polynomials and the golden ratio. 1970 Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) pp. 439–453 Gordon and Breach, New York] Recently this identity has been shown to fit in the framework of quantum topology.

Answer 11

For a permutation $\sigma \in S_n$, let $\ell(\sigma)$ denote the maximal length of an increasing subsequence in $\sigma$. Define $$ \ell_n = \frac{1}{n!} \sum_{\sigma \in S_n} \ell(\sigma), $$ the average value of $\ell(\sigma)$ for a $\sigma$ chosen uniformly at random from $S_n$.

The problem of finding the asymptotic value of $\ell_n$ for large $n$ was proposed by the famous mathematical and nuclear physicist Stanislaw Ulam in 1961. It was further popularized by John Hammersley in 1970, and solved (to a first order of approximation) in 1977 by Anatoly Vershik and Sergei Kerov, and independently by Ben Logan and Larry Shepp, who proved the following remarkable formula, which is the subject of my answer:

---

The Vershik-Kerov-Logan-Shepp formula: $$ \ell_n \sim 2 \sqrt{n}. $$

---

To give a proper explanation of why this formula is considered by many to be extremely "important research level mathematics" would require a book-length exposition. Fortunately, someone has written a book about this precise subject. As a brief summary, I will mention that:

1. The proof of this result is extremely clever and nontrivial (e.g., it takes up pages 5-68 in the book I mentioned above).

2. The proof requires a combination of combinatorial techniques, in particular a use of the hook length formula (another Important Formula in Combinatorics, in fact it's currently the most highly voted answer to this Math Overflow question), and difficult analytic techniques (complex analysis, Hilbert transforms, the calculus of variations). A nice illustration of the principle that "no (area of) math is an island."

3. The result and its proof by Vershik-Kerov-Logan-Shepp are just the beginning of a long story involving the discovery of a much deeper structure underlying such asymptotic behavior. Research on this and closely related subjects has been flourishing for the last twenty years and providing occupation for a large number of researchers, graduate students, postdocs, etc. It was also implicated in various awards and honors to several well-known mathematicians (e.g., Andrei Okounkov's Fields Medal).

Answer 12

The Rogers-Ramanujan identities are partition identities, i.e., statements that equate the number of integer partitions of an integer $n$ belonging to two different partition classes. There are two identities, so I recognize that posting both in one answer bends Rule (1) of Gil's question slightly, but I'm guessing any reasonable person will agree that the two identities belong and deserve to be stated together as one conceptual result.

Of course, I also recognize that according to the rules of the question the identities need to be stated as formulas. There are two ways to do this, which are equivalent to each other but quite different in presentation. First, the "pure" combinatorial statement of the identities is $$ A(n) = B(n), \ \ \ \ \ \ C(n)=D(n), \qquad (n=1,2,3,\ldots), $$ where:

$A(n)$ denotes the number of partitions of an integer $n$ not containing two consecutive parts (also known as minimal difference 2 partitions);

$B(n)$ denotes the number of partitions of $n$ into parts all of which are congruent to $1$ or $4$ mod $5$;

$C(n)$ denotes the number of partitions of $n$ not containing two consecutive parts and not having any parts equal to $1$;

and $D(n)$ denotes the number of partitions of $n$ into parts all of which are congruent to $2$ or $3$ mod $5$.

The problem with the above "formulas" is that most of the logical statement of the result is pushed down to the above verbal definitions that are much longer than the formulas themselves. This may cast some legitimate doubt about whether the R-R identities deserve to be considered proper formulas. Fortunately there is a second algebraic formulation using generating functions that encodes the entire statement of the identities into two self-contained equations, namely $$ \prod_{m=0}^\infty \frac{1}{(1-x^{5m+1})(1-x^{5m+4})} = \sum_{n=0}^\infty \frac{x^{n^2}}{(1-x)(1-x^2)\ldots(1-x^n)}, $$ $$ \prod_{m=0}^\infty \frac{1}{(1-x^{5m+2})(1-x^{5m+3})} = \sum_{n=0}^\infty \frac{x^{n(n+1)}}{(1-x)(1-x^2)\ldots(1-x^n)}, $$ where: ... well, where nothing! In this formulation, no extra verbiage needs to be added.

The fact that the above equations really encode the same statement as the combinatorial statement above is not difficult to see.

The R-R identities were proved by the British mathematician Leonard James Rogers in 1894, in the algebraic form above. I believe Rogers did not recognize the elegant combinatorial content, which is probably why his paper was largely ignored. They were then rediscovered by Ramanujan around 1913. See here for a bit more of their fascinating history.

The importance of the R-R identities is that they are extremely simple to state, and yet highly surprising as well as nontrivial to prove. They have had a large influence on research on partition bijections, bijective proofs, and algorithms in combinatorics, and are still inspiring new proofs and other new research (see for example the papers "Partition Bijections, a Survey" by Igor Pak and "A combinatorial proof of the Rogers-Ramanujan identities" by Pak and Boulet).

Perhaps most amazingly in my opinion, the R-R identities played a key role in Baxter's 1980 solution of the hard hexagon model in statistical physics.

Answer 13

Let $c_n$ be the number of self-avoiding walks of length $n$ on the hexagonal lattice starting at a fixed vertex. An amazing result of H. Duminil-Copin and S. Smirnov in 2010 asserts that $$ \mu_c \mathrel{\mathop:}= \lim_{n\to\infty}c_n^{1/n} = \sqrt{2+\sqrt{2}}. $$ This is the a big breakthrough in the subject of self-avoiding walks. Moreover, Flory (1948) and Nienhuis (1982) conjectured that for some constant $A$ we have $c_n\sim An^{11/32}\mu_c^n$. See https://arxiv.org/pdf/1007.0575.pdf.

Answer 14

The Ramanujan-Hardy asymptotic formula for the number of partitions $p(n)$ of $n$ is the following: $$p(n) \sim \frac{1}{4n\sqrt{3}}\exp\left(\sqrt{\frac{2n}{3}}\right), \quad n \to \infty$$ The proof of this formula led Ramanujan and Hardy to discover the circle method.

The circle method and related techniques have led to founding the subject of "analytic combinatorics". See the text by Flajolet and Sedgewick.

Answer 15

Faà di Bruno's formula generalizes the chain rule to higher order derivatives. Most compact form of Faà di Bruno's formula involves Bell polynomials $B_{n,k}\left(x_1,x_2,\dots,x_{n-k+1}\right)$ and illustrates its combinatorial nature:

$${d^n \over dx^n} f(g(x)) = \sum_{k=1}^n f^{(k)}(g(x))\cdot B_{n,k}\left(g'(x),g''(x),\dots,g^{(n-k+1)}(x)\right).$$

Answer 16

$N({\cal A})= \sum _{x\in L({\cal A})}(-1)^{r(x)}\mu (0,x)$

This is Zaslavsky's formula for the number of regions in an arrangement of hyperplanes.

The details: Given an arrangement of hyperplanes $\cal A$ in ${\mathbb R}^d$, $N({\cal A})$ is the number of regions of the arrangement, namely, connected components in the complement of the union of all hyperplanes. A remarkable fact is that this number depends only on the combinatorics of the lattice of flats determined by $\cal A$, namely the set of all intersection of hyperplanes in the family ordered by inclusion. The formula gives a simple description on the number of regions in terms of the Möbius function of such flats.

The importance: This is an extremely useful formula and a starting point to much research and important questions. For example, if you replace hyperplanes by subspaces of various dimensions then there is a formula by Goresky and Macpherson giving the Betti numbers of the complement in terms of the lattice of flats.

Answer 17

$$(2/e) (1+o(1)) k2^{k/2} \le R(k+1, k+1) \leq (4 - \varepsilon)^k.$$

Best lower and upper bound for diagonal Ramsey numbers. The Ramsey number $R(k,\ell)$ is the smallest integer $n$ such that any two-coloring of the edges of the complete graph on $n$ vertices $K_n$ by red and blue, there either is a red $K_k$ (namely, a complete graph on $k$ vertices all of whose edges are colored red), or a blue $K_{\ell}$. The lower bound is an improvement, by a constant factor, using the Lovasz local lemma, of Erdos' original 1947 lower bound. The upper bound is due to (update:) Marcelo Campos, Simon Griffiths, Robert Morris, & Julian Sahasrabudhe. (2023). An exponential improvement for diagonal Ramsey.

Answer 18

For a Young diagram $\lambda$ of size $n$, let $f^\lambda$ denote the number of standard Young tableaux of shape $\lambda$ (discussed above in Mark Wildon's answer about the hook length formula). Then $$ \sum_{\lambda} (f^\lambda)^2 = n!, \qquad\qquad\qquad\qquad\qquad (*) $$ where the sum ranges over all Young diagrams of size $n$.

This formula is interesting because it is a meeting point of ideas from combinatorics and representation theory. One proof is bijective and involves a way of mapping permutations (enumerated by the right-hand side) to pairs of standard Young tableaux of similar shape (enumerated by the left-hand side). This mapping is known as the Robinson-Schensted correspondence (a special case of the RSK correspondence).

A second proof of $(*)$ interprets the formula as a special case of the representation theoretic fact that the sum of the squared dimensions of the irreducible representations of a finite group is equal to the order of the group. One then relies on the classification of irreducible representations of the symmetric group $S_n$ (they are in one-to-one correspondence with Young diagrams $\lambda$ of size $n$) and the fact that the dimension of the irreducible representation associated with a Young diagram $\lambda$ is equal to $f^\lambda$ (both of these facts being themselves quite nontrivial, and extremely interesting in their own right). To me it's fascinating that $(*)$ has two such completely different proofs, both using combinatorial ideas but the second one being much more algebraic and intricate. (There is also another purely combinatorial proof due to Greene, Nijenhuis and Wilf based on the very pretty idea of the "hook walk," which is a kind of planar random walk.)

A third reason why $(*)$ is interesting is that it has proved extremely important in the study of longest increasing subsequences of permutations (described in my answer about the Vershik-Kerov-Logan-Shepp formula and in Richard Stanley's answer elaborating on the same subject). In this context it is often rewritten as $$ \sum_{\lambda} \frac{(f^\lambda)^2}{n!} = 1, \qquad\qquad\qquad\qquad\qquad (**) $$ and interpreted as the statement that the function assigning weight $(f^\lambda)^2/n!$ to a Young diagram $\lambda$ is a probability measure, known as Plancherel measure. This measure is extremely natural and interesting and its analysis is the subject of a huge literature.

As a final comment, I find it regretful that $(*)$ doesn't have a standard name in the literature. Any suggestions for what would be a good name to refer to it by?

Answer 19

Abel's identity (also referred to as Abel's generalization of the binomial formula)

$$x^{-1}(x+y+n)^n=\sum_{k=0}^n{{n} \choose {k}}(x+k)^{k-1}(y+n-k)^{n-k}.$$

Answer 20

The Kneser graph $KG_{n,k}$ is the graph on $k$-subsets of $\{1, \dots, n\}$ with two subsets made adjacent when they are disjoint. The formula $$\chi(KG_{n,k}) = n - 2k + 2$$ was proved by Lovász in 1978 using topological methods, which gave birth to the area of topological combinatorics.

Some references:

• Kneser's conjecture, chromatic number, and homotopy.
• Using the Borsuk-Ulam theorem.

Answer 21

Van der Waerden's conjecture (1926): If $A$ is a doubly stochastic matrix of size $n\times n$ then $$\text{per}(A)\ge\frac{n!}{n^n}$$ Moreover, equality holds if and only if all the entries of $A$ are $\frac{1}{n}$.

The conjecture was proved by B. Gyires (1980), G. P. Egorychev (1981) and D. I. Falikman (1981). Egorychev and Falikman won the Fulkerson Prize for this.

---

A square matrix with non-negative entries is said to be doubly stochastic if every row and every column sums up to $1$.

The permanent of a matrix $A=(a_{ij})$ of size $n\times n$ is $$\text{per}(A)\overset{\text{def}}{=}\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i\sigma(i)}$$ i.e. the only difference from the definition of determinant is that we don't multiply by the sign of $\sigma$.

Combinatorially, since the sum iterates over elements of the symmetric group, it counts the sum of the edge weights of all perfect matchings of a undirected bipartite graph. Alternatively, it can count the sum of the weights of the cycle covers of a directed graph with adjacency matrix $A$.

Turns out that while computing the determinant is easy (e.g. using Gaussian elimination), computing the permanent is #P-complete even for 0/1 matrices, which makes it an important problem in complexity theory.

You are welcome to edit the post and elaborate on the importance of the theorem.

Answer 22

Expanding on Dan Romik's posting of the Vershik-Kerov-Logan-Shepp formula for the expected length of the longest increasing subsequence of a random permutation $\sigma\in S_n$, there is the fantastic formula of Baik, Deift, and Johansson for the limiting distribution of the length $\mathrm{is}(\sigma)$ of the longest increasing subsequence of $\sigma\in S_n$: for random (uniform) $\sigma\in S_n$ and all $t\in\mathbb{R}$ we have $$ \lim_{n\rightarrow\infty} \mathrm{Prob} \left(\frac{\mathrm{is}(\sigma)-2\sqrt{n}}{n^{1/6}}\leq t\right) = F(t), $$ where $F(t)$ is the Tracy-Widom distribution. The Tracy-Widom distribution $F(t)$ is defined as follows. Let $u(x)$ be the solution to $$ \frac{d^2}{dx^2}u(x) = 2u(x)^3+xu(x) $$ with certain initial conditions. Then $$ F(t) = \exp\left( -\int_t^\infty (x-t)u(x)^2\,dx \right). $$

Answer 23

I'm confused about why no one has mentioned Stirling's formula for the factorial function $n!$, clearly the most famous and important formula in asymptotic combinatorics, and easily one of the most important and recognizable in all of mathematics. It states that the number $n!$ of permutations of $1,\ldots,n$ is given asymptotically as $n\to\infty$ by

$$ n! \sim \sqrt{2\pi n} (n/e)^n. $$

The weaker statement that $n! \sim C\sqrt{n} (n/e)^n$ for some number $C>0$ was first proved by De-Moivre. James Stirling found the value of $C$ shortly afterwards, around 1730 apparently.

Note that Gil was asking for formulas that represent "important research level mathematics" and was vague about whether classical results are allowable. Of course nowadays the principles behind how to prove Stirling's formula and similar results are well-understood, but this was undoubtedly cutting-edge research back in the 1700s. In addition, many new proofs of the formula have been published throughout the ages, including quite recently (see here for a non-subscription download). Furthermore, the standard proof uses the saddle-point method and can be thought of as a prototype for a large number of new and very modern results in asymptotic combinatorics that are being published all the time. So, Stirling's formula is not just "old" mathematics -- it is a true gem that contains important ideas at the forefront of current research. And this is not even mentioning its importance as a fundamental result that plays a role in the derivation of many basic estimates and bounds in virtually all areas of mathematics, as well as computer science, physics, statistics, etc.

Answer 24

No doubts, the inclusion-exclusion principle generates most common type of formulae used in enumerative combinatorics. Examples include explicit formulae for derangements, Striling numbers, rook polynomials, Euler's totient function, and so on.

$$\left\lvert \bigcup_{i=1}^n A_i \right\rvert = \sum_{\emptyset\ne J\subseteq\{1,2,\dots,n\}} (-1)^{|J|-1} \left\lvert \bigcap_{j\in J}^n A_j \right\rvert$$

Answer 25

Series multisection is a folklore formula (Riordan called it an "ancient vintage" in his 1968 book "Combinatorial identities"), which from a given analytical generating function for some numerical sequence allows one to obtain a generating function for a subsequence with indices forming an arithmetic progression. In particular, it leads to a closed-form expression for sums of binomial coefficients taken with a certain step $c$:

$${q\choose d} + {q\choose d+c} + {q\choose d+2c} + \cdots = \frac{1}{c}\cdot \sum_{k=0}^{c-1} \left(2 \cos\frac{\pi k}{c}\right )^q\cdot \cos \frac{\pi(q-2d)k}{c}.$$

Answer 26

The combinatorics underlying iterated derivatives (infinitesimal Lie generators) for compositional inversion and flow maps for vector fields.

Consider a compositional inverse pair of functions, $h$ and $h^{-1}$, analytic at the origin with $h(0)=0=h^{-1}(0)$.

Then with $\omega=h(z)$ and $g(z)=1/[dh(z)/dz]$,

$$\exp \left[ {t \cdot g(z)\frac{d}{{dz}}} \right]f(z) = \exp \left[ {t\frac{d}{{d\omega }}} \right]f[{h^{ - 1}}(\omega )] = f[{h^{ - 1}}[t + \omega]] = f[{h^{ - 1}}[t + h(z)]],$$ so $$\exp \left[ {t \cdot g(z)\frac{d}{dz}} \right]z |_{z=0} = \exp \left[ {t \cdot \frac{d}{dh(z)}} \right] z |_{z=0} = h^{-1}(t) \; .$$

Expansion of the left hand side in terms of the derivatives of $g(z)$ gives the refined Eulerian numbers of OEIS A145271 and can be depicted with forests of trees à la Cayley.

The results of different general expansions of the LHS can be expressed as graded partition polynomials in an infinite set of indeterminates but not in general as simple bivariate polynomials such as for the Sheffer matrices alluded to in Duchamp's answer. The binomial Sheffer matrix rep applies only for particular instantiations of $g(z)$, e.g., $g(x)=(1+x)$. My notes Lagrange à la Lah Part I and II discuss the simple binomial Sheffer sequences for the Stirling numbers of the first and second kinds and Lah numbers (represented by rooted trees--complete trees, corollas or bouquets, and binary trees, respectively) their refined partition polynomial counterparts representing functional composition (by umbralizing the trees), and their further generalization to Lagrange / compositional inversion partition polynomials (by coloring the trees), all of which, as noted, can be represented by trees, among other combinatoric structures. A different tack involves emphasizing the refined noncrossing partitions of OEIS A134264 and another type of generalized Sheffer sequence, Appell partition polynomials, which can be related to the generalized Hirzebruch criterion and free probability constructs.

With the power series rep $h(z)= c_1z + c_2z^2 + c_3z^3 + ... ,$

$$\frac{1}{5!}[g(z)\frac{d}{{dz}}]^{5}z|_{z=0} = \frac{1}{c_1^{9}} [14 c_2^{4} - 21 c_1 c_2^2 c_3 + c_1^2[6 c_2 c_4+ 3 c_3^2] - 1 c_1^3 c_5],$$

which is the coefficient of the fifth order term of the power series for $h^{-1}(t)$. This is related to a refined f-vector (face-vector) for the 3-D Stasheff polytope, or 3-D associahedron, with 14 vertices (0-D faces), 21 edges (1-D faces), 6 pentagons (2-D faces), 3 rectangles (2-D faces), 1 3-D polytope (3-D faces).

This correspondence between the refined f-vectors of the Stasheff polytopes, or associahedra, and the coefficients of the compositional inverse holds in general, (see A133437, inversion for power series, and compare with A033282, coarse f-vectors for associahedra, and with MO-6373). These refined partition polynomials are also a refined presentation of the number of diagonal dissections of a convex n-gon (A033282) or, equivalently, the refined numbers for a set of Schroeder lattice paths (A126216), which sum to the little Schroeder numbers (A001003). Succinctly displaying the connections between the differential analysis surrounding the inverse function theorem and iterated derivatives and the geometry of the associahedra through the signed, refined face partition polynomials of the $m$-dimensional faces of the $k$-dimensional associahedron,

$$h^{-1}(t)= \exp \left[ {t \cdot \frac{d}{d[h(z)=c_1 z + c_2 z^2 + \cdots]}} \right] z |_{z=0} \;$$

$$=\frac{t}{c_1}+\sum_{n \ge 2} t^n c_1^{-(2n-1)}\sum_{m=0}^{n-2} Face[m\;of \;(n-2)-D \; associahedron;\; c_1,...,c_{n}] \; .$$

If $h(z)$ is presented as a Taylor series, the LIF A134685 is obtained, which is related to the tropical Grassmannian G(2,n) and phylogenetic trees (A134991) and to the partitioning of 2n elements into n groups, giving the usual coefficients for the partition polynomials for Lagrange inversion (LI).

Inversion in terms of the coefficients of the reciprocal $z/h(z)$ gives the refined Narayana numbers A134264, which are the refined h-polynomials of the simplicial complexes (A001263) dual to the Stasheff associahedra and also a refined enumeration of a set of Dyck lattice paths A125181 and noncrossing partitions (related to free probability, iterated self-convolutions, and enumeration of positroids), which sum to the Catalan numbers A000108.

Also, the "infinitesimal generators" A145271 for these reps have very interesting associations (e.g., to permutahedra, surjections, and multiplicative reciprocals A019538/A049019, for the LIF A134685) and allow reps of the partition polynomials for A133437 as colored umbral binary trees related to refined Lah polynomials.

One application related to cohomology is illustrated by OEIS-A074060 "Graded dimension of the cohomology ring of the moduli space of n-pointed curves of genus 0 satisfying the associativity equations of physics (also known as the WDVV equations)." See the links in this OEIS entry and and the LIF entries noted above for more on the relation of Lagrange inversion (or, equivalently, the Legendre transform) of series to the cohomology of moduli spaces. See also the MO-Qs Compositional inversion and generating functions in algebraic geometry and Why is there a connection between enumerative geometry and nonlinear waves?.

These reps can be related to antipodes of Hopf algebras, such as the Faa di Bruno Hopf algebra, as well.

The connection to binomial Sheffer sequences of polynomials $p_n(t)$, such as the Bell / Touchard polynomials (Stirling numbers of the second kind) and the falling factorial polynomials (Stirling numbers of the first kind), derives from the (umbral) representation of their exponential generating functions as

$$\exp(p.(t) \; \omega)= \exp(t \; h^{-1}(\omega))$$

and the operator relation

$$ (g(z)D_z)^n \; \exp(t\;z) |_{z=0} = (D_\omega)^n \exp(t \; h^{-1}(\omega)) |_{\omega = 0} = (D_\omega)^n \exp(p.(t) \; \omega) |_{\omega=0} = (p.(t))^n = p_n(t) .$$

The repeated operation of $g(z)D_z$ can be represented as forests of trees as noted above and sketched in my notes Mathemagical Forests.

Rich history too: The flow formula, a.k.a. generalized Taylor series/exp differential op, (and commutation relations) goes back at least to the 1850s with Charles Graves (cf. MO-Q on an operator identity of Sylvester, ref. to Harold Davis, and note pre-Lie algebras), and normal ordering for the Witt ops to Scherk in the 1820s. Comtet (& Prouhet or Pourchet?, see A139605) in the 1970s expanded on the Lie derivative connections to many special functions; however, work on the ops $(xDx)^n$ and $(DxD)^n$ precedes his work. Carlitz, al-Salam (see A132440), Poole and Chatterjea (see MO-Q on falling factorial op), Blissard, Bell, Sheffer, Steffensen, Pincherle, Rota, Roman, B. Taylor, N. Ray and C. Lenart, Dattoli, Srivastava, Bergeron, Labelle, and Leroux, and many others figure in this history also. See also brief historical notes in The generalized Stirling and Bell numbers revisited by Mansour, Schork, and Shattuck, and in Combinatorial models of creation-annihilation by Blasiak and Flajolet on a line of investigators.

Answer 27

Either Knop and Sahi's formula for the integer Jack polynomials,

$$J^{(\alpha)}_\mu(x) = \sum_{T\text{ admissible of shape } \mu} d_T(\alpha) x^T$$

where the sum is over a certain set of tableaux, and $d_T$ is a weight, or the more general formula for the modified Macdonald polynomials,

$$\tilde{H}_\mu(x;q,t) = \sum_{T \text{ shape } \mu} q^{inv(T)} t^{maj(T)}x^T$$

which is a really amazing formula.

Answer 28

Fisher's inequality $$b \ge v.$$ Asserts that the number of blocks in every 2-design is at least the number of elements. A design is a collection of $k$-elements subsets (called blocks) of a set $V$ with $v$ elements such that every pair of elements of $V$ belong to the same number of blocks. This fundamental relation is closely related to the Erdos-DeBruijn theorem in extremal combinatorics, and the linear theoretic proof by Bose is an important starting point for linear algebra methods in combinatorics.

Answer 29

The MacWilliams identity

$$W(C^\perp;x,y) = \frac{1}{\mid C \mid} W(C;y-x,y+x).$$

This identity connects the weight enumerator of a linear binary code $C$ with that of the dual code $C^\perp$. Here, $C$ is a linear subspace of $ \mathbb{F}_2^n$, $C^{\perp}$ is the dual space, and $W(C,x,y)$ is the weight enumerator defined as follows: Let $C_t$ be the number of code-words of weight $t$ (namely, vectors in $X$ with $t$ '1's), $$W(C;x,y)= \sum A_t x^t y^{n-t}.$$

The identity extends also to codes over other fields and to non-linear codes. It is very important in coding theory and has various other applications.

Answer 30

An elegant and rather unexpected formula for the powers of the generating function for Catalan numbers $C_n = \frac{1}{n+1}\binom{2n}{n}$: $$\left(\sum_{n=0}^{\infty} \frac{1}{n+1}\binom{2n}{n} \cdot x^n\right)^m = \sum_{n=0}^{\infty} \frac{m}{n+m}\binom{2n+m-1}{n} \cdot x^n.$$ The formula can be further continued as $\ldots =\left(\frac{1-\sqrt{1-4x}}{2x}\right)^m$, but this would spoil the beauty of the above identity.