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

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

Руководитель Евгений Александрович Асташов
2013/2014 учебный год
Кружок 7 класса (рук. Е. А. Асташов) Кружок 7 класса, группа А (ст. преп. Д. А. Удимов)

Занятие 4. Число сочетаний

Определение. Число способов выбрать из n различных предметов k предметов (порядок, в котором они выбираются, неважен) называется числом сочетаний из n по k и обозначается Cnk (читается «цэ из эн по ка»).
1.
Пользуясь только определением, докажите, что:
а)
Cn0 = Cnn = 1;
б)
Cn1 = Cnn-1 = n;
в)
Cnn−k = Cnk;
г)
Cnk + Cnk+1 = Cn+1k+1;
д)
Cn0 + Cn1 + Cn2 + ... + Cnn−1 + Cnn = 2n.
2.
а)
Сколько способов из 16 инопланетян выбрать капитана тарелки, помощника капитана и повара?
б)
Сколько способов распределить эти роли между тремя инопланетянами?
в)
Сколько способов из 16 инопланетян выбрать трёх?
г)
Есть n инопланетян, сколькими способами можно поставить k из них в очередь на медосмотр перед полётом?
д)
Сколько способов из n инопланетян выбрать k инопланетян?
3.
На плоскости отмечено 10 точек, и никакие три из них не лежат на одной прямой. Сколько есть треугольников с вершинами в этих точках?
4.
Инопланетяне играют в шахматы на доске n×n. Сколькими способами можно поставить на эту доску n ладей так, чтобы они не били друг друга?
5.
Двенадцать инопланетян решили навестить знакомых с Земли. У них есть 4 тарелки разных цветов, в каждую из которых входит ровно трое. Сколько у инопланетян способов разместиться в этих тарелках?
6.
Сколькими есть способов пройти из левой нижней клетки прямоугольника 5×9 в правую верхнюю, если можно ходить только вверх и вправо?}
7.
22 деревьева растут в круг. Сколько существует способов натянуть между ними две одинаковых верёвки так, чтоб они не пересекались? (Если концы верёвок привязаны к одному дереву, то они тоже пересекаются!)
8.
а)
7 ящиков занумерованы числами от 1 до 7. Сколько есть способов разложить по этим ящикам 20 одинаковых шаров так, чтобы ни один ящик не оказался пустым?
б)
А если некоторые ящики могут оказаться пустыми?
9.
Есть 10 землян и 10 марсиан. Сколько существует способов составить компанию, в которой было бы одинаковое число землян и марсиан?