МАЛЫЙ МЕХМАТ МГУ

Кружок 8 класса

Руководитель Евгений Александрович Асташов
2014/2015 учебный год

Занятие 9. История про футболки и сочетания

Определение. Число способов выбрать из n различных предметов k различных предметов, если порядок, в котором они выбираются, неважен, называется числом сочетаний из n по k и обозначается Cnk (читается «цэ из эн по ка»).

Теорема . Cnk = n!/k!(n − k)!

Прочитайте историю, а затем с её помощью попробуйте доказать различные свойства чисел сочетаний. В задачах 1–4 дайте по два доказательства: a) с помощью определения (тут вам и поможет история); б) с помощью теоремы.

Николай собирался в отпуск на юг и выбирал, какие футболки с собой взять. Он ехал на неделю и хотел взять по одной футболке на каждый день, а всего у него было 10 футболок. Сначала Николай долго выбирал, какие футболки взять, но потом решил, что будет проще определиться, какие футболки НЕ брать.

1.
Cn0 = Cnn = 1.
2.
Cn1 = Cnn − 1 = n
3.
(симметричность). Cnk = Cnn − k
4.
(основное биномиальное тождество). Cnk + Cnk + 1 = Cn + 1k + 1.
5.
Пользуясь предыдущими задачами, докажите, что в треугольнике Паскаля в n – й строке на k – м слева месте стоит число Cnk. (Строка из одной единицы имеет номер 0. В каждой строке начальная единица стоит на нулевом месте.)

Николай решил доверить выбор футболок случаю. Он положил их в стиральную машину и решил так: когда они постираются, он будет их по очереди вытаскивать (не глядя). Первые 7 вытащенных футболок он возьмёт с собой, а остальные оставит.

6.
а)
Сколько способов было у Николая вытащить 7 футболок из стиральной машины (в которой их всего 10) и сложить их в стопку (в том порядке, в котором вытащил)?
б)
Сколько способов сложить в стопку выбранные 7 футболок? А невыбранные три футболки?
в)
Сколько способов взять 7 футболок из 10 в отпуск было у Николая?
г)
Докажите теорему.

Пока футболки стирались, Николай начал сомневаться, стоит ли ему на каждый день брать по футболке. Может, проще взять с собой все футболки? А может, часть из них лучше оставить и вместо этого взять рубашки? В общем, сначала надо определиться, сколько футболок брать, а потом решить, какие именно. Или лучше ещё раз перебрать все футболки и про каждую решить, брать её или нет?

7.
С помощью определения докажите, что Cn0 + Cn1 + Cn2 + Cn3 + … + Cnn− 1 + Cnn = 2 n.
8.
(вместо эпилога). В конце концов Николай определился с футболками, собрал чемодан и уехал в отпуск. В самолёте он заметил, что в семизначном номере его авиабилета цифры идут по возрастанию. Николай задумался: а сколько ещё билетов с таким свойством? Ответьте и вы на этот вопрос.