Identità combinatoria

In matematica e in particolare in combinatoria, per identità combinatoria si intende una uguaglianza fra due espressioni le quali sono interpretabili come cardinalità di due insiemi di oggetti discreti (sottoinsiemi di insiemi finiti, combinazioni di estrazioni, orbite di gruppi di trasformazioni, grafi, cammini nel piano combinatorio, polinomi a coefficienti razionali semplici, configurazioni geometriche discrete, ...) che si possono porre in corrispondenza biunivoca, oppure si possono ricavare formalmente da identità come le precedenti. Molte di queste identità riguardano funzioni speciali. Di molte sono possibili interpretazioni geometriche.

Alcuni esempi:

• Formula di Stifel (anche nota come "identità di Pascal")

${n \choose k}={n-1 \choose k}+{n-1 \choose k-1}$

• Sottoinsiemi delle diverse cardinalità di insieme di cardinalità n

$\sum _{k=0}^{n}{n \choose k}=2^{n}$

• Un caso di formula ricavabile dalla formula di inversione di Möbius

$\phi (n)=n\cdot \sum _{d|n}{\mu (d) \over d},$

ove φ è la Funzione φ di Eulero.