Короткий ответ: число разбиений 10 различных предметов по 3 неупорядоченным (непронумерованным) коробкам, допускающим пустые, равно
$$\sum _{j=1}^{3}S(10,j)=S(10,1)+S(10,2)+S(10,3)=1+511+9330=9842,$$ где $S(n,k)$ — числа Стирлинга второго рода.
Подходы и пояснения (счёт и где появляются биномиальные коэффициенты vs числа Стирлинга):
1) Прямо через числа Стирлинга (естественно для неупорядоченных блоков):
- $S(n,k)$ даёт число разбиений $n$ различных элементов на $k$ непустых неупорядоченных подмножеств.
- Здесь пустые коробки допускаются, значит число разбиений на не более чем 3 непустых блока:
${\sum }_{j=1}^{3}S(10,j)$.
- Значения: $S(10,1)=1$, $S(10,2)=2^9-1=511$, $S(10,3)=\frac{3^{10}-3\cdot 2^{10}+3}{6}=9330$.
2) Через размещения по пронумерованным коробкам и действие симметрий (Burnside / Пойя):
- Всего поместить в пронумерованные коробки: $3^{10}$.
- Группа перестановок ярлыков $S_3$ действует на таких размещениях; число орбит (неупорядоченных разбиений) по формуле Бернсайда:
$$\frac{1}{6}(3^{10}+3\cdot 1+2\cdot 0)=9842,$$ поскольку у тождественной перестановки фикси\-руются $3^{10}$ раскраски, у трёх транспозиций — по $1$ (все элементы в неподвижном ярлыке), у двух 3-циклов — $0$.
3) Через включения-исключения и биномиальные коэффициенты:
- Для счёта сюръекций на $k$ пронумерованных коробок используют включ.-искл.:
$$\text{число сюръекций}=\sum _{i=0}^k(-1{)}^i(\genfrac{}{}{0ex}{}{k}{i})(k-i{)}^n.$$ - Деление на $k!$ даёт $S(n,k)$:
$$S(n,k)=\frac{1}{k!}\sum _{i=0}^k(-1{)}^i(\genfrac{}{}{0ex}{}{k}{i})(k-i{)}^n.$$ Здесь явно появляются биномиальные коэффициенты $\left(\genfrac{}{}{0ex}{}{k}{i}\right)$: выбор, какие $i$ ярлыков считаем «пустыми» в включ.-искл.
4) Через мультиномиальные / явный выбор подмножеств (где биномиальные коэффициенты естественны):
- Для пронумерованных коробок и фиксированной структуры размеров $(n_1,n_2,n_3)$ число распределений равно мультиномиальному коэффициенту
$\frac{10!}{n_1!n_2!n_3!}$, а выбор конкретных элементов для первой коробки — $\left(\genfrac{}{}{0ex}{}{10}{n_1}\right)$ и т.д.
- Переход к неупорядоченным коробкам требует деления на факториалы равных по структуре блоков и учёта симметрий — это и приводит к необходимости чисел Стирлинга или Бернсайда (тк. простое деление $3^{10}/3!$ не даёт корректного результата из-за случаев с пустыми коробками и совпадающими блоками).
Вывод-правило: используйте числа Стирлинга, когда коробки неупорядочены и вы считаете разбиения на непустые блоки (или суммы для «не более k»). Биномиальные и мультиномиальные коэффициенты естественно возникают при явном выборе элементов в конкретные (пронумерованные) коробки и в формулах включения–исключения для учёта пустых ярлыков.