146
$\begingroup$

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

enter image description here

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;

enter image description here

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.

enter image description here (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;

enter image description here

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

enter image description here

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

$\endgroup$
24
  • 18
    $\begingroup$ One of my favorites is the Cauchy identity (a fundamental product-sum relation): $\prod_{i,j}(1-x_iy_j)^{-1} = \sum_\lambda s_\lambda(x)s_\lambda(y)$. Even though this may follow from the MacMahon master theorem, its singular elegance deserves individual mention. $\endgroup$
    – Suvrit
    Aug 18, 2015 at 2:11
  • 2
    $\begingroup$ Does this allow for set theoretic infinitary combinatorics? :-) $\endgroup$
    – Asaf Karagila
    Aug 18, 2015 at 20:13
  • 4
    $\begingroup$ Either the rules are too strict or we are too lazy (certainly, I am!), but I am amazed not to find Lagrange inversion in this collection. $\endgroup$ Aug 19, 2015 at 6:32
  • 1
    $\begingroup$ There are several areas of combinatorics that are not yet represented. (Of course it is very natural that enumerative combinatorics has so many wonderful formulas.) Also if you have suggestions to choose from you can always mention them in a comment. $\endgroup$
    – Gil Kalai
    Aug 24, 2015 at 10:59
  • 2
    $\begingroup$ Gil, kudos for the effort of linking all the formulas like that. Perhaps it is worth adding a date, so when someone adds a new answer, and you haven't gotten around to add it to the question itself it won't be a false statement? :-) $\endgroup$
    – Asaf Karagila
    Sep 7, 2015 at 13:12

66 Answers 66

1 2
3
3
$\begingroup$

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.

$\endgroup$
3
  • 13
    $\begingroup$ Please make this self-contained by including explicit uses of the formula, as the question requests. $\endgroup$ Aug 19, 2015 at 23:45
  • $\begingroup$ @DouglasZare: I do not see the point of copying quite lengthy stuff from another MO discussion, moreover most likely this will cover only some partial cases. But you are welcome to elaborate on this if you like. $\endgroup$ Aug 20, 2015 at 16:28
  • 4
    $\begingroup$ The question says, "2) Present the formula explicitly (not just by name or by a link or reference)." You don't have to make it complete, but if you are going to start an answer you should be willing to write out the first example with an appropriately self-contained description, as others have been doing and as the question asks. $\endgroup$ Aug 20, 2015 at 16:52
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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.

$\endgroup$
1
  • 5
    $\begingroup$ Is it just me or is the closed formula a lot nicer than the asymptotic one? $\endgroup$ Sep 2, 2015 at 23:39
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ It is very important result, but I would not call it "formula". Also I doubt that geometry of numbers should be called "combinatorics". $\endgroup$ Aug 18, 2015 at 13:08
  • $\begingroup$ @FedorPetrov I am aware that calling it a formula is a bit of a stretch, but I do not think we should decide formula-hood on basis of complicated-ness! As to whether this falls under combinatorics, I do think it does --- it's a classic of discrete geometry. $\endgroup$
    – anemone
    Aug 18, 2015 at 13:28
1 2
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.