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

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

Листок 21. Комбинаторика. Разные задачи

1.

В урне m белых и n черных шаров, причем все они каким-то образом занумерованы от 1 до m+n. Сколькими способами из урны можно извлечь r+s шаров так, чтобы r из них были белыми, а s — черными (r ≤ m, s ≤ n)?

2.

Сколькими способами из колоды карт (36 карт) можно выбрать 4 карты так, чтобы среди них было ровно 2 дамы, причем одна из них — дама пик?

3.

Сколькими способами можно разместить 7 одинаковых шаров в 4-х занумерованных ящиках:

а)

возможно, оставляя некоторые ящики пустыми;

б)

так, чтобы не было пустых ящиков?

4.

Человек начинает свое движение от фонаря посреди улицы, делая шаги равной длины вправо или влево. Предположим, что он сделал N шагов.

а)

сколькими способами он может сделать n этих шагов вправо, а остальные N−n шагов — влево?

б)

сколькими способами человек может оказаться в m шагах от фонаря справа, делая N шагов (см. рисунок)?

5.

Подземелье состоит из пещер, которые соединены туннелями так, как показано на рисунке. В скобках (n, m) указаны числа: n — номер этажа (этажи нумеруются сверху вниз), m — номер пещеры. Сколькими способами H(n, m)можно попасть из пещеры (0,0) в пещеру (n, m), если можно только спускаться: suproblem: а) при n = 3 и 0 ≤ m ≤ n;

б)

в общем случае?

6.

Используя задачу 5, докажите равенство .

7.

Имеется n разных коробок и m одинаковых шаров (m < n), причем в коробку умещается только один шар. Сколькими способами можно разложить шары в коробки так, чтобы никакие два шара не лежали в соседних коробках:

а)

если коробки стоят в ряд;

б)

если коробки стоят по кругу?