комбинаторика, разбить множество на 3 подмножества

[ewert]

gris писал(а):

$C_{10}^3\cdot 3^7+C_{10}^2 \cdot 2^8 +1$
Первое слагаемое представляет собой количество разбиений на 3 непустых подмножества, второе на два непустых, а третье на одно.

Да, но $C_{10}^3\cdot 3^7$ не совпадает ни с ответом VAL, ни с моим (а они дают один и тот же результат).
Вряд ли мы оба одновременно ошибаемся -- учитывая, что способы решения разные...

[gris]

Упс. Не успел удалить. Конечно я ошибся. Капитаны же не должны выделяться.

[ewert]

Да, конечно.

Ладно, предлагаю ответ:

$${3^{10}-3\over6}+1\;.$$

[VAL]

gris писал(а):

Вопрос не только в том, отличаются ли группы, а ещё и в том, различаются ли элементы множества. Одно дело, когда мы учеников распределяем по трём цветным командам, а другое, когда делаем три кучки из одинаковых белых шаров.

Кстати, в случае цветных команд для их непустоты я бы предложил сначала выбрать трёх капитанов $A_{10}^3= 720$-ю способами, а потом к нам набрать команды $3^7$ способами.

Давайте сразу договримся, какую задачу обсуждем.
Одно дело, когда в комбинаторной задаче речь идет о "делении на комады", "распределении конфет" и.т.д. Здесь мы должны знать различаются ли между собой конфеты, должности в командах и т.д. (хотя я не знаю, при какой именно трактовке условия, возникнет Ваш ответ.)

Совсем другое дело, когда в условии говорится о разбиении множества. Это по определению один из шести случаев классических комбинаторных соединений (остальные пять: сочетания, с повторениями и без, размещения, с повторениями и без, и разбиения чисел).
В любой книжке по дискретной математике числа Стирлинга второго рода (классика комбинаторики) вводятся в рассмотрение именно всвязи с этой задачей - разбиением множеств.

Цитата:

Если раскладываем белые шары по кучкам, то по совету VAL просто перебираем варианты.

А это, как раз, разбиение чисел.
Если слагаемых 3, то легко выписать общую формулу:

$$ p_3(n) = \left\{ \begin{array}{ll} \frac{n^2}{12}, & n \equiv 0 (\mod 6)\\ \frac{n^2}{12}-\frac1{12}, & n \equiv 1 (\mod 6)\\ \frac{n^2}{12}-\frac1{3}, & n \equiv 2 (\mod 6)\\ \frac{n^2}{12}+\frac1{4}, & n \equiv 3 (\mod 6)\\ \frac{n^2}{12}-\frac1{3}, & n \equiv 4 (\mod 6)\\ \frac{n^2}{12}-\frac1{12}, & n \equiv 5 (\mod 6)\\ \end{array} \right. $$

В общем случае возможна только рекуррентная формула или асимптотика.

Цитата:

(1,1,8), (1,2,7), (1,3,6), (1,4,5), (2,2,6), (2,3,5), (2,4,4), (3,3,6), (3,4,3). 9 вариантов.

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

[gris]

Ничего, что я опять про футболки?
Итак $3^{10}$ это количество способов раскрасить 10 ребят в 3 цвета. Мы исключаем 3 способа, когда все раскрашены в один цвет. Потом его прибавляем как один.

Вариантов раскраски трех групп 6.
Но могут быть варианты, когда одно подмножество пустое и остаётся два цвета. Но там тоже 6 вариантов, а я почему то думал 3.
Спасибо, разобрался
VAL, я разумеется повторил, да ещё с ошибкой, то что Вы написали. Никак не научусь внимательно вчитываться

[ewert]

Да. Я только на всякий случай уточню (вдруг кому интересно).

Проблема в том, что все непустые подмножества различны, а вот все пустые одинаковы. Поэтому перестановка двух подмножеств порождает новую комбинацию (в исходной, "пронумерованной" интерпретации) -- за исключением случая, когда переставляются два именно пустых подмножества.

Ну так мы сначала выкидываем все комбинации с двумя пустыми (их три), честно делим на $(3!)$ и потом снова добавляем выкинутую, но без учёта порядка она будет уже одна.

[VAL]

ewert писал(а):

ну, положим, числа Стирлинга поди ещё подсчитай,

Во-первых, для них существуют формулы. С использованием рекуррентного соотношения $S(n+1,k+1) = S(n,k)+(k+1)S(n,k+1)$ и очевидного свойства $S(n,1)=1$ добраться до $S(10.3)$ совсем не трудно. Есть и явные (но не слишком компактные) формулы.
А во-вторых, я всегда ругаю студентов, когда они вместо, например $9^8S(10,5)$, подсовывавают мне в качестве ответа к комбинаторной задаче какие-то миллиарды. Ведь в первом случае виден ход решения, а во втором мне надо самому считать до посинения

Цитата:

а для количества разбиений на 3 непустых и непронумерованных подмножества можно написать и вполне явное выражение:

$${3^9-2^{10}+1\over2}\;.$$

Конечно, можно и так. Использование принципа включения и исключения - еще один из многих способов решения данной задачи.

Цитата:

И, кстати, остался предыдущий вопрос: сколько способов разбить на подмножества (возможно, пустые) без учёта порядка?

Продолжаю настаивать, что это другая задача.
Но вопроса в любоим случае нет. В терминах чисел Стирлинга это $\sum_{i=1}^k S(n,i)$

[ewert]

VAL писал(а):

С использованием рекуррентного соотношения $S(n+1,k+1) = S(n,k)+(k+1)S(n,k+1)$ и очевидного свойства $S(n,1)=1$ добраться до $S(10.3)$ совсем не трудно.

Я честно пытался этими соотношениями воспользоваться (чтоб проконтролировать Ваш ответ). Но очень быстро плюнул.

[TOTAL]

$$C_{10}^1\left(\frac{1}{2} C_{9}^1+C_{9}^2+C_{9}^3+C_{9}^4 \right) +C_{10}^2\left(\frac{1}{2} C_{8}^2+C_{8}^3+\frac{1}{2}C_{8}^4 \right)+C_{10}^3\left(\frac{1}{2} C_{7}^3 \right)$$

Вот такой результат с чем-нибудь правильным совпадает?

[GAA]

Да, совпадает.

$$C_{10}^1\left(\frac{1}{2} C_{9}^1+C_{9}^2+C_{9}^3+C_{9}^4 \right) +C_{10}^2\left(\frac{1}{2} C_{8}^2+C_{8}^3+\frac{1}{2}C_{8}^4 \right)+C_{10}^3\left(\frac{1}{2} C_{7}^3 \right) = S(10,3)$$

,
через $S(n,r)$, как и выше, обозначены числа Стиргинга второго рода.