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

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

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

Кружок 7 класса (рук. Е. А. Асташов)

Кружок 7 класса, группа А (ст. преп. Д. А. Удимов)

Группа А. Старший преподаватель Д. А. Удимов

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

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

1.

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

а): 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ⁿ;
г): C_n⁰C_m^k + C_n¹C_m^k−1 + C_n²C_m^k−2 + ... + C_n^k−1C_m¹ + C_n^kC_m⁰ = C_n+m^k

2.

а): Сколько способов выбрать из 16 инопланетян капитана тарелки, помощника капитана и повара?
б): Сколько способов распределить эти роли между тремя инопланетянами?
в): Сколько способов из 16 инопланетян выбрать трёх?
г): Есть n инопланетян, сколькими способами можно поставить k из них в очередь на медосмотр перед полётом?
д): Сколько способов из n инопланетян выбрать k инопланетян?

3.

а): На плоскости отмечено 10 точек, и никакие три из них не лежат на одной прямой. Сколько есть треугольников с вершинами в этих точках?
б): На каждой из двух параллельных прямых отмечено по 5 точек. Сколько существует треугольников с вершинами в этих точках?

4.

Фигура «хромой король» ходит на одну клетку и только вправо или вверх. Сколькими различными путями можно провести «хромого короля» из левой нижней клетки доски 6×10 в правую верхнюю?

5.

Сколько способов:

а): выбрать из 12 инопланетян 6 для разведки Земли;
б): разделить 12 инопланетян на две команды по 6 персон для игры в космобол?

6.

Двенадцать инопланетян решили навестить знакомых с Земли. У них есть 4 различные тарелки, в каждую из которых должны сесть ровно трое. Сколько у инопланетян

а): вариантов разместиться по тарелкам;
б): вариантов составить четыре экипажа?

7.

Сколько способов выбрать на доске n×n:

а): два столбца;
б): не более двух столбцов;
в): две строки и два столбца?
г): Сколько есть способов закрасить несколько клеток на доске так, чтобы закрашенная часть образовывала прямоугольник?

8.

а): 7 ящиков занумерованы числами от 1 до 7. Сколько есть способов разложить по этим ящикам 20 одинаковых шаров так, чтобы ни один ящик не оказался пустым?
б): А если некоторые ящики могут оказаться пустыми?

9.

а): «Хромой король» из задачи 4 совсем устал. Теперь он ещё и не может два раза подряд ходить вверх. Сколько теперь у него есть путей из левой нижней клетки в правую верхнюю клетку доски 6×10?
б): На полке стоят 14 книг. Сколько есть способов выбрать из них 5 книг так, чтобы никакие две из них не стояли рядом?

10.

12 инопланетян встретили 12 землян. Сколько существует способов составить из них компанию, в которой было бы поровну землян и инопланетян?