Предположим, в одной камере сидят 5 негров, 4 китайца и 4 белых. Каждое утро надзиратель выстраивает их в ряд, причем его обостренное чувство прекрасного не позволяет ему ставить двух негров подряд, и каждый раз он выстраивает другую комбинацию заключенных (заключенных одной расы друг от друга он не отличает). Когда надзирателю придется обновить штат заключенных?

Единственный способ решения, который пришел в голову - полный перебор комбинаций. Но это как то некрасиво.

(0) >>> не позволяет ему ставить двух негров подряд

Как понять сею фразу?

Как Два нигера не могут стоять рядом друг с другом?
Как один и тот же нигер не может повторяться с одим и тем же заключенным?

Задача не полностью сформулирована... Дкмается вам не мешало бы посещать все лекции :)

раскраска графов

(1) Вот так. Комбинация Н Б К Н Б К... легитимна, а Н Н Б К Б К... - нет.

Ок. Специально для любителей сферических коней в ваккуме. Есть 5 черных, 4 белых и 4 желтых шара. Шары одного цвета не отличаются друг от друга. Шары черного цвета не могут стоять подряд. Сколькими способами можно расставить все шары в ряд.


P.S. Несомненно не помешало бы. Однако, лекции по комбинаторике я посещал дай бог лет 17 назад. И основные формулы пока еще помню.

(5 + 4 + 4)!/(5!4!4!)

(4)+ ошибся

(4) Э-э-э, почему?

(6)Формула (4) не учитывает ограничения, что негров нельзя ставить подряд. Правильный ответ должен быть меньше.

а китайцев и белых мона рядом? тогда просто 5 негров и 8 белых

(7) Это понятно, задал вопрос до появления поста (5)
(8) Конечно можно, но это не верно. Тк будут комбинации внутри 8 белокитайцев.

(8) (9) Насколько я понимаю, комбинации, где белый и китаец поменялись местами - разные, так как сказано, что надзиратель не различает людей ОДНОЙ РАСЫ.
А из фразы "не ставить двух негров рядом" не следует, что он не различает белых и китайцев.

То есть полная расстановка из 13 делённая на перестановку 5 и две перестановки 4 - это число всевозможных комбинаций - из них нужно вычесть число комбинаций, где хотя бы два негра находятся рядом.

(10) Логично.

(10) Засада тогда как раз в том, как вычислить количество комбинаций где негры рядом.

Еще вариант - посчитать количество комбинаций белых и китайцев и умножить его на количество разбиений 8 элементов на 6 кучек (возможно пустые 1 и 6).

(12) Кстати мысль. Предположим у нас есть шеренга из 8 белокитайцев. В таком случае начнем впихивать в нее негров (5 рыл). У нас будет 9 мест и 5 негров куда их можно засунуть. Фактически это количество сочетаний из 9 по 5.

Итого имеем решение:

4 белых и 4 китайцев можно скомбинировать 8!/(4!*4!) способами.
8!/(4!*4!)
Распихать негров можно
9!/(4!*5!)
Итого: 8!*9!/(4!*4!*4!*5!)


Вроде логично нет?

(3) Бесконечно. Вернее заключенные будут меняться всегда, пока не умрут или не выйдут на свободу. :)

(13)Логично

Может так получится:
расставим допустимым образов негров на N мест.
Пусть X1 - номер "первого" негра, X2 - расстояние между вторым и первым, Xk - расстояние между последним и предпоследним.
Тогда допустимым будет любое решение:
X1>=1, X2>=2,...,Xk>=2
СУММА(Xi)<=N.
Сделав замену: Y1=X1-1, Y2=X2-2,...,Yk=Xk-2 получим:
Yi>=0
СУММА(Yi)<=N-2k+1.
Число решений такого неравенства (в целых неотрицательных), если не ошибаюсь = (N-2k+2)*(N-2k+1)*...*(N-k+2)/k! (это какой-то известный комбинаторный факт).
Чсло допустимых расстановок негров = число выше*k! (т.к. негры разные).
Осталось только умножить на число расстановок остальных N-k людей на оставшиеся N-k мест, т.е. на (N-k)!.