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

[Meteroka]

найти двуми способами число разбиений множества A, состоящих из 10 элементов, на 3подмножества.
я что то не пойму их всего должно быть два или только два выбрать нужно?

[Парджеттер]

Meteroka в сообщении #176943 писал(а):

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

А какая вам разница? Вы задачу решили?

[Meteroka]

Парджеттер писал(а):

Meteroka в сообщении #176943 писал(а):

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

А какая вам разница? Вы задачу решили?

решить то решила... а кто его знает... вдруг исчо чего есть!

[gris]

А вот тут опять вопрос. Могут ли подмножества быть пустыми. Допустим, на три непустых подмножества.
Тогда второй вопрос - Эти три подмножества различаются или нет?
То есть будут ли разбиения
{1} {2} {3 4 5 6 7 8 9 10} и
{2} {1} {3 4 5 6 7 8 9 10}
различаться или нет?
Например, мы разбиваем класс на три команды - синих, красных и зелёных. Или просто на три группы без отличительных признаков.
Самый простой ответ, если подмножества могут быть пустыми и отличаются. Это $3^{10}$

[ewert]

gris писал(а):

Самый простой ответ, если подмножества могут быть пустыми и отличаются. Это $3^{10}$

А если могут быть пустыми, но не различаются?

[gris]

Тогда в 6 раз меньше.

[ewert]

Ага. А Вас не смущает, что количество способов окажется дробным?

[gris]

Да, я поспешил. Просто я рассуждал так. Дадим каждому ученику по синей, красной или зелёной футболке. А потом я и не знаю, что делать. Пойду спать.

[ewert]

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

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

[VAL]

Meteroka писал(а):

найти двуми способами число разбиений множества A, состоящих из 10 элементов, на 3подмножества.
я что то не пойму их всего должно быть два или только два выбрать нужно?

Конечно, их больше.
А какими двумя способами Вы решили?
Надеюсь, среди них был способ в одно действие, с использованием чисел Стирлинга второго рода? А то, почему-то среди участников обсуждения их никто не упомянул.

И еще два замечания:
1. Разбиения $\{1,2,3\},\{4,5,6\},\{7,8,9,10\}$ и $\{4,5,6\}, \{1,2,3\}, \{7,8,9,10\}$ не различаются.
2. Классы разбиения не могут быть пусты.
И то, и другое по определению разбиения.

[ewert]

VAL писал(а):

1. Разбиения $\{1,2,3\},\{4,5,6\},\{7,8,9,10\}$ и $\{4,5,6\}, \{1,2,3\}, \{7,8,9,10\}$ не различаются.
2. Классы разбиения не могут быть пусты.

Скорее всего, преподавателем ни то, ни другое не предполагалось. Иначе задача (с учётом двухспособовости) получается уж больно занудной.

[VAL]

ewert писал(а):

VAL писал(а):

1. Разбиения $\{1,2,3\},\{4,5,6\},\{7,8,9,10\}$ и $\{4,5,6\}, \{1,2,3\}, \{7,8,9,10\}$ не различаются.
2. Классы разбиения не могут быть пусты.

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

Гипотеза о том, что под разбиениями имелись в виду вовсе не разбиения, представляется мне маловероятной

Цитата:

Иначе задача (с учётом двухспособовости) получается уж больно занудной.

Один из способов решения вообще не требует усилий, просто пишем ответ $S(10,3)=9330$. И всё!
Другие способы более трудозатратны. Но не слишком.
Например, переберем все разбиения числа 10 на 3 слагаемых. Их не слишком много:
$1+1+8 = 1+2+7 = 1+3+6 = 1+4+5 = 2+2+6 = 2+3+5 = 2+4+4 = 3+3+4$
Для каждого случая тривиально выписывается количество соответствующих ему разбиений.
Например, для $2+3+5$ это $ C_{10}^2C_8^3 $
Остается всё это просуммировать.

[gris]

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

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

Если раскладываем белые шары по кучкам, то по совету VAL просто перебираем варианты. (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 вариантов и перебор как первый способ.

[ewert]

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

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

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

[gris]

ewert писал(а):

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

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

Увы, это ошибочное рассуждение.