15. Правило Паскаля и треугольник Паскаля
Число способов выбрать элементов из равно сумме двух чисел: способов, когда особый элемент не взят, и способов, когда он взят: . Из этого правила вырастает треугольник Паскаля — в нём каждое число равно сумме двух чисел над ним.
Что пригодится из прошлого: сочетания — формула с факториалами; симметрия и сумма ; правило суммы — выбор разбивается на непересекающиеся случаи. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Начнём с примера
Выберем двух человек из четырёх: . Всего пар. Сделаем одного человека, например , «особым» и разобьём все пары на две группы: в одной есть , в другой нет.
- есть a: {a, b}, {a, c}, {a, d} — пар: 3
- нет a: {b, c}, {b, d}, {c, d} — пар: 3
В первой группе уже взят; нужно выбрать ещё одного человека из трёх остальных: . Во второй группе не взят; нужно выбрать двоих из трёх остальных: . Группы не пересекаются, поэтому
Правило Паскаля
Следствие 3. Для
Докажем двумя способами: сначала рассуждением, потом вычислением.
Доказательство 1: по классам
Все сочетания без повторений из элементов по разобьём на два класса.
- Сочетания, содержащие элемент . Он уже выбран, остаётся выбрать элементов из оставшихся . Таких сочетаний .
- Сочетания, не содержащие элемент . Все элементов выбираются из оставшихся . Таких сочетаний .
Каждое сочетание попадает ровно в один класс: либо в нём есть, либо нет. По правилу суммы число всех сочетаний равно сумме двух чисел.
Доказательство 2: вычислением
Запишем обе дроби с факториалами:
Приведём к общему знаменателю . У первой дроби в знаменателе не хватает множителя : ведь . У второй — множителя : ведь . Умножим числитель и знаменатель каждой дроби на недостающий множитель:
Первое доказательство объясняет, почему правило верно; второе — проверяет формулу. Оба нужны: они согласуют две картины одного явления.
Треугольник Паскаля
Правило подсказывает способ строить числа без факториалов. Выпишем строки: в строке номер стоят числа .
- Края каждой строки — единицы: .
- Каждое число внутри равно сумме двух чисел, стоящих над ним слева и справа: так сказано в правиле Паскаля.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
Пример. В строке число получено из двух чисел строки , стоящих над ним: и . Вот этот кусочек:
строка 4: 4 6
╲ ╱
строка 5: 10
Как пользоваться треугольником.
- Строки и места нумеруются с нуля. Число — это строка , место . Например, : строка — это , место — число .
- Строки симметричны слева направо: это свойство .
- Сумма чисел строки равна : строки дают суммы — это следствие .
- Вторая диагональ — числа : это .
Частые ошибки
- Нумерация с единицы. Самая верхняя строка — «» — имеет номер ; место крайнего слева числа тоже .
- Складывать не те числа. Каждое число равно сумме двух верхних соседей (слева и справа сверху), а не соседей в той же строке.
- Забыть о краях. Крайние числа всегда — над ними только один сосед (другой считается нулём).
- Применять правило к краям. При и правило Паскаля не нужно: там просто .
Проверь себя
1. Проверьте правило Паскаля для , .
Решение
, а . Числа совпали.
2. Не используя формулу с факториалами, по строке найдите .
Решение
Строка : . По правилу Паскаля .
3. Продолжите треугольник до строки .
Решение
Строка : . Строка : . Строка : .
4. Объясните, почему сумма чисел каждой следующей строки в два раза больше суммы предыдущей.
Решение
Каждое число строки входит в слагаемые ровно двух чисел строки : стоящих под ним слева и справа (у крайних единиц второй «сосед» — нуль). Пример: от строки (, сумма ) к строке (, сумма ): первая входит в первую и в первую ; первая — в первую и в ; вторая — в и во вторую ; последняя — во вторую и в последнюю . Значит, при переходе к следующей строке сумма удваивается. В строке сумма , поэтому в строке она равна .
Итог
- : элемент либо в выборке (остальные из ), либо нет (все из ).
- Это правило строит треугольник Паскаля: каждое число — сумма двух чисел над ним.
- Строка , место (с нуля) — число ; строка симметрична, её сумма равна .
