2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 разбиения на подмножества
Сообщение06.11.2013, 11:25 
нужно посчитать количество отношений эквивалентности на множестве $X=\{1,2,3,4,5,6\}$
я пошел через разбиения на множества. У меня получились разбиения такого вида:
$\{1\}\{2\}\{3\}\{4\}\{5\}\{6\}$ количество:1
$\{1\}\{2,3,4,5,6\}$ количество:6
$\{1,2\} \{3,4,5,6\}$ количество:15
$\{1,2,3\}\{4,5,6\}$ количество:10
$\{1\}\{2\}\{3,4,5,6\}$ количество:15
$\{1,2\}\{3\}\{4\}\{5\}\{6\}$ количество:15
$\{1,2,3,4,5,6\}$ количество:1
$\{1\}\{2,3,4\}\{5,5\}$ количество:60
$\{1\}\{2\}\{3\}\{4,5,6\}$ количество:20
$\{1,2\}\{3,4\}\{5\}\{6\}$
$\{1,2\}\{3,4\}\{5,6\}$
Всего таких разбиений 203(числа Белла), но сколько вариантов в последних двух разбиениях и как их(количество) обосновать я не знаю.

 
 
 
 Re: разбиения на подмножества
Сообщение06.11.2013, 11:56 
А чем сложнее подсчет разбиений $\{1,2\}\{3,4\}\{5\}\{6\}$ от $\{1\}\{2,3,4\}\{5,6\}$?

 
 
 
 Re: разбиения на подмножества
Сообщение06.11.2013, 13:31 
Если делать тем же способом (размещениями), то получается 90 вариантов, что слишком много

 
 
 
 Re: разбиения на подмножества
Сообщение06.11.2013, 13:40 
Аватара пользователя
А вы учли, что $\{1,2\},\{3,4\}$ и $\{3,4\},\{1,2\}$ это одно и то же.

 
 
 
 Re: разбиения на подмножества
Сообщение06.11.2013, 13:42 
Просто что-то (или всё) вы посчитали несколько раз.
Ну, например, у вас правильно посчитано
$\{1,2,3\}\{4,5,6\}$ количество:10
$\{1\}\{2\}\{3\}\{4,5,6\}$ количество:20
Считали ведь практически одинаково для первого и второго случая?
Ну и если вы будете давать ответ по принципу черного ящика, то тяжело сказать, что в этом ящике не так.

 
 
 
 Re: разбиения на подмножества
Сообщение06.11.2013, 13:53 
Аватара пользователя
У меня получилось в последних двух случаях 45 и 15

 
 
 
 Posted automatically
Сообщение06.11.2013, 17:15 
Аватара пользователя
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

Starosta46
Наберите все формулы и термы $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
вернул

 
 
 
 Re: разбиения на подмножества
Сообщение06.11.2013, 17:43 
provincialka в сообщении #785598 писал(а):
У меня получилось в последних двух случаях 45 и 15

можете объяснить как?

 
 
 
 Re: разбиения на подмножества
Сообщение06.11.2013, 18:01 
Аватара пользователя
$\{1,2\}\{3,4\}\{5\}\{6\}$
То есть два по одному и два по два. Сначала выбираем два по одному. Способов будет $\frac{6\cdot5}{2}$. На два делим потому, что порядок самих одноэлементных множеств не важен.
Далее выбираем множество из двух элементов. Вернее, два таких множества, но если первое выбрано, второе определяется однозначно.
Полученное число также делим на 2, и по тем же причинам.

 
 
 
 Re: разбиения на подмножества
Сообщение06.11.2013, 18:19 
provincialka в сообщении #785674 писал(а):
$\{1,2\}\{3,4\}\{5\}\{6\}$

с этим понял, а как делать это $\{1,2\}\{3,4\}\{5,6\}$?

 
 
 
 Re: разбиения на подмножества
Сообщение06.11.2013, 19:13 
Аватара пользователя
Ну уж это сами. Выберите все пары и поделите на $3!$.

 
 
 
 Re: разбиения на подмножества
Сообщение06.11.2013, 19:59 
provincialka в сообщении #785700 писал(а):
Выберите все пары и поделите на $3!$.

для первой скобки это $C^2_6=15$ для второй: $C^2_4=6$ для третьей $C^2_2=0$. а на 3!, так как всего 3! вариантов таких скобок?

 
 
 
 Re: разбиения на подмножества
Сообщение06.11.2013, 20:02 
Аватара пользователя
Starosta46 в сообщении #785714 писал(а):
$C^2_2=0$

Вообще-то единица (думаю, это описка). Да, все подмножества равновелики, так что их можно свободно переставлять.

 
 
 
 Re: разбиения на подмножества
Сообщение06.11.2013, 20:03 
provincialka в сообщении #785715 писал(а):
Starosta46 в сообщении #785714 писал(а):
$C^2_2=0$

Вообще-то единица (думаю, это описка).

да, забылся малец. Спасибо за помощь

 
 
 
 Re: разбиения на подмножества
Сообщение07.11.2013, 05:08 
Имхо, проще решать по-другому. Введем функцию $P(x)$ - число отношений эквивалентности на множестве из $x$ элементов. Эта функция неплохо выражается рекуррентно, и посчитать $P(1)$ , $P(2)$ , $P(3)$ , $P(4)$ , $P(5)$ , $P(6)$ у меня вчера (как увидел эту задачку) получилось за вполне недлинное время

 
 
 [ Сообщений: 18 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group