La partizione di un numero naturale $n$ è un modo per scrivere $n$ come somma di interi positivi, senza tenere conto dell’ordine degli addendi. Ad esempio, il numero $4$ può essere partizionato nei seguenti modi:
$$4=3+1=2+2=1+1+2=1+1+1+1$$
Un partizione di un numero $n$ in $k$ numeri naturali è un modo per scrivere $n$ come somma di $k$ numeri naturali.
Problema In quanti modi possiamo scegliere $a, b, c \ge 0$ tali che $a+b+c=8$?
Soluzione La soluzione usa un’idea molto utile in combinatoria. Immaginiamo di voler separare $8$ blocchetti bianchi in $3$ parti, usando dei blocchetti neri separatori (notiamo che ne servono $2$). Abbiamo, ad esempio:
$$\underbrace{\Box \Box \Box}_{a} \blacksquare \underbrace{\Box \Box \Box \Box}_{b} \blacksquare \underbrace{\Box}_{c}$$
che corrisponde a $a=3, b=4, c=1, (3+4+1=8).$ Questa è una possibilità. Spostando i blocchetti neri otteniamo tutte le possibili scelte di $a, b, c$, perché la somma dei blocchetti bianchi è sempre $8$. Un’altra possibile suddivisione è
$$\underbrace{\Box \Box}_{a} \blacksquare \underbrace{\Box \Box}_{b} \blacksquare \underbrace{\Box \Box \Box \Box}_{c}$$ o anche, se $a=0$: $$\underbrace{}_{a} \blacksquare \underbrace{\Box \Box \Box}_{b} \blacksquare \underbrace{\Box \Box \Box \Box \Box}_{c}$$
Se invece $a=b=0$:$$ \blacksquare \blacksquare \underbrace{\Box \Box \Box \Box \Box \Box \Box \Box}_{c}$$ Il problema adesso è diventato: in quanti modi possiamo posizionare i blocchetti neri? Vogliamo il numero di modi in cui possiamo mettere $2$ blocchetti (quelli neri) in un insieme di $8 \; \mbox{(i blocchetti bianchi)}+2 \; \mbox{(i blocchetti neri)=10}$ elementi, che è $ {10 \choose 2}=45. $
Pertanto abbiamo ottenuto la formula:
Dimostrazione. La dimostrazione usa la stessa idea della soluzione sopra. Il nostro problema è il seguente. Abbiamo:
$$ \underbrace{a+b+…+z}_{k} = n $$
con $a, b, c, …, z \ge 0$. In quanti modi possiamo scegliere $a, b, c, …, z$? Immaginiamo di nuovo di voler separare $n$ blocchetti bianchi in $k$ parti, usando dei blocchetti neri separatori (notiamo che ne servono $k-1$):
$$\underbrace{\Box \Box \Box}_{a} \blacksquare \underbrace{\Box \Box \Box \Box}_{b} \blacksquare \cdots \blacksquare \underbrace{\Box \Box}_{z}$$
Spostando i blocchetti neri otteniamo tutte le varie possibili scelte di $a, b, …, z$. Il problema adesso è diventato: in quanti modi possiamo posizionare i blocchetti neri? Vogliamo il numero di modi in cui possiamo mettere $k-1$ blocchetti neri in un insieme di $n+k-1$ blocchetti, che è $ {n+k-1 \choose k-1} $. Possiamo anche vederlo così: abbiamo $n+k-1$ blocchetti bianchi, e dobbiamo sceglierne $k-1$ e farli diventare neri. In quanti modi possiamo farlo? $\square$
Adesso affrontiamo una leggera variazione al problema di cui sopra, in cui $a, b$ e $c$ devono essere strettamente maggiori di $0$:
Problema In quanti modi possiamo scegliere $a, b, c > 0$ (strettamente) tali che $a+b+c=8$?
Soluzione. La prima idea sarebbe quella di prendere la formula per il caso $\ge 0$ e togliere tutte le partizioni in cui uno dei tre numeri è zero, che corrisponderebbe, nei blocchetti, a due neri vicini. Proviamo per un po’, ma ci rendiamo presto conto che non è semplice. Allora cambiamo un po’ l’idea iniziale.
Questa volta, invece di usare i blocchetti neri come separatori, li usiamo come parte integrante dei singoli numeri: se, ad esempio, $a$ vale $7$, lo rappresenteremo come $6$ blocchetti bianchi, e alla fine $1$ blocchetto nero. Ad esempio, se $n=9, a=3, b=4, c=2 $ abbiamo:
$$\underbrace{\Box \Box \blacksquare}_{a} \underbrace{\Box \Box \Box \blacksquare }_{b} \underbrace{\Box \blacksquare}_{c}$$
Notiamo che non è un problema avere due blocchetti neri vicini, come ad esempio così:
$$\underbrace{\Box \Box \Box \Box \blacksquare}_{a} \underbrace{\Box \Box \blacksquare }_{b} \underbrace{\blacksquare}_{c}$$
In questo modo, semplicemente $n=9, a=5, b=3, c=1$.
A questo punto il problema diventa: in quanti modi possiamo mettere i blocchetti neri.
L’intero blocco stavolta è lungo $n$ (perché i blocchetti neri non sono solo separatori, ma contano come parte integrante dei numeri). Inoltre l’ultimo blocchetto nero è fisso nell’ultima posizione, perché ogni blocco corrispondente ad una certa lettera finisce con un blocchetto nero.
A questo punto il problema è molto semplice: si tratta di scegliere $k-1$ blocchetti neri (ne servono $k$ perché ce n’è uno per ogni lettera, e l’ultimo è fisso), da $n-1$ blocchetti (l’ultimo è fisso). Questo si può fare in ${n-1 \choose k-1}$ modi.
Nel prossimo articolo affrontiamo il problema generale delle partizioni.