Motivation:
The poster for the conference celebrating Noga Alon's 60th birthday, fifteen formulas describing some of Alon's work are presented. (See this post, for the poster, and cash prizes offered for identifying the formulas.) This demonstrates that sometimes (but certainly not always) a major research progress, even areas, can be represented by a single formula. Naturally, following Alon's poster, I thought about representing other people's works through formulas. (My own work, Doron Zeilberger's, etc. Maybe I will pursue this in some future posts.) But I think it will be very useful to collect major formulas representing major research in combinatorics.
The Question
The question collects important formulas representing major progress in combinatorics.
The rules are:
Rules
1) one formula per answer
2) Present the formula explicitly (not just by name or by a link or reference), and briefly explain the formula and its importance, again not just link or reference. (But then you may add links and references.)
3) Formulas should represent important research level mathematics. (So, say $\sum {{n} \choose {k}}^2 = {{2n} \choose {n}}$ is too elementary.)
4) The formula should be explicit as possible, moving from the formula to the theory it represent should also be explicit, and explaining the formula and its importance at least in rough terms should be feasible.
5) I am a little hesitant if classic formulas like $V-E+F=2$ are qualified.
An important distinction:
Most of the formulas represent definite results, namely these formulas will not become obsolete by new discoveries. (Although refined formulas are certainly possible.) A few of the formulas, that I also very much welcome, represent state of the art regarding important combinatorial parameters. For example, the best known upper and lower bounds for diagonal Ramsey's numbers. In the lists and pictures below an asterisk is added to those formulas.
The Formulas (so far)
In order to make the question a more useful source, I list all the formulas in categories with links to answer (updated Feb. 6 '17).
Basic enumeration: The exponential formula; inclusion exclusion; Burnside and Polya; Lagrange inversion; generating function for Fibonacci; generating function for Catalan; Stirling formula; Enumeration and algebraic combinatorics: The hook formula; Sums of tableaux numbers squared, Plane partitions; MacMahon Master Theorem; Alternating sign matrices; Erdos-Szekeres; Ramanujan-Hardy asymptotic formula for the number of partitions; $\zeta(3)$; Shuffles; umbral compositional identity; Jack polynomials; Roger-Ramanujan; Littlewood-Ricardson;
Geometric combinatorics: Dehn-Somerville relations; Zaslavsky's formula; Erhard polynomials; Minkowski's theorem. Graph theory: Tutte's golden identity; Chromatic number of Kneser's graph; (NEW)Tutte's formula for rooted planar maps ; matrix-tree formula; Hoffman bound; Expansion and eigenvalues; Shannon capacity of the pentagon; Probability: Self avoiding planar walks; longest monotone sequences (average); longest monotone sequences (distribution); Designs: Fisher inequality; Permanents: VanderWaerden conjecture; Coding theory: MacWilliams formula; Extremal combinatorics: Erdos-Sauer bound; Ramsey theory: Diagonal Ramsey numbers (); Infinitary combinatorics: Shelah's formula (); A formula in choiceless set theory. Additive combinatorics: sum-product estimates (*); Algorithms: QuickSort.
(Larger formulas): Series multisection; Faà di Bruno's formula; Jacobi triple product formula; A formula related to Alon's Combinatorial Nullstellensatz; The combinatorics underlying iterated derivatives (infinitesimal Lie generators) for compositional inversion and flow maps for vector fields (also related to the enumerative geometry of associahedra); some mysterious identities involving mock modular forms and partial theta functions;
Formulas added after October 2015:
Hall and Rota Mobius function formula; Kruskal-Katona theorem; Best known bounds for 3-AP free subsets of $[n]$ (*);
After October 2016: Abel's binomial identity; Upper and lower bounds for binary codes;
Best Answer
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.