146

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;

YCor
  • 60,149
Gil Kalai
  • 24,218
  • 18
    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. – Suvrit Aug 18 '15 at 02:11
  • 2
    Does this allow for set theoretic infinitary combinatorics? :-) – Asaf Karagila Aug 18 '15 at 20:13
  • Dear Asaf, as I see it, we want important formulas representing major progress in combinatorics; so infinitary combinatorics applies as well. As I see it: it need to be a formula, it need to be stated explicitly, and it need to be related to important research advances. Maybe we should avoid classic famous very well-known formulas, so I would regard $2^\lambda >\lambda$ as too basic to be included. – Gil Kalai Aug 18 '15 at 20:36
  • In short, Asaf, my answer is YES! – Gil Kalai Aug 19 '15 at 06:24
  • 4
    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. – Victor Protsak Aug 19 '15 at 06:32
  • Gil, thank you for the reply. I'll try to think about something. Of course $\lambda<2^\lambda$ is too basic and quite uninteresting from a research point of view. But there is new things to be said about infinitary graphs and the like. – Asaf Karagila Aug 20 '15 at 10:58
  • There must be at least one entry concerning matroids! Unfortunately I don't know enough to choose the best one (in terms of representativeness)... – მამუკა ჯიბლაძე Aug 24 '15 at 10:56
  • 1
    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. – Gil Kalai Aug 24 '15 at 10:59
  • 1
    I'm surprised nobody's mentioned the Sauer-Shelah-Vapnik-Chervonenkis lemma! If it's relevant, I can post it as an answer. [Or better yet, Pajor's lemma -- from which the former readily follows.] – Aryeh Kontorovich Aug 25 '15 at 16:31
  • Thanks Aryeh, There are three conditions for an answer, it needs to be combinatorics (widely interpreted), it needs to be important, and it needs to be (already) in a form of a formula. – Gil Kalai Aug 25 '15 at 16:36
  • Dear Aryeh, I guess that if one can present nicely an important result in a novel way as a formula, this should be ok, but I worry this will be too inclusive.. Certainly the Sauer-Shelah-Vapnik-Chervonenkis lemma is very fundamental.https://gilkalai.wordpress.com/2008/09/28/extremal-combinatorics-iii-some-basic-theorems/ – Gil Kalai Aug 25 '15 at 18:21
  • Regarding Cauchy's identity that Survit mentioned, see http://mathoverflow.net/questions/114275/generalization-of-cauchys-identity . (I am not sure about the name "Cauchy's identity" while referring to Schur functions.) – Gil Kalai Sep 07 '15 at 04:19
  • 2
    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? :-) – Asaf Karagila Sep 07 '15 at 13:12
  • Assaf, done. I'd love to see a formula expressing some Ramsey relation for infinite cardinals or ordinals, but I wouldn't know myself which one to choose. – Gil Kalai Sep 11 '15 at 11:36
  • @Suvrit: please could you give a reference (or a sketch) for how the Cauchy identity follows from the MacMahon Master Theorem? – Mark Wildon Sep 12 '15 at 13:33
  • @MarkWildon: my comment "may follow" was grounded in the observations of a paper by Goulden-Jackson (1992); see for instance Theorem 1 cited in http://www.fmf.uni-lj.si/~konvalinka/gj.pdf --- that is the basis of my imprecise claim of "may" ... hope this helps. – Suvrit Sep 12 '15 at 14:29
  • Perhaps the beautiful Cauchy identity deserves a special answer. – Gil Kalai Sep 12 '15 at 15:27
  • Gil, I added a formula in one of my answers to stress the enumerative geometry of associahedra, as an avatar of the general formula, and I wonder if that formula or a more compact one would be appropriate in your very nice illustrations under geometric combinatorics. Entirely up to you, of course. – Tom Copeland Oct 07 '15 at 23:10
  • Dear Tom, Thanks for the addition. As there are few answers that fits to more than one topic and answers that contain more than one formula I represented in the illustration each answer by a single formula and interested viewers can, of course, jump to the full answer. – Gil Kalai Oct 08 '15 at 12:47
  • You've explicitly excluded elementary formulas---but one of the most important of all combinatorial formulas (for non-combinatorialists, like me) is the equation for the coefficients of Pascal's triangle, $C(n,k) + C(n,k+1) = C(n+1,k+1)$; even better, it has a one-line proof (coefficients of $(1+x)^{k+1}$). – David Handelman Dec 06 '16 at 14:59
  • Thanks David. I suppose this is indeed too elementary... (Probably we want research level formulas that will be new to more than 50% of combinatorialists and 75 percents of mathematicians in other areas.) – Gil Kalai Dec 06 '16 at 15:26
  • @AsafKaragila, regarding infinite combinatorics, do you think the identity ${\bf p}={\bf t}$ should be added? – Gil Kalai Sep 19 '17 at 21:06
  • @Gil: I'm not sure if I would have called it combinatorics, actually. These are characteristics of the continuum. – Asaf Karagila Sep 20 '17 at 04:09
  • From https://gowers.wordpress.com/2017/09/19/two-infinities-that-are-surprisingly-equal/ It looks like a sort of infinite combinatorics. Let it just be mentioned as a comment. – Gil Kalai Sep 20 '17 at 05:28

66 Answers66

58

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.

Fedor Petrov
  • 102,548
Mark Wildon
  • 10,750
  • 3
  • 44
  • 70
  • This is certainly a great formula! – Gil Kalai Aug 17 '15 at 10:18
  • 2
    I'm sorry but as an outsider I fail to see the significance here. What results did it unify? – Vít Tuček Sep 06 '15 at 21:08
  • 7
    For a start, all the hundreds of combinatorial interpretations of the Catalan number $C_n$ (see Stanley, Enumerative Combinatorics, volume II and http://www-math.mit.edu/~rstan/ec/catadd.pdf). For instance $C_n$ is the number of walks with steps $(1,1)$ and $(1,-1)$ from $(0,0)$ to $(2n,0)$ that stay above the $x$-axis; more generally, $f^{(a,b)}$ is the number of walks from $(0,0)$ to $(a+b,a-b)$ with this property. – Mark Wildon Sep 08 '15 at 11:19
  • See also http://summit.sfu.ca/item/14554 "On tree hook length formulae, Feynman rules, and B-series" by Jones. – Tom Copeland Oct 15 '15 at 17:34
41

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.

  • 2
    This is also called Euler transform and Riddell formula: http://mathworld.wolfram.com/EulerTransform.html – Max Alekseyev Aug 18 '15 at 18:52
  • @MaxAlekseyev Thanks, I'll have a look and find connections. – Duchamp Gérard H. E. Aug 18 '15 at 19:21
  • @MaxAlekseyev I had a look and added an item (+1). – Duchamp Gérard H. E. Aug 19 '15 at 04:23
  • 2
    Cf. also http://arxiv.org/abs/0910.0695 and the related http://arxiv.org/abs/1205.2097 on cumulants. – Tom Copeland Aug 26 '15 at 07:09
  • 1
    @TomCopeland The paper seems gogeous. In my answer, the intention was just to "tell the story" of the exponential formula, I did not put any reference (otherwise, I am shure I would have missed a lot, and mainly because of Gilles rule 2). Thanks for the paper, I'll have a look and, if I understand it, I'll mention the subject in the list of connections. – Duchamp Gérard H. E. Aug 26 '15 at 07:35
  • On a historical note: Comtet mentions Prouhet or Pourchet on page 220 of his book Adv. Comb. (Reidel, 1974) in relation to the Faa di Bruno formula. I couldn't track that down. Do you know of his contribution? – Tom Copeland Aug 26 '15 at 07:53
  • @TomCopeland It is not in Comtet's french version, I'll have a look at the english one today. – Duchamp Gérard H. E. Aug 26 '15 at 08:57
  • For connections between the cycle index formula for the symmetric group and characteristic classes, see http://arxiv.org/pdf/1508.04356v1.pdf "Equivariant characteristic classes of external and symmetric products of varieties" by Maxim and Schurmann. (There is actually a connection through the Riemann zeta function at positive integer values to fractional calculus, as well, i.e., translations of the reciprocal factorials.) – Tom Copeland Sep 07 '15 at 21:30
  • And these cycle index partition polynomials can be related to the raising operators of the special Sheffer Appell sequences. – Tom Copeland Sep 07 '15 at 23:03
  • @TomCopeland [There is actually a connection through the Riemann zeta function at positive integer]--> is it zeta or polyzeta ? – Duchamp Gérard H. E. Sep 08 '15 at 02:16
  • 1
    @Duchamp, both. See notes and refs http://mathoverflow.net/questions/111165/riemann-zeta-function-at-positive-integers-and-an-appell-sequence-of-polynomials – Tom Copeland Sep 08 '15 at 03:19
  • @TomCopeland Thank you. This discussion and your Appell polynomials seem very interesting, I'll return to this when I have more time. – Duchamp Gérard H. E. Sep 08 '15 at 05:57
  • 1
    The two examples correspond to http://oeis.org/A036039 and http://oeis.org/A036040. A third is http://oeis.org/A130561. – Tom Copeland Sep 26 '16 at 21:14
  • The first example can be related simply to the Chern class (or form, http://en.wikipedia.org/wiki/Chern_class) and the Pontryagin class (http://oeis.org/A231846). – Tom Copeland Oct 11 '16 at 03:23
  • Been a while (our old chat--link under my answer-is frozen), but I found a ref to one of the two prime suspects Prouhet in "The origins of combinatorics on words" by Berstel and Perrin. They reference Eugene Prouhet, Memoire sur quelques relations entre les puissances des nombres, C.R. Acad. Sci. Paris 33 (1851) 255. – Tom Copeland Mar 08 '24 at 17:25
40

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

Somos
  • 2,464
Fedor Petrov
  • 102,548
40

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.

Sam Hopkins
  • 22,785
30

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

Joseph O'Rourke
  • 149,182
  • 34
  • 342
  • 933
  • Is this actually a formula in combinatorics? I don't recall them being valid for simplicial complexes... – darij grinberg Aug 18 '15 at 19:56
  • @darijgrinberg: The Euler characteristic holds for a simplicial sphere, i.e., a simplicial complex homeomorphic to a $d$-sphere. – Joseph O'Rourke Aug 18 '15 at 20:26
  • But... this is still not combinatorics, is it? Or is homological equivalence enough? – darij grinberg Aug 18 '15 at 20:30
  • 3
    Dear Darij, This is a formula in combinatorics even in a very strict sense since it applies to Eulerian (d-1)-dimensional simplicial complexes, namely to complexes so that links of faces have the same Euler combinatorics as a sphere of the same dimension. Moreover relations between face numbers of polytopes, and even of complexes described by topological conditions are regarded part of combinatorics. – Gil Kalai Aug 18 '15 at 21:11
  • Ah, I forgot the Eulerian form -- that's nice (though probably a case of Möbius inversion?). – darij grinberg Aug 19 '15 at 18:10
  • 1
    Acually, I am not sure how Euler/Dehn-Somerville are related to Möbius inversion. The Dehn Somerville formula has a compact presentation as $$h_i=h_{d-i},$$ where $$\sum f_{i-1}(x-1)^{d-i} = \sum h_i x^{d-i}.$$ – Gil Kalai Sep 05 '15 at 20:13
  • 1
    With the $h$-numbers we can present a few other important formulas for simplicial convex polytopes. $h_2 \ge h_1$ is the lower bound theorem; $h_k \le {{n-d+k-1} \choose {k}}$ is the upper bound theorem; $h_k \le h_{k+1}$ for $k \le [d/2]$ is the generalized lower bound theorem. The g-theorem consists of the Dehn-Somerville relation, the generalized lower bound inequality and additional system of non-linear inequalities. All these results extend or conjecturally extend (at times, with appropriate definition of $h_i$) to simplicial spheres, general polytopes, and more. – Gil Kalai Sep 08 '15 at 16:48
26

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.

Ofir Gorodetsky
  • 13,395
  • 1
  • 60
  • 75
  • 6
    Um, we gave a truly bijective proof of MMT in this paper, section 2. Sorry for the self-promotion. http://arxiv.org/abs/math/0607737 – Igor Pak Aug 24 '15 at 20:03
  • Xavier Viennot has showed that this formula could be derived from the theory of heaps which are actually in bijection with acyclic orientation of graphs – vidyarthi Apr 11 '19 at 14:08
  • The proof using "heaps" is due to Cartier and Foata, https://www.mat.univie.ac.at/~slc/books/cartfoa.html. Viennot's theory of heaps is equivalent to the Cartier-Foata theory of free partially commutative monoids. – Ira Gessel Feb 09 '20 at 14:49
  • See Unitary Symmetry and Combinatorics by Louck for relations to physics and ladder operators. – Tom Copeland Apr 30 '21 at 20:38
22

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.

  • 5
    This has a more-or-less equivalent interpretation in terms of boson-fermion correspondence. The left side is the character of an infinite dimensional spinor representation, while the right side is the character of bosonic strings compactified on a circle. There is an isomorphism of the respective vertex superalgebras, and this yields an equality of characters. – S. Carnahan Aug 17 '15 at 17:16
  • @S.Carnahan Could you recommend a good place to read about such stuff? – მამუკა ჯიბლაძე Aug 17 '15 at 17:24
  • 3
    I wish I knew a good reference that described the physical picture in detail, with $z$ giving momentum and $q$ giving energy. For the mathematical side, I would first suggest "Bombay lectures" by Kac, Raina, and Rozhkovskaya. Then there is the last chapter of Kac's "Infinite dimensional Lie algebras". Finally, there is section 5.3 of Frenkel and Ben-Zvi's "Vertex Algebras on Algebraic curves". – S. Carnahan Aug 17 '15 at 17:40
  • 8
    The Jacobi triple product identity was proved bijectively by Sylvester (see my partition bijections survey). Reviewing the literature I found about 11 proofs by others, all equivalent but phrased differently. Your answer suggests that "particle sea" proof is somehow different and modern. It is in fact equivalent to the original Sylvester's bijection. – Igor Pak Aug 18 '15 at 16:53
  • @IgorPak For me the most exciting part is connection with physics (which I really would like to understand, I don't claim I understand it). – მამუკა ჯიბლაძე Aug 18 '15 at 20:25
  • Yeah, well - this identity is truly classical and extremely important in Partition Theory (see also Hardy & Wright Number Theory book on this). Your statement is sort of like saying "matrices are important especially because SU(3) helps explain quarks". True, but a minority view. – Igor Pak Aug 18 '15 at 23:45
  • @IgorPak I actually meant opposite direction, so your analogy would be correct if some proof of some fundamental fact about matrices could be made involving ideas from quantum chromodynamics. In any case, I find the interpretation of partitions as ensembles of random particles with almost all negative energy levels occupied very intriguing, fruitful and would very much like to see anything written about it. – მამუკა ჯიბლაძე Aug 19 '15 at 15:12
  • 2
    @მამუკაჯიბლაძე: If this interpretation is what I think it is (with physical interpretations, I can never tell), then it is well-known under the names "edge sequences", "Maya diagrams" and others (the "abacus" usually stands for the edge sequence subdivided into length-$p$ blocks); see §2 in van Leeuwen's http://wwwmathlabo.univ-poitiers.fr/~maavl/pdf/edgeseqs.pdf . – darij grinberg Aug 20 '15 at 17:41
  • @IgorPak another "different and modern proof" is the probabilistic proof in the paper "Product blocking measures and a particle system proof of the Jacobi triple product" by Balasz and Bowen, see here. Not sure if it's already on your list. – Dan Romik Jan 12 '24 at 00:07
22

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

Gil Kalai
  • 24,218
  • It's worth mentioning that this is one of several amazing formulas related to alternating sign matrices, plane partitions, and symmetry classes thereof, many of which have generalizations. What makes the formulas particularly amazing is that, despite their simplicity and similarity to each other, they (mostly) do not admit a unified proof, suggesting that we still don't fully understand why these formulas are true. – Timothy Chow Aug 09 '19 at 14:30
18

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

Moh514
  • 451
  • 4
    The real statement should be something like "the number of spanning trees of $G$ is any entry of the adjugate matrix of $G$". The eigenvalues have little to do with this, and division by $n$ feels wasteful. – darij grinberg Aug 18 '15 at 19:49
  • @darijgrinberg: I agree; also, in particular, this is described much better both in the question and in the answers here: http://mathoverflow.net/questions/73385/the-matrix-tree-theorem-without-the-matrix – Suvrit Aug 19 '15 at 02:07
  • 2
    I would represent the matrix tree theorem as: $$\kappa (G) = det (L^-(G)(L^-(G))^{tr}).$$ Here $\kappa (G)$ is the number of spanning trees and $L^-(G)$ is the reduced Laplacian. (The Laplacian with one row deleted). Referring to the determinant rather than eigenvalues is relevant to the proof of the theorem. – Gil Kalai Aug 19 '15 at 06:09
  • @GilKalai: Shouldn't your $L^-(G)$ rather be some kind of reduced incidence matrix? Otherwise it looks like you're getting the square of $\kappa(G)$. – darij grinberg Aug 20 '15 at 13:37
  • Upi are correct! – Gil Kalai Aug 20 '15 at 14:19
  • @darijgrinberg sometimes this formula with eigenvalues is also useful. – Fedor Petrov Jun 12 '20 at 22:18
16

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.

16

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

Dan Romik
  • 2,480
15

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.

Mark Wildon
  • 10,750
  • 3
  • 44
  • 70
Dan Romik
  • 2,480
15

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.

13

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.

knsam
  • 1,127
12

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

Gil Kalai
  • 24,218
12

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

Max Alekseyev
  • 30,425
12

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

Gil Kalai
  • 24,218
  • Is it a combinatorics formula? Isn't it affine geometry, ℝly? – Incnis Mrsi Aug 23 '15 at 13:17
  • 1
    Dear Incnis, Yes it is! Zaslavsky's formula is a very important formula in enumerative combinatorics, as well as geometric combinatorics, and the basis for important developments in topological combinatorics. – Gil Kalai Aug 23 '15 at 16:15
11

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.

Manfred Weis
  • 12,594
  • 4
  • 34
  • 71
Ido
  • 101
11

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:

Anurag
  • 1,157
11

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?

Dan Romik
  • 2,480
  • 2
    See Proposition 1.3.3 in van Leeuwen's http://www-math.univ-poitiers.fr/~maavl/pdf/foata-fest.pdf for the simplest proof of $( * )$. The simplicitly of this proof suggests that the RSK algorithm is actually deeper than $( * )$. – darij grinberg Aug 30 '15 at 23:48
  • 1
    Thanks for the reference. Yes, it is a very nice proof. The same proof appears in the paper "On the relations between the numbers of standard tableaux" by Rutherford (Proc. Edinburgh Math. Soc. 7 (1942), 51-54; available here. Years ago I tried to understand the connection between this proof and the Robinson-Schensted proof. I think they are equivalent (the induction hides a recursive map that is essentially a R-S insertion step) but don't remember the details. – Dan Romik Aug 31 '15 at 00:39
11

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

Gil Kalai
  • 24,218
10

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

Max Alekseyev
  • 30,425
10

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

Max Alekseyev
  • 30,425
10

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.

Tom Copeland
  • 9,937
  • Thanks for the rich connections. We discovered (on our side, using functional analysis and ignoring, I admit, all these connections) the charm and combinatorial richness of the "compositional" one-parameter groups in combinatorial physics http://arxiv.org/abs/quant-ph/0401126 "One-parameter groups and combinatorial physics", one can notice that the matrix $S(n,k)$ which corresponds to the transformation $f\rightarrow h,\frac{d}{dz}[f]$ (with respect to the monomials $\frac{z^n}{n!}$) possesses the Sheffer property as the one of the exponential formula (my answer below). – Duchamp Gérard H. E. Aug 25 '15 at 15:55
  • @Duchamp, thanks, I had actually missed that particular ref, but have been aware of your group's numerous, excellent contributions with the emphasis on relations to quantum physics. – Tom Copeland Aug 25 '15 at 22:33
  • @ TomCopeland Thanks, I made a connection in my answer to yours by means of the Sheffer property (of course, not all Sheffer matrices are related to graphs). – Duchamp Gérard H. E. Aug 25 '15 at 23:07
  • @Duchamps, I made the connection to binomial Sheffer sequences explicit and referenced a Cayley-Comtet tree rep. – Tom Copeland Aug 26 '15 at 07:00
  • OK, I am at the institute and am looking to the "Advanced Comb." (Duchamp had no final "s" :) – Duchamp Gérard H. E. Aug 26 '15 at 10:08
  • 1
    @Duchamp, for Pourchet note see https://books.google.com/books?id=PJzuCAAAQBAJ&pg=PA220&lpg=PA220&dq=comtet+faa+di+bruno+pourchet&source=bl&ots=FaagQD6xv-&sig=RJ2zyaXsh0TNaED2kEGgPrqWxo8&hl=en&sa=X&ved=0CDIQ6AEwAmoVChMIgJney7bHxwIV0jWICh0fMQbg#v=onepage&q&f=false – Tom Copeland Aug 26 '15 at 19:01
  • See also "Hopf monoids and generalized permutahedta" by Marcelo Aguiar, Federico Ardila for recent extensions of these ideas https://arxiv.org/abs/1709.07504 – Tom Copeland Mar 27 '18 at 16:16
  • The Taylor series for the inverse function follows, naturally, from the formula with $z = h^{-1}(w)$. – Tom Copeland Mar 27 '18 at 16:36
  • See also my blog post "Pre-Lie algebras, Cayley's analytic trees, and mathemagicla forests" https://tcjpn.wordpress.com/2018/07/10/pre-lie-algebra-and-cayley-trees/ – Tom Copeland Jul 13 '18 at 20:32
  • Re the chat discussion with Duchamp (link above): Been a while but I found a ref to the prime suspect Prouhet in "The origins of combinatorics on words" by Berstel and Perrin. They reference Eugene Prouhet, Memoire sur quelques relations entre les puissances des nombres, C.R. Acad. Sci. Paris 33 (1851) 255. – Tom Copeland Mar 08 '24 at 17:16
  • I have been a bit away.Thank you for Prouhet's reference, I'll check. – Duchamp Gérard H. E. Mar 09 '24 at 05:49
10

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.

Dan Romik
  • 2,480
  • Dan, I would call it a formula of analysis. Of course, it is widely used in combinatorics (as many other formulas from analysis.) – Fedor Petrov Aug 26 '15 at 10:22
  • 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. – Dan Romik Aug 26 '15 at 16:41
  • 2
    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. – Fedor Petrov Aug 26 '15 at 17:54
10

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

9

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.

9

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.

Max Alekseyev
  • 30,425
9

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.

Gil Kalai
  • 24,218
  • 2
    “The affiliation listed on Bose’s paper is the Institute of Statistics, University of North Carolina. Before taking up residence in the U.S. in 1948, Bose worked at the Indian Statistical Institute in Calcutta. One of the most influential combinatorialists of the decades to come, Bose was forced to become a statistician by the lack of employment chances in mathematics in his native country. A pure mathematician hardly in disguise, he reared generations of combinatorialists ... – Anurag Aug 24 '15 at 15:52
  • 2
    ... His students at Chapel Hill included D. K. Ray-Chaudhuri, a name that together with his student R. M. Wilson (so, may be a grandson of Bose?) will appear several dozen times on these pages for their far reaching extension of Bose’s method.” – pg. 77, Linear Algebra Methods in Combinatorics by Babai and Frankl. – Anurag Aug 24 '15 at 15:53
  • 3
    In 1975, Ray-Chaudhuri and Wilson generalized Fisher's inequality and showed that in a $t-(v,k,\lambda)$ design with $t\geq 2s, v\geq k+s$, one must have that $$b\geq {v\choose s}$$. See Van Lint and Wilson's book: https://books.google.com/books?id=5l5ps2JkyT0C&pg=PA222&lpg=PA222&dq=ray-chaudhuri%E2%80%93wilson+theorem+van+lint+and+wilson&source=bl&ots=wUUQ06IUoK&sig=lQ6xFjl-CYSfpcQqq2pZnbG8rjI&hl=en&sa=X&ved=0CDgQ6AEwBGoVChMIudP_1qPFxwIVSzY-Ch3gUQud#v=onepage&q=ray-chaudhuri%E2%80%93wilson%20theorem%20van%20lint%20and%20wilson&f=false – Sebi Cioaba Aug 25 '15 at 22:29
9

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.

Gil Kalai
  • 24,218
9

Tutte's formula (circa 1963) for the number of rooted planar maps with $n$ edges: $$\#M_n = \frac{2}{n+3}3^nC_n$$ where $C_n = \frac{1}{n+1}\binom{2n}{n}$ is the $n$th Catalan number. This is a surprisingly simple formula. Moreover, this formula is the beginning of an important story about universal $2$-dimensional random structures because the limit of the uniform random planar map is the so-called "Brownian map" which has seen a lot of attention in the last ~10 years. As such it is related to topics like quantum gravity. Note, however, that Tutte used generating function techniques to prove the above formula whereas the scaling limit phenomena are based off bijective techniques that came later (80s-90s).

See these notes for some more details: https://arxiv.org/abs/1101.4856.

Tutte's theory of counting planar maps and triangulations is a true festival of formulas. Here is the original formula (given above in a slightly different form) of Tutte for rooted planar maps and another one from the paper A new branch of enumerative graph theory

enter image description here

Answer by Sam Hopkins

Sam Hopkins
  • 22,785
9

An elegant product-sum identity, involving the symmetric groups $S_n$ on $n$ letters, and parametrized by a real number $r$, is Florentino's identity: $$ 1+\sum_{n\geq1}\sum_{\sigma\in S_{n}}\frac{y^{n}}{n!}{1 \over \det(I_{n}-xM_{\sigma})^{r}}=\ \prod_{k\geq0}(1-yx^{k})^{-\binom{k+r-1}{k}}, $$ where $M_{\sigma}$ is the $n\times n$ permutation matrix of $\sigma\in S_{n}$, and $I_n$ the identity matrix of the same size. It is valid on the formal power series ring ${\mathbb R}[[x,y]]$. This imples Molien's formula for the Hilbert-Poincaré series of the ring of $S_n$ invariants polynomials in $n$ variables: $$ \frac{1}{n!}\sum_{\sigma\in S_{n}}\frac{1}{\det(I_{n}-xM_{\sigma})}=\prod_{k=1}^{n}\frac{1}{1-x^{k}}, $$ as this is the coefficient of $y^n$ in the former series, when $r=1$.

There are also multivariable versions of Florentino's identity. One of these gives a new expression for the basic hypergeometric series $_{2}\phi_{1}$ in the form: $$ _{2}\phi_{1}(\frac{1}{x_{1}},\frac{1}{x_{2}};\,y;\,q;\,yx_{1}x_{2}) \, = \,\, 1+\sum_{n\geq1}\frac{y^{n}}{n!}\sum_{\sigma\in S_{n}}\frac{\det[(I_{n}-x_{1}M_{\sigma})(I-x_{2}M_{\sigma})]}{\det(I_{n}-qM_{\sigma})} $$ The proofs of these identities are in the article Plethystic exponential calculus and characteristic polynomials of permutations, and use the so-called plethystic exponential.

Hexhist
  • 83
8

$$\zeta(3)={5\over2}\sum_{n=1}^{\infty}{(-1)^{n-1}\over n^3{2n\choose n}}$$ was the starting point for Apéry's proof of the irrationality of $\zeta(3)$. [OK, so it's Number Theory, not combinatorics --- but, look! it has a binomial coefficient in it!]. Here is Alf van der Poorten's report.

psmears
  • 255
Gerry Myerson
  • 39,024
8

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.

Max Alekseyev
  • 30,425
8

$$\Theta (C_5)=\sqrt 5.$$

This is the formula by Lovasz for the Shannon capacity of the cycle of length 5.

The Shannon capacity of a graph $\Theta (G)= \lim_{n \to \infty}(\omega(G^n))^{1/n}$, where $\omega (G)$ is the largest size of an independent set of vertices in $G$, and $G^n$ is the $n$-fold strong product of $G$. A key to Lovasz' proof was the introduction of a new spectral parameter $\theta (G)$, and a proof that $\Theta (G) \le \theta (G)$.

Gil Kalai
  • 24,218
7

$$\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: Combinatorial reciprocity theorems.

Sam Hopkins
  • 22,785
7

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

7

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.

  • Here is a post about it (in a simpler form) https://gilkalai.wordpress.com/2012/01/18/a-theorem-about-infinite-cardinals-everybody-should-know/ – Gil Kalai Aug 19 '15 at 18:02
  • 2
    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})^+$. – Asaf Karagila Aug 21 '15 at 23:50
  • @Asaf Karagila What's wrong with max( , ) wherever we have total ordering? – Incnis Mrsi Aug 23 '15 at 13:21
  • 1
    @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. – Asaf Karagila Aug 23 '15 at 13:23
  • 4
    @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. – Ramiro de la Vega Aug 24 '15 at 11:12
  • I think that this is a great formula! I wrote about it (a variant) here https://gilkalai.wordpress.com/2012/01/18/a-theorem-about-infinite-cardinals-everybody-should-know/ and it is a "definite" formula except for the 4 that maybe can be replaced by 1. – Gil Kalai Jan 21 '17 at 12:29
7

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

Gil Kalai
  • 24,218
7

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.

Timothy Chow
  • 78,129
7

A beautiful and deep formula I learned about from Ken Ono is the Nekrasov-Okounkov-Westbury formula: $$ \prod_{n\ge 1} (1-q^n)^{z-1}= \sum_{\lambda} q^{|\lambda|}\ \prod_{\square\in\lambda} \left(1-\frac{z}{h(\square)^2}\right)\ . $$ Here, $\lambda$ is summed over all integer partitions of arbitrary weight. The product over $\square$ is over all boxes of the Ferrers diagram corresponding to $\lambda$. Finally, $h(\square)$ denotes the hook length at the position given by the box $\square$. The article by Nekrasov-Okounkov is here. The one by Westbury is here.

I am not aware of an elementary proof for this identity. The case $z=2$ is Euler's Pentagonal Number Theorem.

  • 1
    A nice simplificarion of Nekrasov-Okounkov formula (replacing the product over all boxes, by a product over only the boundary boxes of the Young diagram) is given in Heim and Neuhauser: https://link.springer.com/content/pdf/10.1007/s00013-019-01335-4.pdf – Hexhist Oct 10 '21 at 10:34
  • 1
    Thanks. I was aware of H-N's log-concavity conjecture but did not know about this simplification. – Abdelmalek Abdesselam Oct 11 '21 at 13:29
6

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.

psmears
  • 255
  • 1
    That's not a formula in a sense that it does not allow computing LR coeff. faster than via the other standard definitions. – Igor Pak Aug 18 '15 at 16:55
  • 1
    @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. – Per Alexandersson Aug 18 '15 at 17:45
  • 1
    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. – Igor Pak Aug 18 '15 at 23:39
  • @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. – Per Alexandersson Aug 19 '15 at 00:41
  • 2
    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. – Igor Pak Aug 19 '15 at 01:52
6

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

  • In fact there is an enormous source of combinatorial formulas stemming from combinatorial Hopf algebras... – მამუკა ჯიბლაძე Sep 02 '15 at 05:39
  • @მამუკაჯიბლაძე 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. – Duchamp Gérard H. E. Sep 02 '15 at 05:45
  • 4
    Is combinatorics the dual subject to mbinatorics? – Gerry Myerson Sep 02 '15 at 06:05
  • @GerryMyerson And in its turn mbinatorics is just a very particular case of mmultinatorics... – მამუკა ჯიბლაძე Sep 02 '15 at 07:15
  • 1
    For some connections to physics, "Hopf algebras and Dyso-Schwinger equations" by Weinzierl http://arxiv.org/abs/1506.09119 – Tom Copeland Sep 19 '15 at 19:35
  • @TomCopeland The group-like property of the generating series of the solutions was, in my understanding, well clarified in our paper with Alan Solomon. [M. Deneufchâtel, G. H. E. Duchamp, Hoang Ngoc Minh, A. I. Solomon, Independence of hyperlogarithms over function fields via algebraic combinatorics , Lecture Notes in Computer Science (2011), Volume 6742 (2011), 127-139. arXiv:1101.4497v1 [math.CO]]. However this paper is mathematical. As we are currently preparing a paper in connection with Physics, I will include your reference. Thanks again. – Duchamp Gérard H. E. Sep 20 '15 at 08:13
  • 1
    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). – Yannic Oct 06 '15 at 03:20
  • @Yannic It seems so after quick skimming. Thanks a lot (this is the miracle of mathoverflow). I'll have a better look later (+1). – Duchamp Gérard H. E. Oct 06 '15 at 03:28
  • @DuchampGérardH.E. It is quite mysterious and miraculous to find out! :) Question: you said "Note that whereas shuffle and stuffle are Hopf (they are in fact enveloping algebras), infiltration is only a bialgebra". But infiltration is a particular case of the Hoffman's quasi shuffle, so infiltration is indeed a product of a bialgebra. Is this wrong? – Yannic Oct 06 '15 at 03:34
  • @Yannic [so infiltration is indeed a product of a bialgebra]--> Yes it is, but the presence of non-invertible group-like elements (e.g. $(1+qa)$ for each letter $a$) makes this bialgebra without antipode. [But infiltration is a particular case of the Hoffman's quasi shuffle]-->not in my understanding because Hoffman's quasi shuffle produces Hopf algebras. I'll make this precise in my answer ASAP. Thanks for interaction. – Duchamp Gérard H. E. Oct 06 '15 at 04:03
  • @Yannic OK, I looked closer. Infiltration appears in the paper of Chen, Fox and Lyndon. Thanks once more. – Duchamp Gérard H. E. Oct 06 '15 at 16:50
6

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.

Russ Woodroofe
  • 3,367
  • 1
  • 23
  • 21
6

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

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). No 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. (*)

Gil Kalai
  • 24,218
5

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

Shahrooz
  • 4,746
5

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

5

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

Update: the upper bound were improved. The current identity (Kelley and Meka, 2023) is:

$$ 2^{-8\sqrt {\log n}} \le \frac {r_3(n)}{n} \le 2^{-(\log n)^\beta},$$ for some $\beta>0$.

Ofir Gorodetsky
  • 13,395
  • 1
  • 60
  • 75
Gil Kalai
  • 24,218
5

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

Gil Kalai
  • 24,218
5

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

Sam Hopkins
  • 22,785
5

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.

Timothy Chow
  • 78,129
5

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

Sam Hopkins
  • 22,785
5

The Durfee square formula for the generating function of the number of partitions doesn't seem to be in this list yet, I find it rather appealing: $$ \frac{1}{(q)_\infty} = \sum_{n\geq 0} \frac{q^{n^2}}{(q)_n (q)_n} \ . $$

eddy ardonne
  • 361
  • 5
  • 11
4

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

Gil Kalai
  • 24,218
4

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

Gil Kalai
  • 24,218
4

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

Gil Kalai
  • 24,218
4

This is a little bit of a lark, but I would argue it still marks important progress in combinatorics: $T=1+T^2\implies T^7=T$. Specifically, this is the (loose) initial justification for the "Seven Trees In One" (categorically) natural bijection between the set of binary trees and the set of 7-tuples of binary trees. It's an exhibition of the still-being-explored connections between combinatorial species, types, and category theory.

3

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.

Max Alekseyev
  • 30,425
  • 13
    Please make this self-contained by including explicit uses of the formula, as the question requests. – Douglas Zare Aug 19 '15 at 23:45
  • @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. – Max Alekseyev Aug 20 '15 at 16:28
  • 4
    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. – Douglas Zare Aug 20 '15 at 16:52
3

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.

Tom Copeland
  • 9,937
3

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.

Asaf Karagila
  • 38,140
  • Infinite sets always have countable subsets, no ? – Duchamp Gérard H. E. Sep 01 '15 at 07:52
  • 3
    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. – Asaf Karagila Sep 01 '15 at 08:03
3

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

Campello
  • 800
  • 1
    Along these lines, Stanley's reciprocity theorem certainly is a(n important) combinatorial formula: https://en.wikipedia.org/wiki/Stanley%27s_reciprocity_theorem – Sam Hopkins Sep 02 '15 at 14:46
  • @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 (http://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. – Tom Copeland Sep 19 '15 at 18:07
  • Other interesing connections: "Characteristic classes of singular toric varieties" by Maxim and Schuemann http://arxiv.org/abs/1303.4454. – Tom Copeland Nov 11 '15 at 21:15
  • See also "Stringy Chern classes of singular toric varieties and their applications" by Batyrev and Schaller https://arxiv.org/abs/1607.04135 – Tom Copeland Nov 05 '17 at 17:05
  • 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)$? – M. Winter Feb 09 '20 at 00:54
3

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

Leox
  • 546
2

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.

2

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.

1

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

anemone
  • 431
  • 3
    It is very important result, but I would not call it "formula". Also I doubt that geometry of numbers should be called "combinatorics". – Fedor Petrov Aug 18 '15 at 13:08
  • @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. – anemone Aug 18 '15 at 13:28
1

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

Taras Banakh
  • 40,791