Calcolo simbolico e coefficienti binomiali
Mauro Cerasoli - 06.11.00

Sia dato l'insieme A = {a,b,g} composto di tre elementi. Scriviamo simbolicamente l’espressione

g(A;x) = (1+xa)(1+xb)(1+xg)

dove x è un puro simbolo, variabile formale o indeterminata. Moltiplicando quindi i tre binomi come se fossero numeri naturali, si ottiene lo sviluppo

1+xa + xb + xg + xa + b + xa + g + xb + g + xa + b + g

Questo polinomio può essere interpretato nel modo seguente: il numero 1 corrisponde all'insieme vuoto; le potenze xa, xb, xg corrispondono ai singoletti {a}, {b}, {g}; le potenze xa + b, xa + g, xb + g corrispondono alle parti {a, b}, {a, g}, {b, g}; infine xa + b + g corrisponde all'insieme A.
In altri termini, il polinomio formale g(A;x) genera l'insieme delle parti di A nel senso che l'esponente di xS è il sottoinsieme S di A quando i segni + sono sostituiti con le virgole e il tutto viene racchiuso tra parentesi graffe. E' ovvio che si può considerare anche un insieme generico A = {a1,a2,…,an} di n elementi, ed il suo polinomio generatore

g(A;x) = (1+x^a1)(1+x^a2)…(1+x^an)

Per l'insieme vuoto poniamo g(Æ,x) = 1. E' immediata la seguente proprietà di questo polinomio:

A Ç B = Æ Þ g(A; x)g(B; x) = g(A È B; x)

Riprendiamo l'insieme A = {a,b,g}e questa volta scriviamo un nuovo polinomio nelle due variabili formali x e y:

g(A;x,y) = (xa + ya)(xb + yb )(xg + yg)

ottenendo, dopo aver sviluppato il prodotto,

xa + b + g xa + b yg xa + g yb xb + g ya xa yb + g xb ya + g xg ya + b ya + b + g

A tutta questa espressione può essere dato un bel significato combinatorio nel modo seguente. Immaginiamo che a, b e g siano delle biglie e che i simboli x e y siano delle scatole. I possibili modi per collocare le tre biglie nelle due scatole x e y sono:


xa+b+g

xa+b yg

xa+g yb

xb+g ya

xa yb+g

xb ya+g

xg ya+b

ya+b+g

Il monomio, o potenza, xa (scritto anche x^a) significa: la biglia a va nella scatola x. Il significato combinatorio del polinomio g(A; x, y), in termini di biglie nelle scatole, è ora evidente: gli esponenti S di x e T di y del monomio xSyT rappresentano rispettivamente la parte S di A che va nella scatola x e la parte complementare T di A che va nella scatola y, quando i segni + sono cambiati in virgole e il tutto è messo tra parentesi graffe. Anche in questo caso possiamo generalizzare la questione. Vediamo come.
Consideriamo un insieme A di n elementi o biglie ai. Il polinomio generatore è ora

g(A; x, y) =(x^a1 +y^a1)(x^a2+y^a2)…(x^an+y^an)

Vediamo cosa succede quando poniamo a1 = a2 = … = an = 1. Si ottiene la potenza (x + y)n. Se poi indichiamo con ( nk ) (leggi n sopra k) il numero di modi di mettere n biglie (gli elementi di A) in due scatole (x e y), così che k biglie siano nella scatola x ed n-k siano nella scatola y, deve valere l'identità:

(x + y)n = S 0£k£n ( nk )xkyn-k (formula binomiale)

Si badi che x ed y non sono numeri ma puri simboli. Inoltre valgono le seguenti identità per i coefficienti binomiali ( nk ):
  1. ( n0 ) =( nn ) = 1; ( n1 ) = n; ( nk ) = 0 per k > n
  2. ( nn-k ) = ( nk );   S 0 £ k £ n ( nk ) = 2n
  3. ( n+1k ) = ( nk ) + ( nk-1 )   (formula di Stifel)
  4. ( nk ) = n( n-1k-1 )/k = (n-k+1)( n-1k )/k
  5. ( nk ) = n(n-1)(n-2)...(n-k+1)/k!

Delle formule precedenti soltanto c) e d) hanno bisogno di una dimostrazione. Infatti a) e b) sono evidenti; per la seconda della b) non è necessario porre x = y = 1 perché la somma dei coefficienti binomiali è il totale dei modi di porre n biglie in due scatole, cioè 2n. La formula e) viene da d) iterando su n e k . Prima di dimostrare c) e d) facciamo notare che queste proprietà fondamentali dei coefficienti binomiali verranno provate ignorando il valore numerico, diciamo la formula e), appositamente collocata alla fine dell'elenco: cioè senza fare calcoli! E' un po' come accade in goniometria alla scuola media superiore: vengono presentate e dimostrate le varie formule che legano senx, cosx, tanx, senza mai menzionare e dimostrare gli sviluppi di Taylor di queste funzioni, cioè le formule che danno i loro valori numerici.
Della formula di Stifel si può dare un'elegante e semplice dimostrazione combinatoria nel modo seguente. Il primo membro è il numero di modi di mettere n+1 biglie in due scatole così che la prima abbia k biglie e la seconda n+1-k. Fissata una biglia a, contiamo diversamente questi modi distinguendo quelli in cui la biglia non va nella prima scatola: sono ( nk ), da quelli in cui ci va: sono ( nk-1 ). Ora basta fare la somma.
Per dimostrare la prima uguaglianza della formula d) contiamo in quanti modi puoi mettere k biglie nella scatola x (ed n-k in y) così che sia evidenziata anche una biglia che mettiamo in x. Per esempio, da n professori si vuole formare una commissione di k professori, in modo che uno di questi sia il presidente. Se prima scelgo le k biglie tra le n disponibili (in ( nk ) modi) e poi scelgo quella da evidenziare (in k modi), in totale questi sono k( nk ). Se però prima scelgo la biglia da evidenziare (in n modi) e poi scelgo le altre k - 1 biglie (in ( n-1k-1 ) modi) tra le restanti n - 1 da mettere nella scatola x, ho n( n-1k-1 ) scelte. Pertanto deve essere k( nk ) = n( n-1k-1 ) da cui segue la prima identità. Contando in maniera diversa questi modi, si ha la seconda identità.
Nello sviluppare il polinomio g(A;x,y) abbiamo tacitamente ammesso la commutatività delle indeterminate, cioè che xy = yx. Che cosa succede se questa ipotesi viene a mancare ? Consideriamo il caso particolare n = 2 biglie e tre scatole, cioè il polinomio generatore

(x+y+z)2 = x2 +y2 +z2 +xy + yx + xz + zx + yz + zy

I termini dello sviluppo sono tutte le parole lunghe 2 dell'alfabeto {x, y, z}. In questo modello le scatole diventano lettere o simboli di un alfabeto e le biglie diventano posti (o caselle) dove scrivere le lettere.