Карточки
Тесты
Зави
Треугольник Паскаля
Треугольник Паскаля
В уроке «Перестановки, факториал, сочетания» мы научились считать сочетания $C_n^k$ по формуле. Сегодня построим таблицу, в которой все числа $C_n^k$ уже вычислены и выстроены в треугольник, — треугольник Паскаля. Разберем, почему каждое его число — сумма двух над ним, и решим с ним задачи о путях, подмножествах, скобках и монетах.
Вопрос, на который ответим в конце урока. Район разбит улицами на квадратные кварталы $4 \times 4$. Пешеход идет из угла $A$ в угол $B$ кратчайшим путем, то есть только вправо или вверх. Сколько существует разных кратчайших путей?
В каждую точку приходят только из двух точек над ней
Возьмем дерево выборов, в котором на каждом ярусе всего два выбора: шаг влево-вниз или шаг вправо-вниз. В уроке «Комбинаторное правило умножения» каждый путь заканчивался своим листом. Теперь пути сходятся: «влево, потом вправо» и «вправо, потом влево» приводят в одну и ту же точку. Напишем в каждой точке, сколько путей ведет в нее от вершины.
В вершине стоит $1$. На ярусе $1$ две точки, в каждую ведет один путь. В среднюю точку яруса $2$ приходят и слева, и справа: $1+1=2$ пути. В точку яруса $3$ приходят из двух точек яруса $2$, где $1$ и $2$ пути, — всего $1+2=3$. Крайние точки достижимы одним путем: все время влево или все время вправо. Поэтому по краям стоят единицы.
Пути, пришедшие слева и справа, разные: у них разный последний шаг. Поэтому их число складывается, а не перемножается. Так получается правило, по которому таблицу можно продолжать без рисования путей.
Определение
Треугольник Паскаля — таблица чисел в форме треугольника: в вершине и по краям каждой строки стоят единицы, а каждое число внутри равно сумме двух чисел над ним.
Строки нумеруют с нуля: вершина — строка $0$. Числа в строке тоже нумеруют с нуля: крайняя левая единица стоит на месте $0$.
Обратите внимание
Номер строки — это число шагов от вершины. В строке $n$ стоит $n+1$ число, и второе число строки равно ее номеру: строка $1, 4, 6, 4, 1$ — строка $4$.
Пример 1
Задача. Строка $4$ треугольника: $1, 4, 6, 4, 1$. Постройте строки $5$ и $6$.
Решение. По краям ставим единицы, внутри складываем соседние числа строки выше.
Строка $5$: $1$, $1+4=5$, $4+6=10$, $6+4=10$, $4+1=5$, $1$.
Строка $6$: $1$, $1+5=6$, $5+10=15$, $10+10=20$, $10+5=15$, $5+1=6$, $1$.
Проверка: в строке $6$ семь чисел, второе равно $6$.
Ответ: $1, 5, 10, 10, 5, 1$ и $1, 6, 15, 20, 15, 6, 1$.
Интересный факт: откуда название
Скрыть
Треугольник назван в честь французского ученого Блеза Паскаля: его «Трактат об арифметическом треугольнике» написан в 1654 году, а напечатан в 1665 году, уже после смерти автора. Но сама таблица гораздо старше. В Китае ее изобразил Чжу Шицзе в книге 1303 года и назвал «старым способом». В Иране с ней связывают имя Омара Хайяма: он упоминал правило возведения суммы в степень, но его трактат не сохранился.
Сетка улиц — тот же треугольник, только повернутый
Возьмем сетку из $3$ кварталов вправо и $2$ вверх. Идем из нижнего левого угла $A$ в верхний правый $B$ только вправо или вверх. В любой перекресток можно прийти только с двух сторон: слева или снизу. Значит, число путей в перекресток равно сумме чисел в соседнем левом и соседнем нижнем перекрестках. На нижней и на левой улице стоят единицы: туда ведет один путь, прямо.
Заполним сетку снизу вверх. Нижняя улица: $1, 1, 1, 1$. Следующая: $1$, $1+1=2$, $2+1=3$, $3+1=4$. Верхняя: $1$, $1+2=3$, $3+3=6$, $6+4=10$. В $B$ ведут $10$ путей.
Поверните сетку так, чтобы $A$ оказалась наверху. Перекрестки, до которых одинаковое число шагов, лягут в одну строку. Через $2$ шага — числа $1, 2, 1$, через $3$ шага — $1, 3, 3, 1$. Это строки треугольника Паскаля: шаг вправо по сетке — шаг влево-вниз в треугольнике, шаг вверх — вправо-вниз. До $B$ ровно $5$ шагов, и в строке $5$ на месте $2$ тоже стоит $10$.
Число в треугольнике считает, какие шаги выбраны
Путь из вершины в строку $n$ состоит из $n$ шагов. Если путь пришел на место $k$, то ровно $k$ шагов из $n$ сделаны вправо, остальные — влево. Путь полностью задается тем, какие $k$ шагов из $n$ идут вправо. Выбрать $k$ номеров шагов из $n$, когда порядок выбора не важен, можно $C_n^k$ способами. Проверим: в строке $5$ на месте $2$ стоит $10$, и по формуле $C_5^2=\dfrac{5 \cdot 4}{2 \cdot 1}=10$.
Теорема
В строке $n$ треугольника Паскаля на месте $k$ стоит число сочетаний $C_n^k$. Правило «сумма двух над числом» в этих обозначениях при $1 \le k \le n-1$:
$$C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$$
Почему это верно и без рисунка. Выбираем команду из $k$ человек среди $n$. Посмотрим на последнего, $n$-го человека. Либо он в команде — тогда остальных $k-1$ выбираем из $n-1$ человека: $C_{n-1}^{k-1}$ способов. Либо его нет — тогда всех $k$ выбираем из $n-1$: $C_{n-1}^k$ способов. Третьего не дано, и одна команда не попадает в оба случая. Поэтому способы складываются. В дереве это тот же вопрос: каким был последний шаг пути.
Пример 2
Задача. В группе $6$ человек: Аня, Боря, Вика, Гриша, Даша и Женя. Выбирают $2$ дежурных. Найдите число способов без формулы сочетаний.
Решение. 1) Женя дежурит. Напарника выбираем из пяти остальных: $C_5^1=5$ способов. 2) Женя не дежурит. Обоих выбираем из пяти: $C_5^2=10$ способов (строка $5$, место $2$). 3) Случаи не пересекаются, складываем: $5+10=15$.
Проверка по формуле: $C_6^2=\dfrac{6 \cdot 5}{2 \cdot 1}=15$. В строке $6$ на месте $2$ стоит $15$.
Ответ: $15$.
Ошибка
Решавр ищет $C_6^4$: «Строка $1, 5, 10, 10, 5, 1$ — шестая сверху, на месте $4$ в ней стоит $5$. Значит, $C_6^4=5$».
Проверим. По формуле $C_6^4=\dfrac{6 \cdot 5 \cdot 4 \cdot 3}{4 \cdot 3 \cdot 2 \cdot 1}=15$, а не $5$. Второе число строки $1, 5, 10, 10, 5, 1$ равно $5$ — это строка $5$. В строке $6$, то есть $1, 6, 15, 20, 15, 6, 1$, на месте $4$ стоит $15$.
Где сломалось рассуждение: Решавр начал счет строк с единицы. Вершина — строка $0$: до нее ноль шагов. Поэтому шестая сверху строка имеет номер $5$.
Строка читается одинаково с обоих концов, а ее сумма удваивается
Симметрия. Отразим путь зеркально: каждый шаг влево заменим шагом вправо и наоборот. Путь, в котором $k$ шагов вправо, превратится в путь с $k$ шагами влево, то есть с $n-k$ шагами вправо. Пути разбились на пары, поэтому $C_n^k=C_n^{n-k}$: в строке $6$ на местах $2$ и $4$ стоит по $15$.
Сумма строки. Каждый путь из $n$ шагов приходит в какую-то точку строки $n$. Значит, сумма чисел строки — это число всех путей из $n$ шагов. На каждом шаге $2$ выбора, по правилу умножения путей $2 \cdot 2 \cdot \ldots \cdot 2=2^n$. По построению то же: каждое число строки входит в две суммы ниже, поэтому следующая строка в сумме вдвое больше.
Свойства
1) По краям строки $n$ стоят единицы, рядом с ними — число $n$: $C_n^0=C_n^n=1$, $C_n^1=n$.
2) Строка симметрична:
$$C_n^k=C_n^{n-k}$$
3) Сумма чисел строки $n$ равна $2^n$:
$$C_n^0+C_n^1+\ldots+C_n^n=2^n$$
Ошибка
Решавр пишет: «В строке $6$ стоят числа $1, 6, 15, 20, 15, 6, 1$. Их сумма равна номеру строки, то есть $6$».
Проверим сложением: $1+6+15+20+15+6+1=64=2^6$. Да и одно число $20$ уже больше $6$.
Где сломалось рассуждение: номер строки — это число шагов пути, а сумма строки — число всех путей из этих шагов. Шагов $6$, а путей $2^6=64$.
Та же модель считает подмножества. Пусть есть $n$ предметов. Подмножество задается тем, берем ли мы каждый предмет: «взять» — шаг вправо, «не взять» — шаг влево. Подмножество из $k$ предметов — путь с $k$ шагами вправо, таких $C_n^k$. Всех подмножеств, включая пустое и само множество, — $2^n$.
Пример 3
Задача. В пиццерии к основе можно добавить любые из $5$ начинок: сыр, грибы, оливки, перец, ветчину. Можно не добавлять ничего, можно добавить все. Сколько разных пицц можно заказать?
Решение. Для каждой начинки $2$ выбора: добавить или нет. По правилу умножения $2^5=32$.
Проверка по строке $5$: без начинок — $1$ пицца, с одной — $5$, с двумя — $10$, с тремя — $10$, с четырьмя — $5$, со всеми — $1$. Сумма $1+5+10+10+5+1=32$.
Ответ: $32$.
Проверьте все правила сразу: сумму двух над числом, место $C_n^k$, симметрию и сумму строки. Сначала сделайте прогноз сами, потом сверьтесь с треугольником.
Скобки, монеты и улицы считаются одной строкой
В уроке «Квадрат суммы и квадрат разности» вы раскрывали $(a+b)^2=a^2+2ab+b^2$. Коэффициенты $1, 2, 1$ — это строка $2$. Посмотрим, почему так. Запишем $(a+b)^4=(a+b)(a+b)(a+b)(a+b)$. Раскрыть скобки — значит из каждой скобки взять $a$ или $b$ и перемножить взятое. Это путь из $4$ шагов: «$a$» — влево, «$b$» — вправо. Слагаемое $a^2b^2$ получается, когда $b$ взято из $2$ скобок из $4$: так бывает $C_4^2=6$ раз.
Правило
Коэффициенты после раскрытия скобок в $(a+b)^n$ — это строка $n$ треугольника Паскаля. Например, по строке $4$:
$$(a+b)^4=a^4+4a^3b+6a^2b^2+4ab^3+b^4$$
Ошибка
Решавр пишет: «$(a+b)^4=a^4+b^4$».
Проверим при $a=b=1$: слева $(1+1)^4=16$, справа $1^4+1^4=2$. Равенство неверно.
Где сломалось рассуждение: Решавр учел только два пути — «все время $a$» и «все время $b$», то есть края строки. Средние слагаемые $4a^3b+6a^2b^2+4ab^3$ потеряны. При $a=b=1$ каждое слагаемое равно своему коэффициенту, поэтому должна получиться сумма строки $4$: $2^4=16$.
Броски монеты устроены так же: каждый бросок — шаг «орел» или «решка». При $n$ бросках все $2^n$ последовательностей равновозможны, а последовательностей ровно с $k$ орлами $C_n^k$. Это число стоит в строке $n$ на месте $k$.
Пример 4
Задача. Монету бросают $5$ раз. Найдите вероятность того, что орел выпадет ровно $2$ раза.
Решение. 1) Всех исходов $2^5=32$: это последовательности из $5$ бросков. 2) Благоприятных — где орлы стоят на $2$ местах из $5$: $C_5^2=10$ (строка $5$, место $2$). 3) $P=\dfrac{10}{32}=\dfrac{5}{16}$.
Проверка смысла: $\dfrac{5}{16}\approx 0{,}31$ — меньше половины: возможно и другое число орлов.
Ответ: $\frac{5}{16}$.
Вернемся к вопросу из начала урока. Кратчайший путь по сетке $4 \times 4$ — это $8$ шагов: $4$ вправо и $4$ вверх. Путь задается тем, какие $4$ шага из $8$ идут вверх, поэтому путей $C_8^4=\dfrac{8 \cdot 7 \cdot 6 \cdot 5}{4 \cdot 3 \cdot 2 \cdot 1}=70$. Тот же ответ дает и сетка: в $B$ приходят из двух соседних перекрестков, где по $35$ путей, а $35+35=70$.
Вывод
Треугольник Паскаля — готовая таблица сочетаний: в строке $n$ на месте $k$ стоит $C_n^k$. Его не нужно запоминать — достаточно помнить, как он строится: в точку приходят только из двух точек над ней, поэтому число равно сумме двух чисел над ним. Он пригодится, когда нужно быстро найти $C_n^k$ для небольших $n$, сосчитать пути, подмножества, коэффициенты $(a+b)^n$ или вероятность «ровно $k$ успехов из $n$».
Как быстро вспомнить главное через модель «дерево выборов, где пути сходятся»:
| Вопрос | Что это в модели | Ответ |
|---|---|---|
| Почему сумма двух над числом | В точку приходят только из двух точек выше | $C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$ |
| Какой номер у строки | Число шагов от вершины; второе число строки | Вершина — строка $0$ |
| Чему равно число в строке | Сколькими способами выбрать $k$ шагов вправо из $n$ | $C_n^k$ |
| Почему строка симметрична | Зеркальный путь: вправо и влево меняются | $C_n^k=C_n^{n-k}$ |
| Чему равна сумма строки | Все пути из $n$ шагов по $2$ выбора | $2^n$ |
| Скобки, монеты, подмножества | Шаг — выбор из двух: $a$ или $b$, орел или решка, взять или нет | Строка $n$ |
Часто задаваемые вопросы
Для небольших $n$ треугольник быстрее: числа получаются сложением, без факториалов и дробей. И он сразу показывает всю строку, например все коэффициенты $(a+b)^n$. Для больших $n$, вроде $C_{45}^6$, удобнее формула.
Номер строки — это число шагов от вершины, а в вершине шагов ноль. Тогда номер строки совпадает с $n$ в записи $C_n^k$ и со степенью в $(a+b)^n$. Проверить себя просто: второе число строки равно ее номеру.
Напрямую нет. Треугольник Паскаля считает пути, где на каждом шаге ровно два выбора: влево или вправо, $a$ или $b$, орел или решка. Вопрос «выпала шестерка или нет» снова дает выбор из двух, но исходы «шестерка» и «не шестерка» не равновозможны, и считать вероятность одной строкой уже нельзя.
Используйте симметрию: $C_n^k=C_n^{n-k}$. Например, $C_{10}^8=C_{10}^2=\dfrac{10 \cdot 9}{2 \cdot 1}=45$: два множителя вместо восьми. Считать с ближнего края быстрее и надежнее.
5
5
1
5