Regula lui Pascal

Regula lui Pascal este o identitate combinatorie pentru coeficienții binomi . Regula spune că pentru orice număr natural n avem

{n-1 \alegeți k}+{n-1 \alegeți k-1}={n \alegeți k)

pentru ,

1\leqslant k\leqslant n

unde este coeficientul binom. De asemenea, este adesea scris ca ${n \alege k}$

{n \alegeți k}+{n \alegeți k-1}={n+1 \alegeți k)

pentru

1\leqslant k\leqslant n+1

Dovada combinatorie

Regula lui Pascal are un sens combinatoriu intuitiv. Amintiți-vă că numără câte moduri poate fi ales o submulțime cu b elemente dintr- o mulțime cu elemente. Astfel, partea dreaptă a identității numără de câte moduri se poate obține o k -submulțime dintr-o mulțime cu n elemente. ${a \alege b}$ ${n \alege k}$

Acum imaginați-vă că selectați un anumit element X dintr-o mulțime cu n elemente. Astfel, de fiecare dată când selectați k elemente dintr-un submult, există două posibilități - X aparține submulțimii selectate sau nu.

Dacă X este în submulțime, atunci trebuie doar să alegem k − 1 obiecte suplimentare (deoarece se știe că X este în submulțime) din restul de n − 1 obiecte. Acest lucru se poate face în moduri. $n-1\alegeți k-1$

Dacă X nu aparține unei submulțimi, atunci trebuie să selectați toate k elemente dintr-o submulțime constând din n − 1 obiecte care nu sunt egale cu X . Acest lucru se poate face în moduri. $n-1 \alege k$

Obținem că numărul de moduri de a obține o k -submulțime dintr -o mulțime de n -element, care, după cum știm, este , este, de asemenea, egal cu numărul ${n \alege k}$ ${n-1 \choose k-1}+{n-1 \choose k}.$

Vezi și Dovada bijectivă .

Dovada algebrică

Trebuie demonstrat că

{n \alegeți k}+{n \alegeți k-1}={n+1 \alegeți k}.

{\begin{aligned}{n \choose k}+{n \choose k-1}&={\frac {n!}{k!(nk)!}}+{\frac {n!} {(k-1)!(n-k+1)!}}\\&=n!\left[{\frac {n-k+1}{k!(n-k+1)!}}+ {\frac {k}{k!(n-k+1)!}}\dreapta]\\&={\frac {n!(n+1)}{k!(n-k+1)!} }={\binom {n+1}{k}}\end{aliniat}}

Generalizare

Lasă și . Apoi $n,k_{1},k_{2},k_{3},\dots,k_{p},p\in \mathbb {N} ^{*}$ ${\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p))$

{\begin{aligned}&{}\quad {n-1 \choose k_{1}-1,k_{2},k_{3},\dots,k_{p))+{n-1 \alegeți k_{1},k_{2}-1,k_{3},\dots ,k_{p}}+\cdots +{n-1 \alegeți 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 \alegeți k_{1},k_{2},k_{3},\dots ,k_{p}}.\end{aligned}}

Vezi și

triunghiul lui Pascal

Note

Literatură

Acest articol încorporează material din articolul „Regula lui Pascal” de pe site-ul PlanetMath , publicat sub licență de la CCA-SA
Acest articol încorporează material din articolul „Dovada regulii lui Pascal” de pe site-ul PlanetMath , publicat sub licență de la CCA-SA
Russell Merris. combinatorii . - John Wiley & Sons., 2003. - ISBN 978-0-471-26296-1 .