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

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

1.

Пользуясь только определением, докажите, что:

а)

C_n⁰ = C_nⁿ = 1;

б)

C_n¹ = C_n^n-1 = n;

в)

C_n^n−k = C_n^k;

г)

C_n^k + C_n^k+1 = C_n+1^k+1;

д)

C_n⁰ + C_n¹ + C_n² + ... + C_nⁿ⁻¹ + C_nⁿ = 2ⁿ.

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 марсиан. Сколько существует способов составить компанию, в которой было бы одинаковое число землян и марсиан?