Fattoriale, calcolo combinatorio e coefficienti binomiali

Questa nota costruisce il coefficiente binomiale $\binom{n}{k}$, che serve per scrivere il Binomio di NewtonLa formula per sviluppare (a+b)^n con i coefficienti binomiali.Binomio di Newton →. Si parte dal fattoriale, poi si contano permutazioni, disposizioni e combinazioni, e da lì si ricava la formula di $\binom{n}{k}$. Lezioni 2 e 3.

Il fattoriale

Per $n \in \mathbb{N}$:

$$n! = \begin{cases} 1 & \text{se } n = 0 \\ n(n-1)(n-2) \cdots 2 \cdot 1 & \text{se } n > 0 \end{cases}$$

Si legge "$n$ fattoriale": è il prodotto di tutti i naturali da $1$ a $n$.

Cresce molto in fretta (più di qualunque potenza $2^n$, $10^n$…: lo si vedrà con i limiti).

Definizione per ricorrenza. Equivalentemente:

$$0! = 1, \qquad (n+1)! = (n+1) \cdot n!$$

Ogni fattoriale si ottiene dal precedente moltiplicando per il numero successivo: $4! = 4 \cdot 3! = 4 \cdot 6 = 24$. Questo modo di definire "un passo alla volta" funziona grazie al Principio di induzionePer dimostrare una proprietà per ogni n basta il passo base e il passo induttivo da n a n+1.Principio di induzione →.

Perché $0! = 1$? È una convenzione, scelta perché fa funzionare tutte le formule: per esempio la ricorrenza con $n = 0$ dà $1! = 1 \cdot 0!$, che è vera solo se $0! = 1$; e le formule dei coefficienti binomiali qui sotto con $k = 0$ o $k = n$.

Un'identità utilissima

Per $0 \le k < n$, nel prodotto $n!$ si possono separare i primi $k$ fattori dagli altri:

$$n! = \underbrace{n(n-1)(n-2)\cdots(n-k+1)}_{k \text{ fattori}} \cdot \underbrace{(n-k)(n-k-1)\cdots 1}_{=(n-k)!}$$

quindi

$$n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!}$$

Esempio. $n = 6$, $k = 3$: l'ultimo fattore del primo gruppo è $n - k + 1 = 6 - 3 + 1 = 4$, e infatti $6! = 6 \cdot 5 \cdot 4 \cdot 3!$, quindi $6 \cdot 5 \cdot 4 = \frac{6!}{3!} = \frac{720}{6} = 120$ ✓.

Perché l'ultimo fattore è $n - k + 1$. I fattori sono $n, n-1, \dots$: il primo è $n - 0$, il secondo $n - 1$, …, il $k$-esimo è $n - (k-1) = n - k + 1$.

Attenzione alle parentesi: $2n! \ne (2n)!$

• $2n! = 2 \cdot (n!)$: il fattoriale si applica solo a $n$, poi si moltiplica per $2$.
• $(2n)! = (2n)(2n-1)(2n-2)\cdots 2 \cdot 1$: il fattoriale di $2n$.

Esempio $n = 3$: $2 \cdot 3! = 12$, mentre $6! = 720$. Usando l'identità di prima (con $2n$ al posto di $n$ e $k = n$):

$$(2n)! = 2n(2n-1)\cdots(n+1) \cdot n!$$

Calcolo combinatorio: contare le stringhe

Il fattoriale ha un significato concreto: conta in quanti modi si possono ordinare degli oggetti.

Permutazioni

Una permutazione di $n$ elementi è un modo di metterli in fila: una stringa ordinata, senza ripetizioni, lunga $n$, che usa tutti gli $n$ elementi.

$$|P_n| = n!$$

Perché. Si riempie la stringa una casella alla volta. Per la prima casella ci sono $n$ scelte; per la seconda ne restano $n - 1$ (un elemento è già usato); per la terza $n - 2$; …; per l'ultima $1$. Le scelte si moltiplicano (per ogni scelta della prima casella ci sono tutte le scelte della seconda, ecc.): $n(n-1)\cdots 1 = n!$.

Esempio. Le permutazioni di $\{1, 2, 3\}$ sono $123, 132, 213, 231, 312, 321$: sono $3! = 6$ ✓. Con $6$ elementi sono $6! = 720$.

Disposizioni

Una disposizione di $n$ elementi "a $k$ a $k$" (con $0 < k < n$) è una stringa ordinata, senza ripetizioni, lunga $k$, con elementi presi tra gli $n$.

$$|D_{n,k}| = n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!}$$

Perché. Come prima, ma ci si ferma dopo $k$ caselle: $n$ scelte per la prima, $n-1$ per la seconda, …, $n - k + 1$ per la $k$-esima. L'uguaglianza con $\frac{n!}{(n-k)!}$ è l'identità vista sopra.

Esempio. $n = 6$, $k = 3$: $|D_{6,3}| = 6 \cdot 5 \cdot 4 = 120$ (per esempio podi possibili con $6$ atleti: oro, argento, bronzo).

La seconda formula, $\frac{n!}{(n-k)!}$, vale anche per $0 \le k \le n$: con $k = n$ dà $\frac{n!}{0!} = n!$ (le permutazioni), con $k = 0$ dà $1$ (la stringa vuota).

Combinazioni

Una combinazione di $n$ elementi "a $k$ a $k$" è una scelta di $k$ elementi tra gli $n$, senza ripetizioni e senza ordine: in pratica, un sottoinsieme di $k$ elementi.

Esempio della prof. $n = 3$, elementi $\{1, 2, 3\}$, $k = 2$. Le disposizioni sono $6$:

$$12, \ 21, \qquad 13, \ 31, \qquad 23, \ 32$$

ma come combinazioni $12$ e $21$ sono la stessa cosa (lo stesso sottoinsieme $\{1, 2\}$), e così via. Le combinazioni sono quindi $3$: $\{1,2\}, \{1,3\}, \{2,3\}$.

La formula. Ogni combinazione di $k$ elementi corrisponde a $k!$ disposizioni (tutti i modi di ordinare quei $k$ elementi). Quindi le disposizioni sono $k!$ volte le combinazioni, e

$$|C_{n,k}| = \frac{|D_{n,k}|}{k!} = \frac{n(n-1)\cdots(n-k+1)}{k!} = \frac{n!}{k!\,(n-k)!}$$

Nell'esempio: $\frac{6}{2!} = 3$ ✓.

Il coefficiente binomiale

$$\binom{n}{k} = \frac{n!}{k!\,(n-k)!} \quad (0 \le k \le n) \qquad = \frac{n(n-1)\cdots(n-k+1)}{k!} \quad (0 < k < n)$$

Si legge "$n$ su $k$". Per quanto visto, $\binom{n}{k}$ è il numero di sottoinsiemi di $k$ elementi di un insieme con $n$ elementi.

Quale formula usare. La seconda (con $k$ fattori sopra e $k!$ sotto) è quella più rapida nei conti: si scrivono $k$ fattori decrescenti partendo da $n$ e si divide per $k!$.

Esempi

$$\binom{5}{3} = \frac{5 \cdot 4 \cdot 3}{3!} = \frac{60}{6} = 10 \qquad\text{oppure}\qquad \binom{5}{3} = \frac{5!}{3!\,2!} = \frac{120}{6 \cdot 2} = 10$$

(nella prima, i fattori sono $3$ perché $k = 3$, e l'ultimo è $n - k + 1 = 5 - 3 + 1 = 3$).

Valori da ricordare (per ogni $n$):

• $\binom{0}{0} = \frac{0!}{0!\,0!} = 1$;
• $\binom{n}{0} = \frac{n!}{0!\,n!} = 1$ e $\binom{n}{n} = \frac{n!}{n!\,0!} = 1$ (c'è un solo sottoinsieme vuoto e un solo sottoinsieme con tutti gli elementi);
• $\binom{n}{1} = \frac{n!}{1!\,(n-1)!} = \frac{n \cdot (n-1)!}{(n-1)!} = n$ (i sottoinsiemi con un elemento sono $n$);
• $\binom{n}{n-3} = \frac{n!}{(n-3)!\,3!} = \frac{n(n-1)(n-2)\,(n-3)!}{6\,(n-3)!} = \frac{n(n-1)(n-2)}{6}$.

Proprietà

1. Simmetria:

$$\binom{n}{k} = \binom{n}{n-k}$$

Con la formula: $\binom{n}{n-k} = \frac{n!}{(n-k)!\,(n - (n-k))!} = \frac{n!}{(n-k)!\,k!}$, che è proprio $\binom{n}{k}$.

Con il significato (spiegazione della prof): scegliere i $k$ elementi da prendere equivale a scegliere gli $n - k$ elementi da lasciare. Ogni sottoinsieme di $k$ elementi corrisponde esattamente a uno di $n - k$ elementi (il suo complementare), quindi sono in ugual numero.

Esempio: $\binom{5}{3} = \binom{5}{2} = \frac{5 \cdot 4}{2} = 10$ (conviene calcolare quello con il $k$ più piccolo).

2. Formula di Stifel (per $0 < k < n$):

$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$

Con il significato (spiegazione della prof): fissiamo un elemento particolare, diciamo $\star$, tra gli $n$. I sottoinsiemi di $k$ elementi si dividono in due gruppi disgiunti:

• quelli che contengono $\star$: oltre a $\star$ bisogna scegliere altri $k - 1$ elementi tra i restanti $n - 1$, e ci sono $\binom{n-1}{k-1}$ modi;
• quelli che non contengono $\star$: bisogna scegliere tutti i $k$ elementi tra gli altri $n - 1$, in $\binom{n-1}{k}$ modi.

Sommando i due gruppi (sono disgiunti, quindi non si conta niente due volte) si ottengono tutti i sottoinsiemi di $k$ elementi.

Con la formula (verifica algebrica):

$$\binom{n-1}{k-1} + \binom{n-1}{k} = \frac{(n-1)!}{(k-1)!\,(n-k)!} + \frac{(n-1)!}{k!\,(n-1-k)!}$$

Si porta tutto al denominatore comune $k!\,(n-k)!$: nella prima frazione si moltiplica sopra e sotto per $k$ (perché $k \cdot (k-1)! = k!$), nella seconda per $n - k$ (perché $(n-k)(n-k-1)! = (n-k)!$):

$$= \frac{(n-1)!\,k + (n-1)!\,(n-k)}{k!\,(n-k)!} = \frac{(n-1)!\,(k + n - k)}{k!\,(n-k)!} = \frac{(n-1)!\,n}{k!\,(n-k)!} = \frac{n!}{k!\,(n-k)!} = \binom{n}{k}$$

Esempio: $\binom{5}{2} = \binom{4}{1} + \binom{4}{2} = 4 + 6 = 10$ ✓.

Il triangolo di Tartaglia

La formula di Stifel dice che ogni coefficiente è la somma dei due che gli stanno sopra. Disponendo i coefficienti a triangolo (riga $n$ = i valori $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$), ogni riga si costruisce dalla precedente:

Come si costruisce. Ai bordi ci sono sempre $1$ (perché $\binom{n}{0} = \binom{n}{n} = 1$). Ogni numero interno è la somma dei due numeri della riga sopra che stanno a sinistra e a destra di lui. Per esempio nella riga $n = 3$: $3 = 1 + 2$ (cioè $\binom{3}{1} = \binom{2}{0} + \binom{2}{1}$) e l'altro $3 = 2 + 1$ ($\binom{3}{2} = \binom{2}{1} + \binom{2}{2}$). Nella riga $5$: $10 = 4 + 6$.

Ogni riga è simmetrica (si legge uguale da sinistra e da destra): è la proprietà di simmetria.

Controllo: la somma della riga $n$ è $2^n$ ($1 + 3 + 3 + 1 = 8 = 2^3$; $1 + 4 + 6 + 4 + 1 = 16 = 2^4$). Non è un caso: è il numero totale di sottoinsiemi di un insieme con $n$ elementi (vedi Insiemi e insieme delle partiCome si descrive un insieme, sottoinsiemi, uguaglianza, insieme delle parti e insiemi finiti e infiniti.Insiemi e insieme delle parti →), e si ottiene dal Binomio di NewtonLa formula per sviluppare (a+b)^n con i coefficienti binomiali.Binomio di Newton → con $a = b = 1$.

Errori comuni

• $0! = 0$: falso, $0! = 1$.
• $2n! = (2n)!$: falso (vedi sopra).
• Semplificare male: $\frac{6!}{3!} \ne 2!$. Si semplifica scrivendo $6! = 6 \cdot 5 \cdot 4 \cdot 3!$: $\frac{6!}{3!} = 6 \cdot 5 \cdot 4 = 120$.
• Contare i fattori sbagliati in $n(n-1)\cdots(n-k+1)$: sono $k$ fattori.
• Confondere disposizioni e combinazioni: se l'ordine conta → disposizioni; se conta solo quali elementi si scelgono → combinazioni ($\binom{n}{k}$).