Si tratta di fare una dimostrazione che non utilizzi il valore numerico dei simboli o altre proprietà dei coefficienti binomiali, ma solo il loro significato insiemistico. Il primo membro rappresenta il numero dei sottoinsiemi a k elementi di un insieme di n elementi. Per verificare l'uguaglianza cerchiamo di contare questi sottoinsiemi in un altro modo. Numeriamo gli elementi dell'insieme da 1 a n, e ragioniamo, per semplicità, su un esempio concreto, ponendo n=7 e k=3. Per contare i sottoinsiemi di 3 elementi dall'insieme di 7, posso cominciare a contare quelli che hanno come minimo elemento 1; essi sono in numero di , in quanto, fissato l'1, devo scegliere i restanti due elementi della terna tra i residui 6 elementi dell'insieme: . Poi conto quelli che cominciano con 2, che saranno, per lo stesso motivo di prima, . Di seguito conterò quelli che cominciamo con 3, 4, 5 che saranno, rispettivamente, , , . Una generalizzazione immediata porta alla formula richiesta.

Si può procedere calcolando (1+i)ⁿ in due modi diversi.

.

D'altro canto . I valori richiesti si trovano ora per confronto.

Il primo membro rappresenta i sottoinsiemi con k elementi di un insieme con n elementi, il secondo membro i sottoinsiemi con n-k elementi. E' chiaro che se un sottoinsieme ha k elementi, il suo complementare ne ha n-k. La formula esprime allora semplicemente il fatto che ogni sottoinsieme di un insieme ha un unico complementare.

I numeri di n cifre sono le disposizioni con ripetizione di 2 simboli (0 ed 1) a n a n, e pertanto sono 2ⁿ. Contiamo ora questi numeri in altro modo. Iniziamo con quelli che non contengono nessun 1: ce n'è uno solo, , quello che ha tutti 0. I numeri che contengono un solo 1 sono n, ovvero , corrispondenti alle possibili scelte dove mettere il numero 1 su n posizioni. I numeri con due 1 sono , corrispondenti alle possibili scelte delle due posizioni, su n, in cui mettere gli 1. La conclusione è ora banale.

La dimostrazione è quasi immediata usando la formula del binomio, dopo aver osservato che m = (1+m-1). Vogliamo però procedere in un altro modo per mettere in evidenza il significato combinatorio dei simboli. Si può fare un confronto con la soluzione dell'esercizio 14. Contiamo i numeri di n cifre in un sistema con m simboli: {s₁, s₂, ..., s_m}. Il primo membro è il conteggio diretto mediante le disposizioni con ripetizione degli m simboli. Contiamo ora i numeri che non contengono il simbolo s₁: sono tanti quanti i numeri che contengono solo i restanti simboli, ovvero . La quantità di numeri che contengono 1 volta il simbolo s₁ si ottiene contando gli posti dove si può mettere s₁ e moltiplicando per (m-1)^n-1 che sono i modi di disporre i restanti m-1 simboli. Analogamente la quantità di numeri che contengono 2 volte il simbolo s₁ si otterrà moltiplicando per (m-1)^n-2 e così via.

Un cammino qualunque di minima lunghezza da A a B ha lunghezza 2n e consta di n passi nella direzione x e di n passi nella direzione y. Per caratterizzare i percorsi devo decidere quali passi devo fare nella direzione x (oppure, il che è lo stesso, nella direzione y), cioè devo scegliere n elementi su un totale di 2n: il risultato è . D'altro canto ogni cammino deve passare per un punto D della diagonale e i cammini da A a D e da D a B hanno lunghezza n. Se D ha coordinate (k,n-k), ripetendo il ragionamento di sopra si vede che i cammini da A a D sono , come quelli da D a B. I cammini da A a B che passano per D saranno allora .. Sommando tutte le possibilità si ottiene la nota formula .

Il primo membro rappresenta le permutazioni indicate. Si tratta di provare a contarle in un altro modo. Si possono scegliere k degli n oggetti, in modi diversi, e poi fare le k! loro permutazioni e le (n-k)! permutazioni dei rimanenti. In questo modo si è provata la formula richiesta. Si noti come questo ragionamento costituisca una dimostrazione alternativa della nota formula riguardante i coefficienti binomiali.

*) L'uguaglianza è vera per p=1, in quanto si riduce a .

**) Supposta vera l'uguaglianza per p, dimostriamola per p+1. Si tratta solo di eseguire i calcoli, ottenendo: , l'ultima uguaglianza essendo giustificata dalla formula di Stifel.

Il primo membro rappresenta il numero dei sottoinsiemi con k elementi di un insieme, diciamolo A, di n elementi. Vediamo di contare questi sottoinsiemi in modo diverso. Indicati con a₁, a₂, ..., a_n, gli elementi di A, consideriamo l'insieme B che si ottiene escludendo a_n e costruiamo i suoi sottoinsiemi di k-1 elementi. Essi sono in numero di . Se ad ognuno di questi aggiungiamo a_n otteniamo sottoinsiemi a k elementi di A, che sono tutti quelli che contengono a_n. Vediamo ora di ottenere anche gli altri. Ad ognuno dei sottoinsiemi di B aggiungiamo uno degli elementi di B che non gli appartengono, e che sono in numero di n-k. Otteniamo insiemi, sottoinsiemi di A, con k elementi. Ciascun sottoinsieme è però ripetuto in questo modo k volte. Per rendercene conto consideriamo, per esempio, l'insieme {a₁, a₂, ..., a_k-1}. Aggiungendoci a_k otteniamo l'insieme C = {a₁, a₂, ..., a_k-1, a_k}. C si ottiene però anche da {a₁, a₂, ..., a_k-2, a_k}, aggiungendo a_k-1, e così via. Ci sono chiaramente k modi di ottenere C. Dunque i sottoinsiemi di A con k elementi, che non contengono an, sono in numero di . Il totale è allora: , con il che l'uguaglianza è provata. Si noti che l'uguaglianza poteva essere provata in modo immediato usando la nota formula per i coefficienti binomiali, ma la dimostrazione che abbiamo fornito rende più chiaro il significato insiemistico dei coefficienti stessi.

Applicando anche la formula di Stifel si ha . Basta ora applicare la formula per i coefficienti binomiali per trovare n=17.