Комбинаторика. Много.

cool.phenon · 12/05/12 604 Оттуда

Здравствуйте, уважаемые участники форума. Прошу проверить на корректность ответы и размышления.

1)В книжный магазин поступили 5 видов книг по одинаковой цене (каждой из книг достаточно много, $>17$ ). Имеется денежная сумма, равная $17$ ценам одной книги. Сколько способов совершить покупку?

Поскольку каждую покупку мы можем совершить покупкой только одного вида книг, то имеем дело с сочетаниями с повторениями. Поэтому ответ $C_{17+5-1}^{5-1}$

2)Сколькими способами можно расставить на шахматной доске $8$ ладей так, чтобы они никакие $2$ не били друг друга?

Скорее всего имелось в виду, что ладьи одного цвета могут бить друг друга, иначе смысл теряется. В таком случае первую ладью ставим $64=8\cdot 8$ вариантами. Вторую можно поставить везде, где не бьёт первая (то есть, можно ставить на любой клетке, столбец и строка которой не совпадают с предыдущими), то есть, $7\cdot 7$ вариантов и т.д . Ответ $64 \cdot 49 \cdot 36 \cdot 25 \cdot 16 \cdot 9 \cdot 4$

3)Сколько всего вариантов того, что, перемешивая буквы разрезной азбуки "М" "А" "Т" "Е" "М" "А" "Т" "И" "К" "А", получится слово "математика"?

В слове 'математика' можно перемешивать все буквы, которые повторяются. Ответ $2!\cdot 3! \cdot 2!$

4)Cколько всего различных слов можно получить, перемешивая буквы разрезной азбуки "М" "А" "Т" "Е" "М" "А" "Т" "И" "К" "А"?

Каждое перемешивание соответствует слову, в котором $2-M$ , $3 -A$ , $2-T$ и так далее. То есть, имеем дело с сочетаниями с повторениями. Ответ $\frac{10!}{2!3!2!}$

5)
Сколькими способами $8$ человек можно рассадить за круглым столом, чтобы 2 фиксированных лица сидели напротив?

Фиксируем одного человека по кругу. Затем садим второго напротив. Остальных можно переставлять произвольно, поэтому ответ $6!$ .

6)
Сколькими способами можно рассадить класс из $10$ дев. и $10$ мал. по $10$ партам, чтобы за каждой партой сидели мал. и дев., а за каждым мал. сидела дев. и за каждой дев. сидел мал.?

В таком случае рассадка проводится в шахматном порядке. Но таких рассадки $2$ . В каждой из них выделяются $10$ мест на мал. и $10$ мест на дев. Поэтому ответ $\left(10!\right)^{2}\cdot 2$
7)Сколькими способами можно рассадить $20$ людей по $5$ вагонам, чтобы первые $3$ вагона заняли соответственно $2,5,3$ человека? (Людей считать разными)

Сначала нужно выбрать $2$ человека в $1$ вагон, $3$ человека в $3$ вагон, $5$ человек во $2$ вагон. Это можно сделать $C_{20}^{2}\cdot C_{18}^{5}\cdot C_{13}^{3}$ способами. Оставшиеся $10$ людей садятся в один из последних вагонов, поэтому вариантов $2^{10}$ . Ответ $C_{20}^{2}\cdot C_{18}^{5}\cdot C_{13}^{3}\cdot 2^{10}$

А если людей считать одинаковыми? Тогда рассаживание в первые $3$ вагона однозначно, в последние $2$ можно рассадить $C_{10+2-1}^{2-1}$ способами. Это и будет ответ.

8)Сколькими способами можно рассадить $10$ коз и $15$ волков по $3$ вагонам, чтобы ни одна коза не попала в один вагон с волком?

Можно либо рассадить всех волков в $1$ вагон ( $3$ способа), а оставшихся коз по $2$ вагонам и наоборот. Поэтому общее число будет равно $3\cdot C_{10+2-1}^{2-1}+3\cdot C_{15+2-1}^{2-1}$

Но это решение нерационально, так как можно увеличить число коз, волков и вагонов так, что ручной подсчёт займёт много времени. Как эту задачу можно решить рациональнее?

venco · 04/05/09 4587

1) Да
2) А если сначала поставить последнюю ладью, а в конце первую, то расстановка будет та же?
3) Да
4) Да
5) А что, первый человек может сесть без вариантов?
6) Да
7) Да
8) Да
Что бы рациональнее было, надо раскрыть $C^{2-1}_{*}$ . Это и к другим ответам относится.

cool.phenon · 12/05/12 604 Оттуда

2)Ладьи у нас можно считать одинаковыми (ведь цвет не влияет на то, бьет или нет). Поэтому я считаю, что не имеет значения, какую ладью считать первой или последней, они все равно одинаковы.
5) Формально там еще есть 0 действие - отметить начало отсчета, но оно определяется однозначно с точностью до поворота. А уже затем на это место мы садим 1 человека.

Я оставлял именно в таком виде, чтобы было видно, что я пользовался именно формулой сочетаний с повторениями.
Но вопрос к последней задаче все-таки остается открытым.

-- 21.06.2013, 19:53 --

Я понял, что имелось в виду по поводу ладей. Что будут ли одинаковыми расстановками одна и другая, если расставить ладьи по тем же местам, но в другом порядке. Конечно же, это одинаковые расстановки. Но вот учитывалось ли это при подсчете..похоже, что нет.
Нужно еще разделить на количество таких возможных перестановок, то есть ответ будет $8!$

venco · 04/05/09 4587

2) Теперь правильно
5) Хм, по моему, в условии не сказано "с точностью до поворотов".

cool.phenon · 12/05/12 604 Оттуда

5) Дело в том, что на то круг и является кругом, чтобы циклические перестановки совпадали. Но все же я не уверен, правильно решил или нет.

Xaositect · 06/10/08 6422

venco в сообщении #739257 писал(а):

5) Хм, по моему, в условии не сказано "с точностью до поворотов".

Обычно в этих задачках когда пишут "круглый стол", имеют в виду именно неразличимость конфигураций, полученных друг из друга поворотом.

Shadow · 26/08/11 2102

cool.phenon в сообщении #739219 писал(а):

2)Сколькими способами можно расставить на шахматной доске $8$ ладей так, чтобы они никакие $2$ не били друг друга?

Скорее всего имелось в виду, что ладьи одного цвета могут бить друг друга, иначе смысл теряется. В таком случае первую ладью ставим $64=8\cdot 8$ вариантами. Вторую можно поставить везде, где не бьёт первая (то есть, можно ставить на любой клетке, столбец и строка которой не совпадают с предыдущими), то есть, $7\cdot 7$ вариантов и т.д . Ответ $64 \cdot 49 \cdot 36 \cdot 25 \cdot 16 \cdot 9 \cdot 4$

Только если считать ладьи неразличимыми, а одинаковые позиции, полученные разными путями - различимыми. Второе для меня совсем не очевидно. Я решал бы как "сколько существуют разных позиций..."

cool.phenon · 12/05/12 604 Оттуда

Ну, что касается этого вопроса, то тут все ясно: в условии не сказано, считать ли ладей одинаковыми или нет, но если считать разными, то задача существенно усложняется, а так как в таком случае считаем ладьи одинаковыми, то естественно считать именно те позиции в которых ладьи стоят одинаково, но расстановки получены иначе, различными.

--mS-- · 23/11/06 4171

Shadow в сообщении #739369 писал(а):

Только если считать ладьи неразличимыми, а одинаковые позиции, полученные разными путями - различимыми. Второе для меня совсем не очевидно. Я решал бы как "сколько существуют разных позиций..."

Как раз в этом решении ладьи и различимы. Демонстрирую. Есть $64$ варианта для первой ладьи. Например, она может стать на клетку $A1$ , и тогда вторая, например, из своих $49$ вариантов может выбрать клетку $B2$ . А может встать на клетку $B2$ , и тогда вторая из своих $49$ вариантов может выбрать, например, клетку $A1$ . Варианты $A1, B2, \ldots$ и $B2, A1, \ldots$ посчитаны как разные. Это и называется "ладьи различимы". Что совершенно то же самое, что "одинаковые позиции, полученные разными путями - различимыми". Почему Вы различили эти две вещи - загадка.

А вот ситуация, когда ладьи неразличимы, более естественна. На $8!$ перестановок следует поделить в этом случае.

Shadow · 26/08/11 2102

--mS-- в сообщении #739417 писал(а):

Варианты $A1, B2, \ldots$ и $B2, A1, \ldots$ посчитаны как разные. Это и называется "ладьи различимы

У меня была интерпретация ладьи неразличимы, а вот ходы различимы (что то же самое, что ладьи различимы - Вы правы) $A1,B2 \text { и } B1,A1$ разлчны.

--mS-- в сообщении #739417 писал(а):

А вот ситуация, когда ладьи неразличимы, более естественна

Именно это я имел ввиду. Сколько вариантов для ладьи на вертикали $A$ ...

cool.phenon · 12/05/12 604 Оттуда

Задачи еще буду добавлять, проверьте, пожалуйста, их на правильность.

9) Очередь в столовую состоит из $30$ человек. В столовой в наличии только $28$ пирожков. Сколько способов расставить очередь так, чтобы $2$ определённым людям не досталось пирожков?

2 определённых людей ставим в самый конец, это можно сделать $2$ способами. Остальные $28$ людей можно как угодно переставлять. Поэтому ответ $2\cdot 28!$