Правило Паскаля - Pascals rule - Wikipedia

В математика, Правило Паскаля (или же Формула Паскаля) это комбинаторный личность о биномиальные коэффициенты. В нем говорится, что для положительного натуральные числа п и k,

куда - биномиальный коэффициент; одна интерпретация которого - коэффициент Иксk срок в расширение из (1 + Икс)п. Нет ограничений на относительные размеры п и k,[1] поскольку, если п < k значение биномиального коэффициента равно нулю, и тождество остается в силе.

Правило Паскаля также может рассматриваться как утверждение, что формула

решает линейное двумерное разностное уравнение

над натуральными числами. Таким образом, правило Паскаля также является утверждением формулы для чисел, появляющихся в Треугольник Паскаля.


Правило Паскаля также может быть обобщено для применения к полиномиальные коэффициенты.

Комбинаторное доказательство

Паскаля Правило имеет интуитивно-комбинаторное значение, которое ясно выражено в этом доказательстве подсчета.[2]

Доказательство. Напомним, что равно количеству подмножества с k элементы из набор с п элементы. Предположим, что один конкретный элемент однозначно помечен Икс в комплекте с п элементы.

Чтобы построить подмножество k элементы, содержащие Икс, выберите Икс и k - 1 элемент из оставшихся п - 1 элемент в наборе. Есть такие подмножества.

Чтобы построить подмножество k элементы нет содержащий Икс, выберите k элементы из оставшихся п - 1 элемент в наборе. Есть такие подмножества.

Каждое подмножество k элементы либо содержат Икс или нет. Общее количество подмножеств с k элементы в наборе п элементов - это сумма количества подмножеств, содержащих Икс и количество подмножеств, не содержащих Икс, .

Это равно ; следовательно, .

Алгебраическое доказательство

В качестве альтернативы следует алгебраический вывод биномиального случая.

Обобщение

Правило Паскаля можно обобщить на полиномиальные коэффициенты.[3] Для любого целое число п такой, что , и ,

куда коэффициент при срок в расширении .

Алгебраический вывод для этого общего случая следующий.[3] Позволять п быть таким целым числом, что , и . потом

Смотрите также

Рекомендации

  1. ^ Мазур, Дэвид Р. (2010), Комбинаторика / Экскурсия, Математическая ассоциация Америки, стр. 60, ISBN  978-0-88385-762-5
  2. ^ Бруальди, Ричард А. (2010), Вводная комбинаторика (5-е изд.), Прентис-Холл, стр. 44, ISBN  978-0-13-602040-0
  3. ^ а б Бруальди, Ричард А. (2010), Вводная комбинаторика (5-е изд.), Прентис-Холл, стр. 144, ISBN  978-0-13-602040-0

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

внешняя ссылка

В этой статье использованы материалы из Треугольник Паскаля на PlanetMath, который находится под лицензией Лицензия Creative Commons Attribution / Share-Alike.

В этой статье использованы материалы из Доказательство правила Паскаля на PlanetMath, который находится под лицензией Лицензия Creative Commons Attribution / Share-Alike.