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

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{matrix} (\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)! [\frac{n - k}{k! (n - k)!} + \frac{k}{k! (n - k)!}] \\ = (n - 1)! \frac{n}{k! (n - k)!} \\ = \frac{n!}{k! (n - k)!} \\ = (\binom{n}{k}) . \end{matrix}$

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

$\begin{matrix} (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) & = \frac{(n - 1) \dots ((n - 1) - k + 1)}{k!} + \frac{(n - 1) \dots ((n - 1) - (k - 1) + 1)}{(k - 1)!} \\ = \frac{(n - 1) \dots (n - k)}{k!} + \frac{(n - 1) \dots (n - k + 1)}{(k - 1)!} \\ = \frac{(n - 1) \dots (n - k + 1)}{(k - 1)!} [\frac{n - k}{k} + 1] \\ = \frac{(n - 1) \dots (n - k + 1)}{(k - 1)!} \cdot \frac{n}{k} \\ = \frac{n (n - 1) \dots (n - k + 1)}{k!} \\ = (\binom{n}{k}) . \end{matrix}$

Poiché $(\binom{z}{k}) = \frac{z (z - 1) \dots (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 ℤ^{+},$ e $n = k_{1} + k_{2} + k_{3} + \dots + k_{p} \geq 1$ , $(\binom{n - 1}{k_{1} - 1, k_{2}, k_{3}, \dots, k_{p}}) + (\binom{n - 1}{k_{1}, k_{2} - 1, k_{3}, \dots, k_{p}}) + \dots + (\binom{n - 1}{k_{1}, k_{2}, k_{3}, \dots, k_{p} - 1}) = (\binom{n}{k_{1}, k_{2}, k_{3}, \dots, k_{p}})$ dove $(\binom{n}{k_{1}, k_{2}, k_{3}, \dots, k_{p}})$ è il coefficiente del termine $x_{1}^{k_{1}} x_{2}^{k_{2}} \dots 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 ℕ^{+},$ e $n = k_{1} + k_{2} + k_{3} + \dots + k_{p} \geq 1$ . Allora: $\begin{matrix} (\binom{n - 1}{k_{1} - 1, k_{2}, k_{3}, \dots, k_{p}}) + (\binom{n - 1}{k_{1}, k_{2} - 1, k_{3}, \dots, k_{p}}) + \dots + (\binom{n - 1}{k_{1}, k_{2}, k_{3}, \dots, k_{p} - 1}) \\ = \frac{(n - 1)!}{(k_{1} - 1)! k_{2}! k_{3}! \dots k_{p}!} + \frac{(n - 1)!}{k_{1}! (k_{2} - 1)! k_{3}! \dots k_{p}!} + \dots + \frac{(n - 1)!}{k_{1}! k_{2}! k_{3}! \dots (k_{p} - 1)!} \\ = \frac{k_{1} (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} + \frac{k_{2} (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} + \dots + \frac{k_{p} (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} = \frac{(k_{1} + k_{2} + \dots + k_{p}) (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} \\ = \frac{n (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} = \frac{n!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} = (\binom{n}{k_{1}, k_{2}, k_{3}, \dots, k_{p}}) . \end{matrix}$

Note

↑ David R. Mazur, Combinatorics: A Guided Tour, Mathematical Association of America, 2010, p. 60, ISBN 978-0-88385-762-5.
↑ Richard A. Brualdi, Introductory Combinatorics, 5ª ed., Prentice-Hall, 2010, p. 44, ISBN 978-0-13-602040-0.
↑ Richard A. Brualdi, Introductory Combinatorics, 5ª ed., Prentice-Hall, 2010, p. 144, ISBN 978-0-13-602040-0.

Bibliografia

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

Voci correlate

Triangolo di Tartaglia

Collegamenti esterni

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

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

[1] David R. Mazur, Combinatorics: A Guided Tour, Mathematical Association of America, 2010, p. 60, ISBN 978-0-88385-762-5.

[Brualdi44-2] Richard A. Brualdi, Introductory Combinatorics, 5ª ed., Prentice-Hall, 2010, p. 44, ISBN 978-0-13-602040-0.

[Brualdi144-3] Richard A. Brualdi, Introductory Combinatorics, 5ª ed., Prentice-Hall, 2010, p. 144, ISBN 978-0-13-602040-0.