Doppia prova di conteggio

In matematica combinatoria , una dimostrazione mediante doppio conteggio , o doppio conteggio , o anche doppio conteggio , è una tecnica di dimostrazione combinatoria utilizzata per dimostrare che due espressioni sono uguali dimostrando che ci sono due modi per contare il numero di elementi d 'lo stesso insieme . Van Lint e Wilson descrivono questa tecnica come "uno degli strumenti più importanti in calcolo combinatorio".

Caso speciale: enumerazione di una parte di un prodotto cartesiano

Principio

Siano due insiemi finiti e , e un sottoinsieme di ; ogni volta che appartiene a , diciamo che e sono incidenti. $\ mathcal {E}$ ${\ mathcal {F}}$ ${\ mathcal {G}}$ ${\ displaystyle {\ mathcal {E}} \ times {\ mathcal {F}}}$ $(x, y)$ ${\ mathcal {G}}$ $X$ $y$

Si noti che può essere visto come il grafico di una relazione binaria di worm , nel qual caso viene scritto " e incidenti" , o come un grafico bipartito . ${\ mathcal {G}}$ $R$ $\ mathcal {E}$ ${\ mathcal {F}}$ $X$ $y$ ${\ displaystyle xRy}$

Se designa il numero di elementi che incidono su e quello degli elementi che incidono su , abbiamo la formula nota come doppio conteggio o conteggio per fette (o per pile) : ${\ displaystyle n ^ {+} (x)}$ $y$ $X$ ${\ displaystyle n ^ {-} (y)}$ $X$ $y$

${\ Displaystyle \ sum _ {x \ in E} n ^ {+} (x) = \ sum _ {y \ in F} n ^ {-} (y) = \ left \ vert {\ mathcal {G}} \ right \ vert = {\ text {card}} {\ mathcal {G}}}$ .

Un caso particolare interessante è quello dove e sono costanti; la formula viene quindi scritta . ${\ displaystyle n ^ {+}}$ ${\ displaystyle n ^ {-}}$ ${\ displaystyle n ^ {+}. \ left \ vert {\ mathcal {E}} \ right \ vert = n ^ {-}. \ left \ vert {\ mathcal {F}} \ right \ vert}$

Illustrazione del diagramma sagittale

La formula del doppio conteggio è interpretata in questo diagramma dal fatto che il numero delle frecce è uguale al numero delle loro partenze così come al numero dei loro arrivi.

Illustrazione della matrice di incidenza

Se definiamo la matrice di incidenza del grafico o della relazione con se appartiene a , altrimenti, la formula del doppio conteggio significa che la somma dei termini della matrice si ottiene sommando righe per righe, oppure sommando colonne per colonne. Indeed è il numero di siti nella riga associata a , ed è il numero di siti nella colonna associata a . $A$ ${\ mathcal {G}}$ $R$ ${\ displaystyle A (x, y) = 1}$ $(x, y)$ ${\ mathcal {G}}$ ${\ displaystyle A (x, y) = 0}$ $A$ ${\ displaystyle n ^ {+} (x)}$ $1$ $X$ ${\ displaystyle n ^ {-} (y)}$ $1$ $y$

Nell'esempio a fianco, la matrice di incidenza è . ${\ displaystyle A = {\ begin {pmatrix} & \ alpha & \ beta & \ gamma & \ delta \\ a & 1 & 0 & 0 & 0 \\ b & 1 & 1 & 0 & 0 \\ c & 0 & 0 & 1 & 1 \\ d & 0 & 1 & 0 & 0 \\ e & 1 & 0 & 0 & 1 \ end {pmatrix}}}$

In questo senso, la formula di doppio conteggio è un caso particolare della formula di segni di inversione di sommatoria : . ${\ Displaystyle \ sum _ {(i, j) \ in I \ times J} a_ {i, j} = \ sum _ {i \ in I} \ sum _ {j \ in J} a_ {i, j} = \ sum _ {j \ in J} \ sum _ {i \ in I} a_ {i, j}}$

Esempi di applicazioni

Somma di numeri interi primi

non

Qui, gli insiemi e sono uguali all'insieme di numeri interi da 1 a e due interi e sono incidenti se . ${\ mathcal E}$ ${\ mathcal {F}}$ $non$ $io$ $j$ ${\ displaystyle i \ leqslant j}$

Quindi e ${\ displaystyle n ^ {+} (i) = n + 1-i}$ ${\ displaystyle n ^ {-} (i) = i}$

Viene quindi scritta la formula per il doppio conteggio , dalla quale si deduce la formula classica . ${\ Displaystyle \ sum _ {i = 1} ^ {n} (n + 1-i) = \ sum _ {i = 1} ^ {n} i}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} i = {n (n + 1) \ over {2}}}$

Numero medio di divisori

Gli stessi set e , ma e sono incidenti se divisi . ${\ mathcal E}$ ${\ mathcal {F}}$ $io$ $j$ $io$ $j$

Allora è il numero di multipli di minore o uguale a , che è dove denota la parte intera, ed è il numero di divisori di . ${\ displaystyle n ^ {+} (i)}$ $io$ $non$ ${\ displaystyle \ left \ lfloor {\ frac {n} {i}} \ right \ rfloor}$ ${\ displaystyle \ left \ lfloor. \ right \ rfloor}$ ${\ displaystyle n ^ {-} (i)}$ ${\ displaystyle d (i)}$ $io$

Viene quindi scritta la formula per il doppio conteggio ; possiamo facilmente dedurlo ( serie armonica ), e come , otteniamo che il numero medio di divisori di un numero compreso tra 1 e è equivalente a . ${\ Displaystyle \ sum _ {i = 1} ^ {n} d (i) = \ sum _ {i = 1} ^ {n} \ left \ lfloor {\ frac {n} {i}} \ right \ rfloor }$ ${\ Displaystyle {1 \ over n} \ sum _ {i = 1} ^ {n} d (i) \ sim \ sum _ {i = 1} ^ {n} {1 \ over i} = H_ {n} }$ ${\ displaystyle H_ {n} \ sim \ ln n}$ $non$ ${\ displaystyle \ ln n}$

Somma dei gradi dei vertici di un grafo

Qui, l'insieme è l'insieme dei vertici di un grafo , l'insieme dei suoi archi, e la relazione di incidenza è quella di adiacenza tra i vertici e gli archi. Per un vertice , viene interpretata come il grado di , ed un bordo , ; viene quindi scritta la formula del doppio conteggio dove è il numero di bordi del grafico. Deduciamo che il numero di vertici di grado dispari è pari, il che costituisce il lemma delle strette di mano . ${\ mathcal E}$ ${\ mathcal {F}}$ $S$ ${\ displaystyle n ^ {+} (s)}$ $S$ $a$ ${\ displaystyle n ^ {-} (a) = 2}$ ${\ Displaystyle \ sum \ operatorname {deg} (s) = 2A}$ $A$

Deduciamo anche ad esempio che in un poliedro tutti i vertici sono di grado , dove è il numero di vertici. $non$ ${\ displaystyle nS = 2A}$ $S$

Allo stesso modo, in un poliedro in cui tutte le facce hanno bordi, dov'è il numero di facce. $p$ ${\ displaystyle pF = 2A}$ $F$

Formula sui coefficienti binomiali

Qui, l'insieme è l'insieme di parti in elementi di un insieme di elementi e l'insieme di parti in elementi; è decretato che due parti e sono accessorie se sono disgiunte . ${\ mathcal E}$ $p$ $non$ ${\ mathcal {F}}$ $q$ $A$ $B$

Vale il numero di elementi del grafico (scelta di , quindi scelta di in ). Ora qui , che è il numero di disgiunti di , è e vale . Viene quindi scritta la formula per il doppio conteggio: ${\ mathcal {G}}$ ${\ displaystyle {\ binom {n} {p + q}} {\ binom {p + q} {p}}}$ $A \ cup B$ $A$ $A \ cup B$ ${\ displaystyle n ^ {+} (A)}$ $B$ $A$ ${\ displaystyle {\ binom {np} {q}}}$ ${\ displaystyle n ^ {-} (B)}$ ${\ displaystyle {\ binom {nq} {p}}}$

${\ displaystyle {\ binom {n} {p}} {\ binom {np} {q}} = {\ binom {n} {q}} {\ binom {nq} {p}} = {\ binom {n } {p + q}} {\ binom {p + q} {p}}}$ .

Ad esempio, facendo , otteniamo , che cambiando in dà l'importante formula del pedone : $q = 1$ ${\ displaystyle (np) {\ binom {n} {p}} = n {\ binom {n-1} {p}} = (p + 1) {\ binom {n} {p + 1}}}$ $p$ $p-1$

${\ displaystyle {\ binom {n} {p}} = {n \ over p} {\ binom {n-1} {p-1}}}$ .

Altri esempi

Somma di una retta del triangolo di Pascal

Cerchiamo di trovare il numero di parti di un insieme con n elementi.

Primo metodo : ci sono due possibilità per ogni elemento: o è nel gioco o non lo è. Pertanto, ci sono un totale di parti. $2 \ times 2 \ times \ ldots \ times 2 \, (n {\ mbox {times}}) = 2 ^ {n}$

Secondo metodo : il numero di elementi in una parte è un numero intero compreso tra 0 e . Il numero di parti per elementi è il coefficiente binomiale , quindi il numero di parti è . $p$ $non$ $p$ ${\ displaystyle {\ binom {n} {p}}}$ ${\ displaystyle \ sum _ {p = 0} ^ {n} {\ binom {n} {p}}}$

L'equalizzazione delle due espressioni dà:

{\ displaystyle \ sum _ {p = 0} ^ {n} {\ binom {n} {p}} = 2 ^ {n}}

Il piccolo teorema di Fermat

Il piccolo teorema di Fermat afferma che "se è un numero primo e se è un intero, allora un multiplo di ". Per esempio : $p$ $a$ ${\ displaystyle a ^ {p} -a}$ $p$

4 3 - 4 = 60 che è divisibile per 3.

Sia un numero primo e un numero intero. Considera un alfabeto fatto di simboli. Contiamo le parole di lunghezza in cui sono presenti almeno due simboli distinti. $p$ $a$ $a$ $non$ $p$

Primo metodo : ci sono parole di qualsiasi lunghezza nell'alfabeto, da cui è necessario rimuovere le parole composte da uno stesso simbolo: ${\ displaystyle a ^ {p}}$ $p$ $a$

{\ displaystyle n = a ^ {p} -a}

Secondo metodo : queste parole possono essere raggruppate in insiemi di parole che possono essere dedotte l'una dall'altra mediante permutazione circolare . Questi set sono chiamati collane (illustrazione) . Ad esempio, se l'alfabeto è e se consideriamo le parole di tre lettere, le tre parole , e siamo nella stessa collare. $\ {A, B, C, D \}$ $ABD$ $BDA$ $TAMPONARE$

Ci sono parole simbolo in ogni collana. In effetti, ciascuna delle permutazioni dà una parola diversa, perché è primaria. Questo non sarebbe il caso se non fosse primo, ad esempio ci sono solo 2 parole diverse di 4 simboli nella collana . Quindi abbiamo: $p$ $p$ $p$ $p$ $p$ $ABAB$

{\ displaystyle n = p. {\ text {(numero di collane)}}}

Scrivendo l'uguaglianza tra queste due espressioni per , troviamo che è divisibile per . $non$ ${\ displaystyle n = a ^ {p} -a}$ $p$

Enumerazione di alberi colorati

Qual è il numero di alberi di colore diverso che possono coprire una gamma di altezze diverse? La formula di Cayley dà la risposta: $C_ {n}$ $non$

C_ {n} = n ^ {{n-2}}

Aigner e Ziegler elencano quattro diverse prove di questo risultato. Affermano che, delle quattro, è la dimostrazione per doppio conteggio che dobbiamo a Jim Pitman che è "il più bello di loro" .

In questa dimostrazione enumeriamo in due modi le diverse serie di archi orientati che possono essere aggiunti a un grafo nullo (senza spigoli) di n vertici per formare un albero.

Primo metodo : partiamo da uno dei possibili alberi non orientati e scegliamo uno dei suoi n vertici come radice dell'albero orientato, che dà un albero orientato. Ci sono modi per scegliere il primo bordo, poi modi per scegliere il bordo successivo e così via. Infine, il numero totale di sequenze che possono essere formate in questo modo è: $C_ {n}$ $n-1$ $n-2$

C_ {n} n!

Secondo metodo : aggiungiamo gli archi uno per uno al grafico vuoto, considerando il numero di scelte disponibili ad ogni passaggio. Se abbiamo già aggiunto una raccolta di archi per formare una foresta di alberi orientati k (illustrazione) , è possibile scegliere di aggiungere il bordo successivo. Infatti, il suo vertice iniziale può essere uno qualsiasi degli n vertici del grafo e il suo vertice finale può essere una qualsiasi delle radici diverse dalla radice dell'albero contenente il vertice iniziale (illustrazione) . Infine, moltiplicando il numero di scelte nel primo passaggio, nel secondo passaggio, ecc., Il numero totale di scelte è: $nk$ ${\ displaystyle n (k-1)}$ $k-1$

{\ Displaystyle \ prod _ {k = 2} ^ {n} n (k-1) = n ^ {n-1} (n-1)! = n ^ {n-2} n!}

Scrivendo l'uguaglianza tra queste due espressioni per il numero di sequenze di archi,

C_ {n} n! = N ^ {{n-2}} n!

otteniamo la formula di Cayley:

{\ displaystyle C_ {n} = n ^ {n-2}}

Altri esempi

L' identità Vandermonde , l' identità della stella di David , altre proprietà dei coefficienti binomiali che si possono dimostrare con il doppio conteggio.
I numeri piramidali quadrati . L'uguaglianza tra la somma dei primi n quadrati e un polinomio di terzo grado può essere dimostrata contando due triple di interi ( x , y , z ) dove z è maggiore di ciascuno degli altri due numeri.
La disuguaglianza Lubell-Yamamoto-Meshalkin . La dimostrazione di questo risultato di D. Lubell sulle famiglie di insiemi utilizza un argomento di doppio conteggio sulle permutazioni per dimostrare questa volta una disuguaglianza piuttosto che un'uguaglianza.
La legge della reciprocità quadratica . Una dimostrazione dovuta a Gotthold Eisenstein permette di ottenere quest'altro importante risultato della teoria dei numeri , contando in due modi diversi i punti di un reticolo in un triangolo.

Note e riferimenti

(fr) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in inglese intitolato " Double counting (proof technique) " ( vedi la lista degli autori ) .

Questo articolo è parzialmente o interamente tratto dall'articolo intitolato “ Prova biettiva ” (vedi l'elenco degli autori ) , dove contiamo separatamente due insiemi legati da una biiezione per stabilire l'uguaglianza tra due quantità.

(a) Jacobus H. van Lint e Richard M. Wilson , A Course in Combinatorics , Cambridge University Press ,2001, 602 p. ( ISBN 978-0-521-00601-9 , leggi online ) , p. 4, p. 4 " Uno degli strumenti importanti in calcolo combinatorio è il metodo per contare determinati oggetti in due modi diversi ".
Martin Aigner e Günter M. Ziegler , Divine Reasonings , Springer-Verlag ,2013, p. 186.
Martin Aigner e Günter M. Ziegler , Divine Reasonings , Springer-Verlag ,2013, p. 187.
(a) Martin Aigner e Günter M. Ziegler , Proofs from THE BOOK , Springer-Verlag ,1998, p. 145-146.
Martin Aigner e Günter M. Ziegler , Divine Reasonings , Springer-Verlag ,2013, p. 229-230.