Правило Паскаля

Немає цієї сторінки; ймовірно, її ще не перевіряли на відповідність правилам проекту.

Не плутати із законом Паскаля.

У математиці правило Паскаля (або формула Паскаля) — це комбінаторна тотожність щодо біноміальних коефіцієнтів. Вона стверджує, що для натуральних чисел ${\displaystyle n}$ і ${\displaystyle k}$ , справедливе наступне співвідношення:

${\displaystyle {n-1 \choose k}+{n-1 \choose k-1}={n \choose k},}$

де ${\displaystyle {\tbinom {n}{k}}}$ — біноміальний коефіцієнт; одна з інтерпретацій якого — це коефіцієнт при ${\displaystyle x^{k}}$ у ^[en] ${\displaystyle (1+x)^{n}}$. Не існує обмежень щодо відносних значень ${\displaystyle n}$ і ${\displaystyle k}$, оскільки, якщо ${\displaystyle n<k}$, то значення біноміального коефіцієнта дорівнює нулю, і тотожність залишається вірною.

Правило Паскаля також можна узагальнити на випадок мультиноміальних коефіцієнтів.

Комбінаторне доведення

Правило Паскаля допускає інтуїтивне комбінаторне розуміння, що чітко продемонстровано в цьому обчислювальному доведені.

Доведення. Нагадаємо, що ${\displaystyle {n \choose k}}$ — це кількість підмножин з ${\displaystyle k}$ елементів у множині з ${\displaystyle n}$ елементів. Припустимо, один конкретний елемент однозначно позначений як ${\displaystyle X}$ у наборі з ${\displaystyle n}$ елементів.

Для побудови підмножини з ${\displaystyle k}$ елементів, що містять ${\displaystyle X}$, виберемо ${\displaystyle X}$ та ${\displaystyle k-1}$ елементів із решти ${\displaystyle n-1}$ елементів множини. Є ${\displaystyle {n-1 \choose k-1}}$ таких підмножин.

Для побудови підмножини з ${\displaystyle k}$ елементів, що не містять ${\displaystyle X}$, виберемо ${\displaystyle k}$ елементів із решти ${\displaystyle n-1}$ елементів множини. Є ${\displaystyle {n-1 \choose k}}$ таких підмножин.

Кожна підмножина з ${\displaystyle k}$ елементів або містить ${\displaystyle X}$, або ні. Загальна кількість підмножин з ${\displaystyle k}$ елементами в множині з ${\displaystyle n}$ елементів — це сума кількості підмножин, що містять ${\displaystyle X}$, і кількості підмножин, які не містять ${\displaystyle X}$, ${\displaystyle {n-1 \choose k-1}+{n-1 \choose k}}$. Це дорівнює ${\displaystyle {n \choose k}}$, тому

${\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}.}$

Алгебраїчне доведення

Як альтернативу, можна вивести алгебраїчне доведення біноміального випадку

${\displaystyle {\begin{aligned}{n-1 \choose k}+{n-1 \choose 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)!}}\\&={n \choose k}.\end{aligned}}}$

Узагальнення

Правило Паскаля можна узагальнити на випадок мультиноміальних коефіцієнтів.

Для будь-якого натурального ${\displaystyle p}$, такого, що ${\displaystyle p\geq 2}$, ${\displaystyle {k_{1},k_{2},k_{3},\dots ,k_{p}}\in {\mathbb {N} }}$, і ${\displaystyle n=k_{1}+k_{2}+k_{3}+\dots +k_{p}\geq 1}$,

${\displaystyle {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}},}$

де ${\displaystyle {n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}}$ — коефіцієнт при ${\displaystyle x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{p}^{k_{p}}}$ у розкладі ${\displaystyle (x_{1}+x_{2}+\dots +x_{p})^{n}}$.

Алгебраїчне доведення для цього загального випадку полягає в наступному. Нехай ${\displaystyle p}$ --- натуральне число, таке, що ${\displaystyle p\geq 2}$, ${\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{+}\!,}$ and ${\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1}$. Тоді

${\displaystyle {\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}}}$

Див. також

• Трикутник Паскаля
• Бієктивне доведення

Посилання

1. Mazur, David R. (2010), Combinatorics / A Guided Tour, Mathematical Association of America, с. 60, ISBN 
2. Brualdi, Richard A. (2010), Introductory Combinatorics (вид. 5th), Prentice-Hall, с. 44, ISBN 
3. Brualdi, Richard A. (2010), Introductory Combinatorics (вид. 5th), Prentice-Hall, с. 144, ISBN 

Бібліографія

• Merris, Russell. Combinatorics. John Wiley & Sons. 2003

Зовнішні посилання

• Central binomial coefficient на PlanetMath
• Binomial coefficient на PlanetMath