Regola di Pascal

In matematica, la regola di Pascal (o formula di Pascal) è un'identità combinatoria sui coefficienti binomiali. I coefficienti binomiali sono i numeri che compaiono nel triangolo di Tartaglia (noto anche come triangolo di Pascal). La regola di Pascal afferma che, per ogni coppia di interi positivi $n$ e $k$, $${\binom {n-1}{k}}+{\binom {n-1}{k-1}}={\binom {n}{k}},$$ dove ${\binom {n}{k}}$ è il coefficiente binomiale, cioè il coefficiente del termine $x^{k}$ nello sviluppo del polinomio $(1+x)^{n}$. Non ci sono restrizioni sulle grandezze relative di $n$ e $k$; in particolare, la suddetta identità rimane valida quando $n<k$, poiché ${\binom {n}{k}}=0$ ogni volta che $n<k$.

Insieme alle condizioni al contorno ${\binom {n}{0}}={\binom {n}{n}}=1$ per tutti gli interi non negativi $n$, la regola di Pascal determina che $${\binom {n}{k}}={\frac {n!}{k!(n-k)!}},$$ per tutti gli interi $0\leq k\leq n$. In questo senso, la regola di Pascal è la relazione di ricorrenza che definisce i coefficienti binomiali.

La regola di Pascal può anche essere generalizzata per essere applicata ai coefficienti multinomiali.

Dimostrazione combinatoria

Illustrazione della dimostrazione combinatoria: ${\binom {4}{1}}+{\binom {4}{2}}={\binom {5}{2}}.$

La regola di Pascal ha un significato combinatorio intuitivo, che è chiaramente espresso in questa dimostrazione per conteggio.

Dimostrazione. Si ricordi che ${\binom {n}{k}}$ è pari al numero di sottoinsiemi di $k$ elementi estratti da un insieme di $n$ elementi. Supponiamo che un particolare elemento sia etichettato in modo univoco con $X$ in un insieme di $n$ elementi.

Per costruire un sottoinsieme di $k$ elementi che contenga $X$, includiamo $X$ e scegliamo $k-1$ elementi tra i restanti $n-1$ elementi dell'insieme. Ci sono ${\binom {n-1}{k-1}}$ sottoinsiemi di questo tipo.

Per costruire un sottoinsieme di $k$ elementi che non contenga $X$, scegliamo $k$ elementi tra i restanti $n-1$ elementi dell'insieme. Ci sono ${\binom {n-1}{k}}$ sottoinsiemi di questo tipo.

Ogni sottoinsieme di $k$ elementi o contiene $X$ oppure non lo contiene. Il numero totale di sottoinsiemi con $k$ elementi presi da un insieme di $n$ elementi è la somma del numero di sottoinsiemi che contengono $X$ e del numero di sottoinsiemi che non lo contengono, ovvero ${\binom {n-1}{k-1}}+{\binom {n-1}{k}}$.

Questo totale è uguale a ${\binom {n}{k}}$; pertanto, ${\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}$.

Dimostrazione algebrica

In alternativa, segue la derivazione algebrica per il caso binomiale. $${\begin{aligned}{\binom {n-1}{k}}+{\binom {n-1}{k-1}}&={\frac {(n-1)!}{k!(n-1-k)!}}+{\frac {(n-1)!}{(k-1)!(n-k)!}}\\&=(n-1)!\left[{\frac {n-k}{k!(n-k)!}}+{\frac {k}{k!(n-k)!}}\right]\\&=(n-1)!{\frac {n}{k!(n-k)!}}\\&={\frac {n!}{k!(n-k)!}}\\&={\binom {n}{k}}.\end{aligned}}$$

Una dimostrazione algebrica alternativa utilizza la definizione alternativa dei coefficienti binomiali: ${\binom {n}{k}}={\frac {n(n-1)\cdots (n-k+1)}{k!}}$. Infatti:

$${\begin{aligned}{\binom {n-1}{k}}+{\binom {n-1}{k-1}}&={\frac {(n-1)\cdots ((n-1)-k+1)}{k!}}+{\frac {(n-1)\cdots ((n-1)-(k-1)+1)}{(k-1)!}}\\&={\frac {(n-1)\cdots (n-k)}{k!}}+{\frac {(n-1)\cdots (n-k+1)}{(k-1)!}}\\&={\frac {(n-1)\cdots (n-k+1)}{(k-1)!}}\left[{\frac {n-k}{k}}+1\right]\\&={\frac {(n-1)\cdots (n-k+1)}{(k-1)!}}\cdot {\frac {n}{k}}\\&={\frac {n(n-1)\cdots (n-k+1)}{k!}}\\&={\binom {n}{k}}.\end{aligned}}$$

Poiché ${\binom {z}{k}}={\frac {z(z-1)\cdots (z-k+1)}{k!}}$ è utilizzata come definizione estesa del coefficiente binomiale quando $z$ è un numero complesso, questa dimostrazione algebrica alternativa mostra che la regola di Pascal è valida più in generale quando $n$ è sostituito da un qualsiasi numero complesso.

Generalizzazione

La regola di Pascal può essere generalizzata ai coefficienti multinomiali. Per ogni intero $p$ tale che $p\geq 2$, con $k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {Z} ^{+}\!,$ e $n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1$, $${n-1 \choose k_{1}-1,k_{2},k_{3},\dots ,k_{p}}+{n-1 \choose k_{1},k_{2}-1,k_{3},\dots ,k_{p}}+\cdots +{n-1 \choose k_{1},k_{2},k_{3},\dots ,k_{p}-1}={n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}$$ dove ${n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}$ è il coefficiente del termine $x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{p}^{k_{p}}$ nello sviluppo di $(x_{1}+x_{2}+\dots +x_{p})^{n}$.

La derivazione algebrica per questo caso generale è la seguente. Sia $p$ un intero tale che $p\geq 2$, con $k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{+}\!,$ e $n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1$. Allora: $${\begin{aligned}&{}\quad {n-1 \choose k_{1}-1,k_{2},k_{3},\dots ,k_{p}}+{n-1 \choose k_{1},k_{2}-1,k_{3},\dots ,k_{p}}+\cdots +{n-1 \choose k_{1},k_{2},k_{3},\dots ,k_{p}-1}\\&={\frac {(n-1)!}{(k_{1}-1)!k_{2}!k_{3}!\cdots k_{p}!}}+{\frac {(n-1)!}{k_{1}!(k_{2}-1)!k_{3}!\cdots k_{p}!}}+\cdots +{\frac {(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots (k_{p}-1)!}}\\&={\frac {k_{1}(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}+{\frac {k_{2}(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}+\cdots +{\frac {k_{p}(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}={\frac {(k_{1}+k_{2}+\cdots +k_{p})(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}\\&={\frac {n(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}={\frac {n!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}={n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}.\end{aligned}}$$

Voci correlate

• Triangolo di Tartaglia

Bibliografia

• Russell Merris, Combinatorics (PDF), John Wiley & Sons, 2003, ISBN 978-0-471-26296-1.

Collegamenti esterni

• (EN) Eric W. Weisstein, Pascal's Formula, su MathWorld, Wolfram Research.
• (EN) Coefficiente binomiale centrale, su PlanetMath.
• (EN) Coefficiente binomiale, su PlanetMath.