Не плутати із законом Паскаля.
У математиці правило Паскаля (або формула Паскаля) — це комбінаторна тотожність щодо біноміальних коефіцієнтів. Вона стверджує, що для натуральних чисел і , справедливе наступне співвідношення:
де — біноміальний коефіцієнт; одна з інтерпретацій якого — це коефіцієнт при у . Не існує обмежень щодо відносних значень і , оскільки, якщо , то значення біноміального коефіцієнта дорівнює нулю, і тотожність залишається вірною.
Правило Паскаля також можна узагальнити на випадок мультиноміальних коефіцієнтів.
Комбінаторне доведення Правило Паскаля допускає інтуїтивне комбінаторне розуміння, що чітко продемонстровано в цьому обчислювальному доведені.
Доведення. Нагадаємо, що — це кількість підмножин з елементів у множині з елементів. Припустимо, один конкретний елемент однозначно позначений як у наборі з елементів.
Для побудови підмножини з елементів, що містять , виберемо та елементів із решти елементів множини. Є таких підмножин.
Для побудови підмножини з елементів, що не містять , виберемо елементів із решти елементів множини. Є таких підмножин.
Кожна підмножина з елементів або містить , або ні. Загальна кількість підмножин з елементами в множині з елементів — це сума кількості підмножин, що містять , і кількості підмножин, які не містять , . Це дорівнює , тому
Алгебраїчне доведення Як альтернативу, можна вивести алгебраїчне доведення біноміального випадку
Узагальнення Правило Паскаля можна узагальнити на випадок мультиноміальних коефіцієнтів.
Для будь-якого натурального , такого, що , , і ,
де — коефіцієнт при у розкладі .
Алгебраїчне доведення для цього загального випадку полягає в наступному. Нехай --- натуральне число, таке, що , and . Тоді
Див. також Трикутник Паскаля Бієктивне доведення
Посилання
Бібліографія
Merris, Russell. Combinatorics. John Wiley & Sons. 2003
Зовнішні посилання