Calcolo combinatorio elementare e binomio di Newton

I principi di conteggio

Contare gli elementi di un insieme finito è l’operazione più elementare dell’aritmetica finché l’insieme può essere percorso elemento per elemento. Tuttavia, quando gli elementi sono i modi di compiere una scelta composta, come ordinare dieci libri su uno scaffale o scegliere tre rappresentanti fra trenta persone, l’enumerazione diventa impraticabile, e il numero si ottiene scomponendo la scelta in parti o in fasi. Tutto il calcolo combinatorio elementare poggia su due principi, che si dimostrano a partire da una definizione precisa di che cosa significa contare.

Contare gli elementi di un insieme significa numerarli: assegnare a ogni numero da $1$ a $n$ un elemento, senza ripeterne nessuno e senza ometterne nessuno. Si dice che un insieme $A$ ha $n$ elementi, con $n$ naturale, quando esiste una biiezione dall’insieme $\{1, 2, \ldots, n\}$ su $A$, cioè una funzione che manda numeri distinti in elementi distinti e raggiunge tutti gli elementi di $A$; l’insieme vuoto ha $0$ elementi, e un insieme è finito se è vuoto o ha $n$ elementi per qualche naturale $n$. Le biiezioni, la loro composizione e la loro inversa si studiano nella lezione su insiemi, relazioni e funzioni.

Fatto ammesso (numero di elementi). Si ammette senza dimostrazione che il numero di elementi di un insieme finito è ben definito: un insieme non può avere contemporaneamente $m$ elementi e $n$ elementi se $m \neq n$. Si ammette inoltre che ogni sottoinsieme di un insieme finito è finito.

Entrambi i fatti si dimostrano per induzione su $n$; il primo è, in fondo, il principio dei cassetti, secondo il quale non esiste una funzione che mandi gli $n + 1$ numeri di $\{1, \ldots, n + 1\}$ in numeri distinti di $\{1, \ldots, n\}$. Le loro dimostrazioni sono lunghe e non apportano idee che si usino in seguito, e per questo si ammettono. Senza il primo, l’espressione «il numero di elementi» non avrebbe senso, e una dimostrazione combinatoria, che conta uno stesso insieme in due modi, non potrebbe concludere che i due risultati sono uguali.

Per induzione sul numero delle parti, il principio si estende a un numero finito qualsiasi di insiemi a due a due disgiunti: l’unione di $A_1, \ldots, A_r$, con $n_1, \ldots, n_r$ elementi, ha $n_1 + \cdots + n_r$ elementi, perché l’unione dei primi $r + 1$ è quella dei primi $r$ con l’ultimo, che non ha elementi comuni con essi. Da esso si deduce il secondo principio, che conta le scelte compiute per fasi.

Allo stesso modo, per induzione sul numero delle fasi, il principio moltiplicativo si estende a un numero finito qualsiasi di esse: una scelta in $r$ fasi, che possono compiersi rispettivamente in $n_1, n_2, \ldots, n_r$ modi, può compiersi in $n_1 n_2 \cdots n_r$ modi. Per esempio, nel sistema decimale studiato nella lezione sui sistemi di numerazione posizionale ci sono $9 \cdot 10 \cdot 10 = 900$ numeri di tre cifre, perché la prima cifra non può essere $0$ e le altre due sono libere. Conviene avvertire che il principio moltiplicativo esige che il numero di opzioni di ciascuna fase non dipenda da ciò che si è scelto prima, anche se le opzioni stesse ne dipendono; se questa condizione viene meno, si distinguono casi in cui essa vale e se ne sommano i risultati con il principio additivo.

Le fasi successive di una scelta si rappresentano con un diagramma ad albero: da un punto iniziale, la radice, escono tanti rami quante sono le opzioni della prima fase; dall’estremo di ogni ramo, tanti quante sono quelle della seconda, e così via. Ogni percorso dalla radice a un estremo finale, o foglia, è una scelta completa, e il principio moltiplicativo conta le foglie senza disegnarle.