Una dimostrazione mediante doppio conteggio è un genere di dimostrazione utilizzata in combinatoria che ha come scopo una uguaglianza di due espressioni enumerative che forniscono la cardinalità di un insieme finito X e consiste in due diversi modi di contare gli elementi di tale insieme. I due modi di contare riguardano due diverse prospettive per l'organizzazione dell'insieme X, oppure due diversi procedimenti per costruirlo, oppure due diversi percorsi per visitarlo (cioè per passare su tutti e suoi elementi una sola volta).
Esempi Sottoinsiemi e coefficiente binomiale Dato un insieme di elementi, possiamo contare i suoi sottoinsiemi in due modi. Il primo metodo consiste nel considerare che ogni elemento dell'insieme può appartenere o meno ad un sottoinsieme: per ognuno degli elementi sono perciò possibili due scelte, e il numero totale di scelte, pari al numero di sottoinsiemi, è .
Un secondo metodo consiste nel contare separatamente i sottoinsiemi di una data cardinalità : è noto che i sottoinsiemi di cardinalità sono espressi dal coefficiente binomiale ; il numero totale di sottoinsiemi è perciò dato dalla somma dei vari coefficienti bininomiali.
Uguagliado il risultato di questi due metodi si ha che
Questa formula, tra le altre cose, afferma che ogni riga del triangolo di Tartaglia ha come somma una potenza di due.
Teorema di Cauchy-Frobenius Il teorema di Cauchy-Frobenius (anche noto come lemma di Burnside), afferma che, nell'azione di un gruppo finito su un insieme finito , il numero di orbite è dato dalla formula
dove è il numero di elementi dell'insieme che rimangono fissi sotto l'azione di . Per dimostrare questo teorema, si considera l'insieme e il suo sottoinsieme
Si può contare la cardinalità di questo insieme "per righe" o "per colonne". L'uguaglianza fra questi due conteggi porta al risultato.
Voci correlate Dimostrazione mediante biiezione
Note
Categoria:Combinatoria Categoria:Dimostrazioni matematiche