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

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

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

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

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

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

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

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

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

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

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

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

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}) .

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

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

\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}

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

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

Для будь-якого натурального $p$ , такого, що $p \geq 2$ , $k_{1}, k_{2}, k_{3}, \dots, k_{p} \in ℕ$ , і $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}}),

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

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

\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}

Див. також

Посилання

Шаблон:Reflist

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

Merris, Russell. Combinatorics. John Wiley & Sons. 2003 Шаблон:ISBN

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

[1] Шаблон:Citation

[2] Шаблон:Citation

[Brualdi-3] Шаблон:Citation

[1]

[2]

[3]

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

Зміст

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

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

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

Див. також

Посилання

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

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

Навігаційне меню

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

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

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

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

Див. також

Посилання

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

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

Навігаційне меню

Пошук