113
$\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$
  • 15
    $\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 '15 at 2:11
  • 2
    $\begingroup$ Does this allow for set theoretic infinitary combinatorics? :-) $\endgroup$ – Asaf Karagila Aug 18 '15 at 20:13
  • 3
    $\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$ – Victor Protsak Aug 19 '15 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 '15 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 '15 at 13:12

61 Answers 61

7
$\begingroup$

Burnside Lemma and Redfield-Polya Theorem are celebrated results in combinatorics. They allow to enumerate objects modulo group actions. One of the classic (and simplest) examples is enumeration of necklaces modulo rotations. Other examples include various graphs, chemical compounds, etc.

$\endgroup$
  • 9
    $\begingroup$ Please make this self-contained by including explicit uses of the formula, as the question requests. $\endgroup$ – Douglas Zare Aug 19 '15 at 23:45
7
$\begingroup$

Since infinitary combinatorics were allowed and nobody has done it let me introduce some noise with Shelah´s celebrated cardinal arithmetic inequality:$$\aleph_\omega^{\aleph_0} < \max\{\aleph_{\omega_4},(2^{\aleph_0})^+\},$$ which shows that cardinal exponentiation is not as wild as it was thought to be. People may want to read Shelah´s paper Cardinal Arithmetic for Skeptics, Bulletin of the AMS, Vol.26, Num. 2, 1992.

$\endgroup$
  • $\begingroup$ Here is a post about it (in a simpler form) gilkalai.wordpress.com/2012/01/18/… $\endgroup$ – Gil Kalai Aug 19 '15 at 18:02
  • 2
    $\begingroup$ The use of $\max$ is a bit confusing, and it will be clearer, in my opinion, to write $\aleph_\omega^{\aleph_0}<\aleph_{\omega_4}\cdot(2^{\aleph_0})^+$. $\endgroup$ – Asaf Karagila Aug 21 '15 at 23:50
  • $\begingroup$ @Asaf Karagila What's wrong with max( , ) wherever we have total ordering? $\endgroup$ – Incnis Mrsi Aug 23 '15 at 13:21
  • 1
    $\begingroup$ @Incnis Mrsi: Nothing is wrong, really. But it feels less natural than addition and multiplication of cardinals, since it causes you to pause and think "Which one is larger?", and then realize the result is actually irrelevant. Whereas addition/multiplication works better since it's just a constant term. $\endgroup$ – Asaf Karagila Aug 23 '15 at 13:23
  • 4
    $\begingroup$ @AsafKaragila, your comment makes no sense to me. I don´t see how $a \cdot b$ is more of a "constant term" or less confusing than $\max\{a,b\}$ when $a\cdot b=\max\{a,b\}$. In addition, I feel that $\max$ captures a bit more the spirit of the formula: if $2^{\aleph_0}$ is not too big, $\aleph_{\omega_4}$ is a bound. $\endgroup$ – Ramiro de la Vega Aug 24 '15 at 11:12
7
$\begingroup$

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.

enter image description here

$\endgroup$
6
$\begingroup$

(Initially I had this in my other answer, then I followed a suggestion by S. Carnahan and made it a separate one)

There are several impressive combinatorial proofs of some mysterious identities involving mock modular forms and partial theta functions. Just to give an example - here is my favorite (I actually mentioned it in a comment to one of my MO questions), \begin{multline*} \frac q{1+q}+2\frac{(1-q)q^2}{(1+q)(1+q^2)}+3\frac{(1-q)(1-q^2)q^3}{(1+q)(1+q^2)(1+q^3)}+...\\+\frac{(1-q)(1-q^2)(1-q^3)\cdots}{(1+q)(1+q^2)(1+q^3)\cdots}\left(\frac q{1-q}+\frac{q^3}{1-q^3}+\frac{q^5}{1-q^5}+...\right)\\=2q-4q^4+6q^9-8q^{16}+... \end{multline*} It appears in Combinatorial Proofs of q-Series Identities by Robin Chapman.

$\endgroup$
6
$\begingroup$

I propose one of the combinatorial formulas for the Littlewood-Richardson coefficients, $c^\lambda_{\mu\nu} =$ the number of skew semi-standard Young tableaux with shape $\lambda/\mu$ and weight $\nu$ with the Yamanouchi condition.

$\endgroup$
  • 1
    $\begingroup$ That's not a formula in a sense that it does not allow computing LR coeff. faster than via the other standard definitions. $\endgroup$ – Igor Pak Aug 18 '15 at 16:55
  • 1
    $\begingroup$ @IgorPak: True, but this formula establishes that these numbers are non-negative integers, which is not clear from the definition. Furthermore, it was still a major achievement when the first complete proof of this identity was finalized, as this was done 40 years after the formulation of the statement. $\endgroup$ – Per Alexandersson Aug 18 '15 at 17:45
  • 1
    $\begingroup$ Um, no. They were originally defined and studied as multiplicity constants in the tensor product of two GL(n,C) modules. Those are non-negative integers by definition. A combinatorial interpretation came much later indeed, but that speaks to the importance (which I agree with completely), not whether this is a formula akin the HLF. $\endgroup$ – Igor Pak Aug 18 '15 at 23:39
  • $\begingroup$ @IgorPak: Ah, of course, you are right, as multiplicities, it is clear. I was thinking that from the definition in terms of expansion of a product of Schur polynomials, and then, not knowing the representation theory behind, it is mysterious why they are non-negative integers. $\endgroup$ – Per Alexandersson Aug 19 '15 at 0:41
  • 2
    $\begingroup$ I think we agree on everything except "what is a formula". It's not really a formal discussion, but if this is a formula, then so is every theorem in combinatorics. $\endgroup$ – Igor Pak Aug 19 '15 at 1:52
6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Dan, I would call it a formula of analysis. Of course, it is widely used in combinatorics (as many other formulas from analysis.) $\endgroup$ – Fedor Petrov Aug 26 '15 at 10:22
  • $\begingroup$ Fedor, all formulas in asymptotic combinatorics (including the Hardy-Ramanujan formula for p(n), also posted here as an answer) require methods of analysis to derive, so in that sense they are indeed formulas of analysis. However, to say that they are not part of combinatorics would seem to suggest that asymptotic combinatorics is not a part of combinatorics, which seems unfair to me. If a formula says something interesting and profound about permutations or partitions, I would say it is a formula in combinatorics. $\endgroup$ – Dan Romik Aug 26 '15 at 16:41
  • 2
    $\begingroup$ Probably, if we write in the left hand side "number of permutations of a set with $n$-elements", it becomes a matter of asymptotic combinatorics, just like asymptotics of $p(n)$. But with $n!$ (or, say, $\Gamma(n+1)$) it is pure analysis. Why nobody states Stirling formula in such a combinarial way? Because it is a combination of two independent facts: "number of permutations equals $n!$" and astmptotics of $n!$. First fact belongs to combinatorics, the second does not. And most applications do not treat exactly permutations, factorial appears in different ways. $\endgroup$ – Fedor Petrov Aug 26 '15 at 17:54
6
$\begingroup$

Shuffles, stuffles and other dual laws

Mother Formula

All what follows is around the same recursive formula/pattern. \begin{equation} au*bv=a(u*bv)+b(au*v)+\varphi(a,b)(u*v)\quad (0) \end{equation}

The shuffle product appears in many contexts (representation theory, iterated integrals, Hecke algebras, symmetric functions, decomposition of polytopes, theory of languages, of codes, of automata).

It turns out that it can be better understood as a law dual to a comultiplication. These co-operations were introduced, in combinatorics, by a seminal paper of Joni and Rota (S.A. Joni and G.-C. Rota, Coalgebras and bialgebras in combinatorics, Stud. Appl. Math. 61 (1979) 93–139.).

Considering two (non empty) words as card decks $au,bv$ the top cards being respectively $a,b$, the shuffle product of $au$ and $bv$ reads (I do not know how to write the Cyrillic ``Sha'', which is the standard sign for the shuffle, in MathJax, so I use $\sqcup$) \begin{equation} au\sqcup bv=a(u\sqcup bv)+b(au\sqcup v)\quad (1) \end{equation} which is the sum of all possible shuffles between $au$ and $bv$ (two disjoint cases $a$ or $b$ on top).

Formula $(1)$ together with the initialization making neutral the empty word i.e. \begin{equation} w\sqcup 1=1\sqcup w=w \end{equation} defines perfectly the shuffle product.

Now, this law is better understood as "dual". I mean, if you define the natural pairing on the words by $\langle u\mid v\rangle:=\delta_{u,v}$ you get \begin{equation} \langle u\sqcup v\mid w\rangle=\langle u\otimes v\mid \Delta(w)\rangle \end{equation} with \begin{equation} \Delta(w)=\sum_{I+J=[1..|w|]}w[I]\otimes w[J]\quad (2) \end{equation} where $|w|$ stands for the length of $w$ and, for $I=\{i_1,i_2,\cdots i_k\}$ a choice of places (indexed in increasing order $i_1<i_2<\cdots <i_k$), $w[I]$ is the subword \begin{equation} w[I]=w[i_1]w[i_2]\cdots w[i_k] \end{equation} (therefore $\Delta(w)$ is sometimes called the ``unshuffling'' of $w$).

The miracle is that the unshuffling is a morphism i.e. it can be defined letter by letter
\begin{equation} \Delta(a_1a_1a_2\cdots a_n)=\Delta(a_1)\Delta(a_2)\cdots \Delta(a_n) \end{equation} with $\Delta(a)=a\otimes 1+1\otimes a$ for a single letter.

Many other combinatorial deformations/perturbations of the shuffle product follow a similar scheme, let me exemplify two of them.

Stuffle (also called Hoffman's shuffle, quasi-shuffle, sticky shuffle) which appears in many contexts (harmonic sums, lambda rings, quasi-symmetric functions). This time, the set of cards is infinite, more precisely, you have an alphabet $\{y_i\}_{i\in \mathbb{N}_{>0}}$ indexed by non-zero integers. The stuffle law is defined recursively as \begin{equation} w*1=1*w=w\ ;\ y_iu*y_jv=y_i(u* y_jv)+y_j(y_iu*v)+y_{i+j}(u*v)\quad (3) \end{equation} the term $y_{i+j}(u*v)$ is the reason why certain physicists call it ``sticky shuffle'' because, in this case, the cards $y_i,y_j$ stick together.

Here the dual law is again a morphism defined on the letters by \begin{equation} \Delta(y_k)=y_k\otimes 1+1\otimes y_k+\sum_{i+j=k}y_i\otimes y_j \end{equation}

Infiltration and $q$ infiltration Infiltration products can be traced back to the paper of

Chen, Fox and Lyndon, Free differential calculus, IV - The quotient groups of the lower central series" (Ann. Math 65, 163-178, 1958)

and later (1981) to Oschenschläger's work about binomial coefficients

Ochsenschläger, P., Binomialkoeffizenten und Shuffle-Zahlen, Technischer Bericht, Fachbereich Informatik, T. H. Darmstadt. (1981)

Let's define directly the $q$ infiltration (for $q=0$, you get the shuffle and $q=1$ the infiltration)

\begin{equation} w*1=1*w=w\ ;\ au*bv=a(u* bv)+b(au*v)+\delta_{a,b}\,q\,a(u*v)\quad (4) \end{equation}

Again, the dual law is a morphism defined on the letters by \begin{equation} \Delta(a)=a\otimes 1+1\otimes a+q\,a\otimes a \end{equation} and there is a beautiful analogue of formula $(2)$ \begin{equation} \Delta(w)=\sum_{I\cup\, J=[1..|w|]}q^{|I\,\cap\, J|}w[I]\otimes w[J]\quad (5) \end{equation}

A bit more

Endowed with these dual laws (shuffle, stuffle), the free algebra (with coefficients within a $\mathbb{Q}$-algebra) becomes an enveloping bialgebra (and hence a Hopf algebra) whereas, except when $q$ is nilpotent, the infiltration coproduct turns the free algebra into a bialgebra which is NOT a Hopf algebra (due to the presence of non-invertible group-like elements as $(1+qx),\ x\in X$).

$\endgroup$
  • $\begingroup$ In fact there is an enormous source of combinatorial formulas stemming from combinatorial Hopf algebras... $\endgroup$ – მამუკა ჯიბლაძე Sep 2 '15 at 5:39
  • $\begingroup$ @მამუკაჯიბლაძე Thank you. Of course, see only the papers on noncommutative symmetric functions for instance. Here, I wanted to deliver an easy-to-read and transversal account. Note that whereas shuffle and stuffle are Hopf (they are in fact enveloping algebras), infiltration is only a bialgebra. $\endgroup$ – Duchamp Gérard H. E. Sep 2 '15 at 5:45
  • 4
    $\begingroup$ Is combinatorics the dual subject to mbinatorics? $\endgroup$ – Gerry Myerson Sep 2 '15 at 6:05
  • 1
    $\begingroup$ For some connections to physics, "Hopf algebras and Dyso-Schwinger equations" by Weinzierl arxiv.org/abs/1506.09119 $\endgroup$ – Tom Copeland Sep 19 '15 at 19:35
  • 1
    $\begingroup$ The infiltration product appears in fact before the work of Oschenschläger, in a more algebraic framework, in the paper "Free differential calculus, IV - The quotient groups of the lower central series" (Ann. Math 65, 163-178, 1978), of Chen, Fox and Lyndon (Theorem 3.9, page 93). $\endgroup$ – Yannic Oct 6 '15 at 3:20
5
$\begingroup$

Let $P_n$ be a permutation of $1,2,\ldots,n$. Also, suppose $is(P_n)$ and $ds(P_n)$ shows the longest increasing and decreasing subsequences of permutation $P_n$, respectively. So, the Erdős–Szekeres inequality is: $$is(P_n)\times ds(P_n)\geq n\,.$$

Also, the above inequality is best possible and if $n=pq$, we have the equality.

Now, suppose $A_n(p,q)$ shows the total number of permutation of $1,2,\ldots,n$ for which we have $is(P_n)=p$ and $ds(P_n)=q$. then $A_n(p,q)$ is equal to the sum of all $(f^{\lambda})^2$, where $\lambda$ is a partition of $n$ satisfying $\ell(\lambda)=p$ and $\lambda_1=q$. Also, $f^{\lambda}$ can be evaluate by hook-length formula, which is appeared in one of the above answers.

For special case, if $n=pq$, we have: $$A_n(p,q)=\left[\frac{(pq)!}{1^12^2\cdots p^p(p+1)^p\cdots q^p(q+1)^{p-1}(q+2)^{p-2}\cdots (p+q-1)^1}\right]^2.$$

$\endgroup$
5
$\begingroup$

The Sauer–Shelah-Vapnik-Chervonenkis lemma: $$ |C| \le \sum_{i=0}^d \binom{n}{i} ,$$ where $C\subseteq\{0,1\}^n$ and its VC-dimension $d$ is the size of the largest shattered index set $I\subset[n]$, where we say that $I$ is shattered if the restriction of $C$ to $I$ is all of $\{0,1\}^{|I|}$. The bound is tight, achievable, e.g., by $C$ corresponding to all subsets of $n$ of size at most $d$.

For $n\ge d$, we have the simple estimate $\sum_{i=0}^d \binom{n}{i}\le(en/d)^d$. The actual lemma has several proofs, the shortest being via Pajor's lemma, which states that $C$ shatters at least $|C|$ distinct index sets $I$.

$\endgroup$
5
$\begingroup$

The Kruskal-Katona inequality: $$|\partial{\cal F}| \ge {{m_k} \choose {k-1}} + {{m_{k-1}} \choose {k-2}}+ \cdots + {{m_j} \choose {j-1}}.$$

Here ${\cal F}$ is a family of $k$-sets, and $\partial {\cal F}$ is its shadow, namely all sets of size $(k-1)$ contained by some set in $\cal F$. And,

$$|{\cal F}|=m= {{m_k} \choose {k}} + {{m_{k-1}} \choose {k-1}}+ \cdots + {{m_j} \choose {j}},$$ where $m_k > m_{k-1} >\cdots > m_j \ge j >0$.

$\endgroup$
5
$\begingroup$

I don't believe anyone has yet mentioned the Möbius function formula of Hall and Rota, although several answers have referred to formulas in which this formula is an element in a proof.

Specifically, if $x<y$ are elements in a poset $P$, then the formula is $$\mu([x,y]) = \tilde{\chi}(\Delta[x,y]).$$ Here $\Delta[x,y]$ is the order complex of $[x,y]$, the simplicial complex consisting of all chains of elements in $P$ strictly between $x$ and $y$. Of course $\mu$ is the Mobius function (which controls inclusion-exclusion over $P$), and $\tilde{\chi}$ is the reduced Euler characteristic.

This formula was proved by Hall in a 1936 paper. As far as I understand, it was Rota who noticed the connection with Euler characteristics in the paper "On foundations of combinatorial theory I. Theory of Mobius functions". It has since become a cornerstone of topological and poset combinatorics.

Möbius number calculations can often be significantly simplified and/or viewed in a more general context by use of homotopy type and other tools from topology. Two favorite examples of mine: If some element of a lattice $L$ has no complement, then $\Delta L$ is contractible and hence $\mu(L)=0$ (a result of Bjorner and Walker). And Rota's Crosscut Theorem is a special case of the Nerve Theorem.

$\endgroup$
5
$\begingroup$

$$\max (|A+A|,|A\times A|) \ge \frac12 |A|^{4/3} (\log |A|)^{-1/3}.$$

This sum product-relation by Solymosi is one of the highlights of additive combinatorics. Sum-product theorems have many recent applications. Here $A$ is an arbitrary set of positive real numbers and $A+A=\{a+a': a,a' \in A\}$. $A \times A=\{a \cdot a': a,a' \in A\}$.

Let me add two other important formulas from additive combinatorics. The Cauchy-Davenport relation

$$|A+A| \ge 2|A|-1.$$

And the Plünnecke relation

$$|A+A| \le C|A| \implies |kA-\ell A| \le C^{k+\ell} |A|. $$

Solymosi's record was broken several times and the current world record is by George Shakan. See this paper and this Quanta Magazine's article.

enter image description here

$\endgroup$
4
$\begingroup$

$$\def\multichoose#1#2{{\left(\kern-.3em\left(\genfrac{}{}{0pt}{}{#1}{#2}\right)\kern-.3em\right)}} \binom{n}{k} = (-1)^{k} \multichoose{-n}{k}$$

Here $\binom{n}{k}$ is the binomial coefficient "$n$ choose $k$": the number of ways to select $k$ items from a set of $n$. And $\multichoose{n}{k}$ is ``$n$ multichoose $k$'': the number of ways to select $k$ items from a set of $n$, where you are allowed to select the same item multiple times.

Of course, to interpret the above formula you must see each side as a polynomial in $n$. Then it is a straightforward exercise to show that the formula holds. However, this formula is the ur-combinatorial reciprocity result. For more on combinatorial reciprocity, see Stanley's paper: http://dedekind.mit.edu/~rstan/pubs/pubfiles/23.pdf.

$\endgroup$
4
$\begingroup$

$$\frac {\alpha (G)}{n}\le \frac {\lambda_{\min}}{d-\lambda_{\min}}$$

This is Hoffman's bound for the independence number $\alpha (F)$ (namely, the largest number of vertices in an independent set of vertices in $G$), of a $d$-regular graph with $n$ vertices. Here $\lambda_{\min}$ is the smallest eigenvalue of the adjacency matrix of $G$. For more details see e.g. this paper.

$\endgroup$
  • 3
    $\begingroup$ A related inequality is also due to Hoffman and states that $$\chi(G)\geq 1+\frac{\lambda_{max}(G)}{-\lambda_{min}(G)}$$ where $\chi(G)$ is the chromatic number and $\lambda_{max}(G)$ is the largest eigenvalue of the adjacency matrix of $G$. When $G$ is regular, this follows from the inequality above for $\alpha(G)$, but when $G$ is not regular, it does not. Another inequality for $\chi(G)$ is due to Wilf:$$\chi(G)\leq 1+\lambda_{max}(G).$$ $\endgroup$ – Sebi Cioaba Aug 25 '15 at 20:32
4
$\begingroup$

$$1-H(\delta) \le R(\delta) \le H(\frac{1}{2} -\sqrt {\delta (1-\delta)}).$$

This formula describes the state-of-the-art lower and upper bound for the rate of binary codes of length $n$, as $n$ tends to infinity, and minimal distance $\delta n$, $0 < \delta < 1/2$. The lower bound is due to Gilbert (1952). Now better lower bound is known today. The upper bound is by McEliece, Rudemich, Rumsey, and Welsh (MRRW) (1977), who described also an improved upper bound for $\delta \ge 0.273$. No better upper bounds than those discovered by MRRW are known today.

Van Lint's book on the theory of error-correcting codes is a good source. (*)

$\endgroup$
4
$\begingroup$

A parking function is a sequence $(a_1, \ldots, a_n)$ of positive integers such that, if $b_1 \le b_2 \le \cdots \le b_n$ is the increasing rearrangement of the sequence $(a_1, \ldots, a_n)$, then $b_i\le i$.

Theorem. The number of parking functions of length $n$ is $(n+1)^{n-1}$.

Parking functions are related to a host of seemingly unrelated combinatorial objects, such as labeled trees (there is a close connection with Cayley's formula $n^{n-2}$ for the number of labeled trees on $n$ vertices), noncrossing partitions, and hyperplane arrangements (the Shi arrangement in particular). There is even a connection with the $n!$ conjecture mentioned in another answer, in that the action of the symmetric group on the space of parking functions is isomorphic to a certain action on a space of coinvariants. More information may be found in many places, e.g., these slides by Richard Stanley.

$\endgroup$
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$
  • 13
    $\begingroup$ Please make this self-contained by including explicit uses of the formula, as the question requests. $\endgroup$ – Douglas Zare Aug 19 '15 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$ – Max Alekseyev Aug 20 '15 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$ – Douglas Zare Aug 20 '15 at 16:52
3
$\begingroup$

$$(1-\lambda_2)/2\le h(G)\le \sqrt{2(1-\lambda_2)},$$ is the "discrete Cheeger-Buser inequality", relating the spectral gap of the discrete laplace operator to the discrete Cheeger constant of a graph. In particular, it gives the spectral characterization of expander families.

Here $h(G)$ is the expansion of a graph $G$, and $\lambda_2$ refers to the secpnd smallest eigenvalue of the Laplacian of $G$. The inequality on the right is due to Alon-Millman and Tanner. The inequality on the left is by Alon.

$\endgroup$
3
$\begingroup$

I guess this can be counted as infinitary combinatorics. And it is a fundamental formula in choiceless set theory.

$$\aleph_0\leq^*\mathfrak p\iff\aleph_0\leq2^\frak p$$

Namely, given a set $X$ of cardinality $\frak p$, there is a surjection from $X$ onto $\Bbb N$ if and only if there is an injection from $\Bbb N$ into $\mathcal P(X)$. This is a theorem of Kuratowski, and using it we can deduce all sort of things, e.g. if there is an infinite set without a countable subset, then there is one which can be mapped onto $\Bbb N$

Proof. If $A$ is an infinite set without a countable subset, either $A$ can be mapped onto $\Bbb N$, else $\mathcal P(A)$ can be mapped onto $\Bbb N$; however from the formula above, $\mathcal P(A)$ has no countable subset. $\square$

One might wonder what use are sets which have no countably infinite subset. But due to their inherent [Dedekind-]finiteness, they can be used for certain "odd" combinatorial constructions and counterexamples to many theorems which appeal to the axiom of choice.

$\endgroup$
  • $\begingroup$ Infinite sets always have countable subsets, no ? $\endgroup$ – Duchamp Gérard H. E. Sep 1 '15 at 7:52
  • 2
    $\begingroup$ If you assume choice, sure. If you define infinite as Dedekind-infinite (there is a self injection which is not surjective) then also yes. But if you define infinite as not-finite, then it is consistent with the failure of choice there are infinite sets which are not Dedekind-infinite. $\endgroup$ – Asaf Karagila Sep 1 '15 at 8:03
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$
3
$\begingroup$

Read's 1958 beautiful formula for the asymptotic number of 3-regular graphs with n vertices

$$g_3(n) \sim \frac {(3n)! e^{-2}}{(3n/2)!288^{n/2}}.$$

$\endgroup$
  • $\begingroup$ This is for labelled graphs, right? $\endgroup$ – Fedor Petrov Nov 26 '18 at 7:33
3
$\begingroup$

I'm not sure if the Garsia–Haiman $n!$ conjecture (now a theorem) counts as a formula, but it feels like a formula to me. Let $\mu$ be a partition of $n$, and let the coordinates of the cells in the Ferrers diagram of $\mu$ be $\{(p_1,q_1), \ldots, (p_n,q_n)\}$, where $p$ is the row coordinate and $q$ is the column coordinate, indexed from zero, so that the corner cell is $(0,0)$. Define $$\Delta_\mu(x_1,\ldots,x_n,y_1,\ldots,y_n) := \det \pmatrix{x_1^{p_1}y_1^{q_1} & x_2^{p_1} y_2^{q_1} & \cdots & x_n^{p_1} y_n^{q_1} \cr x_1^{p_2}y_1^{q_2} & x_2^{p_2} y_2^{q_2} & \cdots & x_n^{p_2} y_n^{q_2} \cr \vdots & \vdots & \ddots & \vdots \cr x_1^{p_n}y_1^{q_n} & x_2^{p_n} y_2^{q_n} & \cdots & x_n^{p_n} y_n^{q_n} \cr}$$ Then the dimension of the space $\mathscr{H}_\mu$ spanned by all partial derivatives of all orders of $\Delta_\mu$ is $n!$.

The $n!$ conjecture lies at the center of a web of fascinating algebraic combinatorics that features Macdonald polynomials, diagonal harmonics, and Hilbert schemes. Garsia has said that when they were first mapping out a conjectural picture of this corner of the mathematical universe, they fairly quickly realized that the $n!$ conjecture was a crucial linchpin. Although they couldn't immediately prove it, they initially assumed that because the formula was so simple, it would be easy to prove, and they focused their attention on other conjectures. One by one, the other conjectures were proved, and the $n!$ conjecture was left as the surprisingly stubborn nut. It was eventually proved by Haiman using surprisingly delicate arguments from commutative algebra and algebraic geometry. I believe that even today, the only proof is essentially a dimension-counting argument, and that in general there is no known explicit basis for $\mathscr{H}_\mu$ that is indexed by $n!$ combinatorially defined objects.

$\endgroup$
3
$\begingroup$

The BEST Theorem (https://en.wikipedia.org/wiki/BEST_theorem) for the number of Eulerian circuits of an Eulerian directed graph $G$: $$ec(G) = t_w(G) \cdot \prod_{v\in V} (\mathrm{deg}(v)-1)!,$$ where $t_w(G)$ is the number of arborescences rooted at any fixed vertex $w\in G$. The number $t_w(G)$ can be computed as a determinant thanks to (a directed graph version of) the matrix-tree theorem, already mentioned in another answer.

This is a remarkable formula because, like many other formulas mentioned in answers to this question, it is right "on the border" of what is computationally tractable. For instance, as mentioned in the Wikipedia article above, the problem of counting Eulerian circuits in an undirected graph is by contrast #P-complete.

(Another very similar "on the border" result in enumeration in graph theory is the Kasteleyn method for computing perfect matchings of a planar graph, compared to the difficulty of computing perfect matchings of an arbitrary graph, which should be an answer if it is not already.)

$\endgroup$
2
$\begingroup$

What about the Erhart's polynomial? Is the statement that, for a $d$-dimensional polytope in $\mathbb{R}^n$ and $t > 0$: $$\#(tP \cap \mathbb{Z}^n) = \sum_{i=0}^d a_i t^{i},$$ for some $a_i \in \mathbb{Q}$, considered a "formula"? This yields Pick's formula for a $2$-d integer polygon: $$A = \#\mbox{int}(P \cap \mathbb{Z}^2) + \frac{\partial(P \cap \mathbb{Z}^2)}{2} -1.$$

$\endgroup$
  • 1
    $\begingroup$ Along these lines, Stanley's reciprocity theorem certainly is a(n important) combinatorial formula: en.wikipedia.org/wiki/Stanley%27s_reciprocity_theorem $\endgroup$ – Sam Hopkins Sep 2 '15 at 14:46
  • $\begingroup$ @Campello, could you remove the question marks and flesh this out? Perhaps you could use "New models of Veneziano amplitudes: Combinatorial, symplectic, and supersymmetric aspects" by Kholodenko (arxiv.org/abs/hep-th/0503232) to explicitly state the relation between the interior lattice points and the boundary points for order polytopes encoded by the Ehrhart polynomials and their connections to some fascinating physics and mathematical analysis (period integrals), and sketch some history. $\endgroup$ – Tom Copeland Sep 19 '15 at 18:07
  • $\begingroup$ Other interesing connections: "Characteristic classes of singular toric varieties" by Maxim and Schuemann arxiv.org/abs/1303.4454. $\endgroup$ – Tom Copeland Nov 11 '15 at 21:15
  • $\begingroup$ See also "Stringy Chern classes of singular toric varieties and their applications" by Batyrev and Schaller arxiv.org/abs/1607.04135 $\endgroup$ – Tom Copeland Nov 5 '17 at 17:05
  • $\begingroup$ Shouldn't it be $\mathrm{int}(P)\cap\Bbb Z^2$ rather than $\mathrm{int}(P\cap \Bbb Z^2)$ and $\partial P \cap\Bbb Z^2$ rather than $\partial(P\cap \Bbb Z^2)$? $\endgroup$ – M. Winter Feb 9 at 0:54
2
$\begingroup$

Let $r_k(n)$ denotes the size of the largest cardinality of a subset $A$ of $\{1,2,\dots,n\}$, such that $A$ does not contain a k-term arithmetic progression. The following formula describes the state of knowledge for $k=3$. For references and related bounds see this Wikipedia article.

$$ 2^{-8\sqrt {\log n}} \le \frac {r_3(n)}{n} \le C \frac { (\log \log n)^4}{\log n}$$

$\endgroup$
2
$\begingroup$

Davis-Slepian-Polya formula for the number of simple graphs on $n$ nodes $$ \frac{1}{n!} \sum_{j_1+2j_2+\cdots+n j_n=n}\frac{n!}{\prod\limits_{k=1}^n k^{j_k} j_k!} 2^{\displaystyle \frac{1}{2}\left( \sum_{k=1}^n k j_k^2 - \sum_{\text{ $k$ odd}} j_k \right) + \sum_{k=1}^n \sum_{i=1}^{k-1} (k,i) j_k j_i}. $$

$\endgroup$
2
$\begingroup$

The Lindström–Gessel–Viennot lemma is a very powerful tool for proving all kinds of combinatorial product formulas. It says that if $G$ is a directed acyclic edge-weighted graph, and $M$ is the square matrix whose rows are indexed by some set of vertices $\{u_1,\ldots,u_n\}$ of $G$ and whose columns are indexed by some other set of vertices $\{v_1,\ldots,v_n\}$, and whose $(u,v)$th entry is the sum $\sum_{p\colon u \to v}\omega(p)$ of the weights of all paths connecting $u$ to $v$, then the determinant of $M$ is $$ \mathrm{det}(M)= \sum_{(P_1,\ldots,P_n)\colon A\to B} \mathrm{sign}(\sigma(P))\prod_{i=1}^{n}\omega(P_i),$$ where the sum is over all non-intersecting (i.e., vertex-disjoint) tuples $(P_1,\ldots,P_n)$ of paths, where $P_i$ is a path from $u_i$ to $v_{\sigma(i)}$ for the corresponding permutation $\sigma(P)$. The lemma is especially useful when one can argue (e.g., because of planarity) that the only such non-intersecting tuples must connect $u_i$ and $v_i$ (i.e., $\sigma(P)$ must be the identity).

This lemma can be used to prove that the combinatorial and determinantal definitions of the Schur functions agree. It can also be used to give a very nice proof of MacMahon's product formula for the number of plane partitions in a box (an earlier answer to this question).

$\endgroup$
1
$\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$
  • 5
    $\begingroup$ Is it just me or is the closed formula a lot nicer than the asymptotic one? $\endgroup$ – darij grinberg Sep 2 '15 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 http://www.businessinsider.com/17-equations-that-changed-the-world-2014-3?IR=T

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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