Комбинаторика

[VAL]

tess в сообщении #563296 писал(а):

Вариантов-то немного, зачем Стирлинг.

Стирлинг привлекался по второму пункту.

Цитата:

Преступники и магазины неразличимы: 227, 236, 245, 335 и 344 - 5 вариантов.
Преступники неразличимы, магазины различны: 3[*]3 (две цифры одинаковые)+2[*]6 (три цифры различны) = 21 вариант (без ограничений число вариантов было бы равно числу сочетаний из 11 по 3 с повторениями, то есть 78).
Преступники индивидуальны, магазины неразличимы: для случая 227 число вариантов равно числу сочетаний из 11 по 2 умножить на число сочетаний из 9 по 2, то есть 1980, и так далее: 1980+4620+6930+9240+11550 = 34320 вариантов.
Наконец, преступники индивидуальны, магазина различны:
1980[*]3+4620[*]6+6930[*]6+9240[*]3+11550[*]3 = 137610 вариантов (без ограничений было бы 3 в 11 степени, то есть 177147 вариантов).

Вариантов еще меньше.
Магазины (в отличие от камер) различны по условию.
Преступники различны по здравому смыслу (это ж не шары одного цвета).
Ограничения имеются.
Поэтому правильный ответ 137610.

[tess]

Уважаемый VAL! Согласен, что последнее слово за Вами. Но начальник тюрьмы, который должен рассадить 11 неразличимых для него заключённых в 4 различные камеры, возьмет бумажку и карандаш и, как любитель математики, посчитает: всего имеется 364 варианта (число сочетаний из 11 по 4 с повторениями), вычтет случаи 0-0-0-11 (4 варианта), 0-0-1-10 (12 вариантов) и 0-1-1-9 (12 вариантов), и получит ответ 336.
При всем его уважении к Джеймсу Стирлингу он оставит его в покое.
Другое дело, как начальник выберет один вариант.

[VAL]

tess в сообщении #563359 писал(а):

Уважаемый VAL! Согласен, что последнее слово за Вами.

И не сомневайтесь!

Цитата:

Но начальник тюрьмы, который должен рассадить 11 неразличимых для него заключённых

Не согласен. Но допустим.

Цитата:

в 4 различные камеры, возьмет бумажку и карандаш и, как любитель математики, посчитает: всего имеется 364 варианта (число сочетаний из 11 по 4 с повторениями)

Для неграмотного начальника тюрьмы простительно. Но от Вас я ожидал увидеть число сочетаний из 4 по 11 с повторениями.

[ewert]

$N_{n+1}=3\,N_n+3n\cdot2^{n-1}-6n^2,\qquad N_n=C\cdot3^n-3(n+2)2^{n-1}+3(n^2+n+1);$

$N_{6}=C_6^2\cdot C_4^2=90,\qquad C=1,\qquad N_n=3^n-3(n+2)2^{n-1}+3(n^2+n+1);$

$N_{11}=177\,147-39\,936+399=137610.$

[MayorBarbariska]

Цитата:

Возможные количественные составы групп определены выше. Выберем участников персонально:
1. $\frac12C_{11}^2C_9^2$
2. $C_{11}^2C_9^3$
3. $C_{11}^2C_9^4$
4. $\frac12C_{11}^3C_8^3$
5. $\frac12C_{11}^3C_8^2$
Остается распределить группы по магазинам. Для этого достаточно умножить сумму полученных чисел на $3!$

VAL, могу я поинтересоваться откуда береться коэффицент $1/2$ в 1, 4 и5 случаях?

[VAL]

MayorBarbariska в сообщении #563438 писал(а):

Цитата:

Возможные количественные составы групп определены выше. Выберем участников персонально:
1. $\frac12C_{11}^2C_9^2$
2. $C_{11}^2C_9^3$
3. $C_{11}^2C_9^4$
4. $\frac12C_{11}^3C_8^3$
5. $\frac12C_{11}^3C_8^2$
Остается распределить группы по магазинам. Для этого достаточно умножить сумму полученных чисел на $3!$

VAL, могу я поинтересоваться откуда береться коэффицент $1/2$ в 1, 4 и5 случаях?

Эти случаи соответствуют разбиениям на три группы, в которых имеется по две равномощных группы.
Если не брать множитель $\frac12$, то каждое такое разбиение будет сосчитано дважды.
Например, мы сначала выбрали 1-го и 2-го воров, затем - 3-го и 4-го (остальные с 5-го по 11-го попали в группу из семи человек). В следующий раз мы сначала выбрали 3-го и 4-го, а затем 1-го и 2-го. Легко понять, что оба случая приводят к одному и тому же разбиению.

[MayorBarbariska]

VAL, премного благодарю, вроде больше вопросов по этой задаче нет. правда надо с числами Стирлинга разобраться, но это я сам как-нибудь.

[VAL]

ewert в сообщении #563383 писал(а):

$N_{n+1}=3\,N_n+3n\cdot2^{n-1}-6n^2,\qquad N_n=C\cdot3^n-3(n+2)2^{n-1}+3(n^2+n+1);$

$N_{6}=C_6^2\cdot C_4^2=90,\qquad C=1,\qquad N_n=3^n-3(n+2)2^{n-1}+3(n^2+n+1);$

$N_{11}=177\,147-39\,936+399=137610.$

Изящно!
А можно увидеть рассуждение, приводящее к данной рекуррентной формуле?

[ewert]

VAL в сообщении #563569 писал(а):

А можно увидеть рассуждение, приводящее к данной рекуррентной формуле?

Оно достаточно напрашивается. Пусть $N_n$ -- количество "хороших" размещений $n$ клиентов по трём магазинам (таких, что в каждом не менее двух). И $M_n$ -- количество "квазихороших", т.е. таких, что в ровно в одном ровно один клиент, а в двух других -- опять же не менее двух. Тогда, очевидно, $N_{n+1}=3\cdot N_n+1\cdot M_n$. А $M_n$ легко выписывается явно: $M_n=3\cdot n \cdot\big(2^{n-1}-2-2(n-1)\big)$.

С тюрьмами несколько сложнее, поскольку $4>3$. Тут, конечно, тоже можно покустарничать, но это уже не выйдет проще Стирлинга.

[VAL]

ewert в сообщении #563581 писал(а):

Оно достаточно напрашивается. Пусть $N_n$ -- количество "хороших" размещений $n$ клиентов по трём магазинам (таких, что в каждом не менее двух). И $M_n$ -- количество "квазихороших", т.е. таких, что в ровно в одном ровно один клиент, а в двух других -- опять же не менее двух. Тогда, очевидно, $N_{n+1}=3\cdot N_n+1\cdot M_n$. А $M_n$ легко выписывается явно: $M_n=3\cdot n \cdot\big(2^{n-1}-2-2(n-1)\big)$.

Спасибо! Я так и думал