bulgakov

15. Правило Паскаля и треугольник Паскаля

Число способов выбрать rr элементов из nn равно сумме двух чисел: способов, когда особый элемент не взят, и способов, когда он взят: (nr)=(n−1r)+(n−1r−1)\dbinom nr=\dbinom{n-1}{r}+\dbinom{n-1}{r-1}. Из этого правила вырастает треугольник Паскаля — в нём каждое число равно сумме двух чисел над ним.

Что пригодится из прошлого: сочетания — формула с факториалами; симметрия и сумма 2n2^n; правило суммы — выбор разбивается на непересекающиеся случаи. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Начнём с примера

Выберем двух человек из четырёх: a,b,c,da,b,c,d. Всего (42)=6\dbinom42=6 пар. Сделаем одного человека, например aa, «особым» и разобьём все пары на две группы: в одной есть aa, в другой нет.

  • есть a: {a, b}, {a, c}, {a, d} — пар: 3
  • нет a: {b, c}, {b, d}, {c, d} — пар: 3

В первой группе aa уже взят; нужно выбрать ещё одного человека из трёх остальных: (31)=3\dbinom31=3. Во второй группе aa не взят; нужно выбрать двоих из трёх остальных: (32)=3\dbinom32=3. Группы не пересекаются, поэтому

(42)=(32)+(31)=3+3=6.\binom42=\binom32+\binom31=3+3=6.

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

Следствие 3. Для 1≤r≤n−11\le r\le n-1

(nr)=(n−1r)+(n−1r−1).\boxed{\binom nr=\binom{n-1}{r}+\binom{n-1}{r-1}}.

Докажем двумя способами: сначала рассуждением, потом вычислением.

Доказательство 1: по классам

Все сочетания без повторений из элементов A={a1,a2,…,an}A=\{a_1,a_2,\dots,a_n\} по rr разобьём на два класса.

  1. Сочетания, содержащие элемент a1a_1. Он уже выбран, остаётся выбрать r−1r-1 элементов из оставшихся n−1n-1. Таких сочетаний (n−1r−1)\dbinom{n-1}{r-1}.
  2. Сочетания, не содержащие элемент a1a_1. Все rr элементов выбираются из оставшихся n−1n-1. Таких сочетаний (n−1r)\dbinom{n-1}{r}.

Каждое сочетание попадает ровно в один класс: либо a1a_1 в нём есть, либо нет. По правилу суммы число всех сочетаний равно сумме двух чисел. □\square

Доказательство 2: вычислением

Запишем обе дроби с факториалами:

(n−1r)+(n−1r−1)=(n−1)!r! (n−1−r)!+(n−1)!(r−1)! (n−r)!.\binom{n-1}{r}+\binom{n-1}{r-1} =\frac{(n-1)!}{r!\,(n-1-r)!}+\frac{(n-1)!}{(r-1)!\,(n-r)!}.

Приведём к общему знаменателю r! (n−r)!r!\,(n-r)!. У первой дроби в знаменателе не хватает множителя (n−r)(n-r): ведь (n−r)!=(n−r)⋅(n−r−1)!(n-r)!=(n-r)\cdot(n-r-1)!. У второй — множителя rr: ведь r!=r⋅(r−1)!r!=r\cdot(r-1)!. Умножим числитель и знаменатель каждой дроби на недостающий множитель:

=(n−1)! (n−r)r! (n−r)!+(n−1)! rr! (n−r)!=(n−1)! ((n−r)+r)r! (n−r)!=(n−1)! nr! (n−r)!=n!r! (n−r)!=(nr).□\begin{aligned} &=\frac{(n-1)!\,(n-r)}{r!\,(n-r)!}+\frac{(n-1)!\,r}{r!\,(n-r)!}\\ &=\frac{(n-1)!\,\bigl((n-r)+r\bigr)}{r!\,(n-r)!}\\ &=\frac{(n-1)!\,n}{r!\,(n-r)!}=\frac{n!}{r!\,(n-r)!}=\binom nr.\qquad\square \end{aligned}

Первое доказательство объясняет, почему правило верно; второе — проверяет формулу. Оба нужны: они согласуют две картины одного явления.

Треугольник Паскаля

Правило подсказывает способ строить числа (nr)\dbinom nr без факториалов. Выпишем строки: в строке номер nn стоят числа (n0),(n1),…,(nn)\dbinom n0,\dbinom n1,\dots,\dbinom nn.

  • Края каждой строки — единицы: (n0)=(nn)=1\dbinom n0=\dbinom nn=1.
  • Каждое число внутри равно сумме двух чисел, стоящих над ним слева и справа: так сказано в правиле Паскаля.
               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

Пример. В строке 55 число 10=(52)10=\dbinom52 получено из двух чисел строки 44, стоящих над ним: 4=(41)4=\dbinom41 и 6=(42)6=\dbinom42. Вот этот кусочек:

строка 4:           4     6
                     ╲   ╱
строка 5:             10

Как пользоваться треугольником.

  • Строки и места нумеруются с нуля. Число (nr)\dbinom nr — это строка nn, место rr. Например, (62)\dbinom62: строка 66 — это 1  6  15  20  15  6  11\;6\;15\;20\;15\;6\;1, место 22 — число 1515.
  • Строки симметричны слева направо: это свойство (nr)=(nn−r)\dbinom nr=\dbinom n{n-r}.
  • Сумма чисел строки nn равна 2n2^n: строки дают суммы 1,2,4,8,16,…1,2,4,8,16,\dots — это следствие ∑k=0n(nk)=2n\sum_{k=0}^n\dbinom nk=2^n.
  • Вторая диагональ — числа 1,2,3,4,…1,2,3,4,\dots: это (n1)=n\dbinom n1=n.

Частые ошибки

  • Нумерация с единицы. Самая верхняя строка — «11» — имеет номер 00; место крайнего слева числа тоже 00.
  • Складывать не те числа. Каждое число равно сумме двух верхних соседей (слева и справа сверху), а не соседей в той же строке.
  • Забыть о краях. Крайние числа всегда 11 — над ними только один сосед (другой считается нулём).
  • Применять правило к краям. При r=0r=0 и r=nr=n правило Паскаля не нужно: там просто 11.

Проверь себя

1. Проверьте правило Паскаля для n=6n=6, r=3r=3.

Решение

(63)=20\dbinom63=20, а (53)+(52)=10+10=20\dbinom53+\dbinom52=10+10=20. Числа совпали.

2. Не используя формулу с факториалами, по строке 77 найдите (83)\dbinom83.

Решение

Строка 77: 1721353521711 7 21 35 35 21 7 1. По правилу Паскаля (83)=(73)+(72)=35+21=56\dbinom83=\dbinom73+\dbinom72=35+21=56.

3. Продолжите треугольник до строки 1010.

Решение

Строка 88: 182856705628811 8 28 56 70 56 28 8 1. Строка 99: 1936841261268436911 9 36 84 126 126 84 36 9 1. Строка 1010: 11045120210252210120451011 10 45 120 210 252 210 120 45 10 1.

4. Объясните, почему сумма чисел каждой следующей строки в два раза больше суммы предыдущей.

Решение

Каждое число строки n−1n-1 входит в слагаемые ровно двух чисел строки nn: стоящих под ним слева и справа (у крайних единиц второй «сосед» — нуль). Пример: от строки 33 (1,3,3,11,3,3,1, сумма 88) к строке 44 (1,4,6,4,11,4,6,4,1, сумма 1616): первая 11 входит в первую 11 и в первую 44; первая 33 — в первую 44 и в 66; вторая 33 — в 66 и во вторую 44; последняя 11 — во вторую 44 и в последнюю 11. Значит, при переходе к следующей строке сумма удваивается. В строке 00 сумма 11, поэтому в строке nn она равна 2n2^n.

Итог

  • (nr)=(n−1r)+(n−1r−1)\dbinom nr=\dbinom{n-1}{r}+\dbinom{n-1}{r-1}: элемент a1a_1 либо в выборке (остальные r−1r-1 из n−1n-1), либо нет (все rr из n−1n-1).
  • Это правило строит треугольник Паскаля: каждое число — сумма двух чисел над ним.
  • Строка nn, место rr (с нуля) — число (nr)\dbinom nr; строка симметрична, её сумма равна 2n2^n.
ПрактикаЗагружаем тест…