Сколько существует способов распределить 6 пассажиров по трем различным отелям?
6 человек хотят посетить 3 разных отеля, так что каждый отель может выбрать от нуля до 6 человек, все состояния возможны. С точки зрения пассажира мы знаем, что есть$3^6=729$разные способы выполнить эту задачу. Но как решить эту проблему с точки зрения отелей?
Мы знаем, что отель 1 может получить 6, а отель 2,3 - нули, т.е. $(6,0,0)$ ИЛИ отель 1 5 и отель 2 1 и отель 3 ничего $(5,1,0)$ ИЛИ отель 1 3 отеля 2 2 и отель 3 1 $(3,2,1)$ИЛИ так далее. Но этот метод подсчета не дает правильного ответа. Заранее спасибо за помощь.
Ответы
В качестве альтернативы красивому ответу Пако Адахара вы можете провести анализ случая, используя $7$случаях следующим образом. . .
Пусть пассажиры идентифицируются по идентификационным номерам $1,2,3,4,5,6$.
Позволять $a,b,c$ обозначают количество пассажиров, которые попадают в отели $A,B,C$ соответственно.
Позволять $\text{sort}(a,b,c)$ обозначим тройку $(a,b,c)$ переставлены в порядке возрастания.
случай $(1)$:$\;\,\text{sort}(a,b,c)=(0,0,6)$.
На этот случай есть $$\binom{3}{1}=3$$ пути с
- Есть ${\large{\binom{3}{1}}}$ способы выбора отеля, который принимает все $6$ пассажиры.
случай $(2)$:$\;\,\text{sort}(a,b,c)=(0,1,5)$.
На этот случай есть $$\binom{3}{1}\binom{6}{5}\binom{2}{1}=3{\,\cdot\,}6{\,\cdot\,}2=36$$ пути с
- Есть ${\large{\binom{6}{5}}}$ способы выбрать $5$ пассажиры для этого отеля.$\\[4pt]$
- После того, как выбранные выше варианты будут сделаны, появятся ${\large{\binom{2}{1}}}$ способы выбрать отель, который заберет оставшиеся $1$ пассажир.
случай $(3)$:$\;\,\text{sort}(a,b,c)=(0,2,4)$.
На этот случай есть $$\binom{3}{1}\binom{6}{4}\binom{2}{1}=3{\,\cdot\,}15{\,\cdot\,}2=90$$ пути с
- Есть ${\large{\binom{3}{1}}}$ способы выбора отеля, который занимает $4$ пассажиры.$\\[4pt]$
- Есть ${\large{\binom{6}{4}}}$ способы выбрать $4$ пассажиры для этого отеля.$\\[4pt]$
- После того, как выбранные выше варианты будут сделаны, появятся ${\large{\binom{2}{1}}}$ способы выбрать отель, который заберет оставшиеся $2$ пассажиры.
случай $(4)$:$\;\,\text{sort}(a,b,c)=(0,3,3)$.
На этот случай есть $$\binom{3}{1}\binom{5}{2}\binom{2}{1}=3{\,\cdot\,}10{\,\cdot\,}2=60$$ пути с
- Есть ${\large{\binom{3}{1}}}$ способов выбрать отель, который принимает пассажира #$1$ плюс $2$ другие пассажиры.$\\[4pt]$
- Есть ${\large{\binom{5}{2}}}$ способы выбрать $2$ другие пассажиры этого отеля.$\\[4pt]$
- После того, как выбранные выше варианты будут сделаны, появятся ${\large{\binom{2}{1}}}$ способы выбора отеля, который занимает $3$ оставшиеся пассажиры.
случай $(5)$:$\;\,\text{sort}(a,b,c)=(1,1,4)$.
На этот случай есть $$\binom{3}{1}\binom{6}{4}\binom{2}{1}=3{\,\cdot\,}15{\,\cdot\,}2=90$$ пути с
- Есть ${\large{\binom{3}{1}}}$ способы выбора отеля, который занимает $4$ пассажиры.$\\[4pt]$
- Есть ${\large{\binom{6}{4}}}$ способы выбрать $4$ пассажиры для этого отеля.$\\[4pt]$
- После того, как выбранные выше варианты будут сделаны, появятся ${\large{\binom{2}{1}}}$ способы выбора отеля, в котором находится пассажир с наименьшим идентификационным номером $2$ оставшиеся пассажиры.
случай $(6)$:$\;\,\text{sort}(a,b,c)=(1,2,3)$.
На этот случай есть $$\binom{3}{1}\binom{6}{3}\binom{2}{1}\binom{3}{2}=3{\,\cdot\,}20{\,\cdot\,}2{\,\cdot\,}3=360$$ пути с
- Есть ${\large{\binom{3}{1}}}$ способы выбора отеля, который занимает $3$ пассажиры.$\\[4pt]$
- Есть ${\large{\binom{6}{3}}}$ способы выбрать $3$ пассажиры для этого отеля.$\\[4pt]$
- После того, как выбранные выше варианты будут сделаны, появятся ${\large{\binom{2}{1}}}$ способы выбрать другой отель, который занимает $2$ пассажиры.$\\[4pt]$
- Есть ${\large{\binom{3}{2}}}$ способы выбрать $2$ пассажиры для этого отеля.
случай $(7)$:$\;\,\text{sort}(a,b,c)=(2,2,2)$.
На этот случай есть $$\binom{3}{1}\binom{5}{1}\binom{2}{1}\binom{3}{1}=3{\,\cdot\,}5{\,\cdot\,}2{\,\cdot\,}3=90$$ пути с
- Есть ${\large{\binom{3}{1}}}$ способов выбрать отель, который принимает пассажира #$1$ плюс $1$ другой пассажир.$\\[4pt]$
- Есть ${\large{\binom{5}{1}}}$ способы выбрать $1$ другой пассажир для этого отеля.$\\[4pt]$
- После того, как выбранные выше варианты будут сделаны, появятся ${\large{\binom{2}{1}}}$ способы выбора отеля, в котором находится пассажир с наименьшим идентификационным номером из оставшихся $4$ пассажиры плюс $1$ другой пассажир.$\\[4pt]$
- Есть ${\large{\binom{3}{1}}}$ способы выбрать $1$ другой пассажир для этого отеля.
Суммируя подсчеты для $7$ случаев дает общее количество $$ 3+36+90+60+90+360+90=729 $$ как и ожидалось.
Пусть это будут три отеля A, B, C. Предположим, что отель A получит $m$ пассажиры с $0 \le m \le 6$. Есть$\binom{6}{m}$способы, чтобы это произошло. Тогда отель B должен получить$n$ из оставшихся $6 - m$пассажиры. Есть$\binom{6 - m}{n}$способы сделать это. По умолчанию отель C получает оставшиеся$6 - m - n$ пассажиры.
Таким образом, общее количество способов сделать это в отелях определяется выражением $$ \begin{align*} \sum_{m=0}^6\sum_{n=0}^{6-m}\binom{6}{m}\binom{6 - m}{n} &= \sum_{m=0}^6\binom{6}{m}\sum_{n=0}^{6-m}\binom{6 - m}{n} \\ &= \sum_{m=0}^6 \binom{6}{m}2^{6 - m} = (1 + 2)^6 = 729 \end{align*} $$ как указано ранее.
Количество способов выбора $a$ люди для первого отеля, $b$ для второй гостиницы, и $c$ для третьего отеля, с $a+b+c=6$, - полиномиальный коэффициент $$\binom{6}{a,b,c}= \frac{6!}{a! b! c!}$$ так что общее количество возможных аранжировок равно $$\sum_{a+b+c = 6} \binom{6}{a,b,c}$$ где суммирование ведется по всем целым тройкам $(a,b,c)$ с участием $a+b+c = 6$ и $a,b,c \ge 0$. Мы могли бы решить это, но есть ярлык.
По полиномиальной теореме $$(x+y+z)^6 = \sum_{a+b+c = 6} \binom{6}{a,b,c} x^a y^b z^c$$ где, как и раньше, суммирование ведется по всем целым тройкам $(a,b,c)$ с участием $a+b+c = 6$ и $a,b,c \ge 0$. Теперь позвольте$x=y=z=1$, и у нас есть $$3^6 = \sum_{a+b+c = 6} \binom{6}{a,b,c}$$ который воспроизводит предыдущий ответ $3^6 = 729$.