комбинаторика

[Mr.Cherry]

Дано множество U из n элементов. Каким числом способов можно выбрать три подмножества A,B,C так, чтобы выполнялись заданные условия?
n=8, |A пересек B пересек C| = 4, |(A объед B) - C| = 1

не уверен - как решать?
8*7*6*5 + 4 + 3 ^ 3 = 1711 ?

[PAV]

PAV:

Используйте принятые средства набора формул
$|A\cap B\cap C|$ и $A\cup B$ - гораздо лучше выглядит

[Mr.Cherry]

ну.. торопился..
$n=8, |A \cap B \cap C| = 4, |(A \cup B)-C| = 1$

[PAV]

Нужно использовать тот факт, что все множество объема $n$ представляется в виде объединения следующих восьми попарно непересекающихся множеств $ABC$, $\overline{A}BC$, ... $\overline{A}\overline{B}\overline{C}$, где знаки пересечения для краткости опущены, а черта обозначает дополнение множества.

[Mr.Cherry]

ээ.. совсем ничего не понял..
Диаграмму Эйлера—Венна то я сделал, но вот как сосчитать не могу понять..
п.с. сейчас наарисую..

[PAV]

Обозначьте $a_0b_0c_0=|ABC|$, $a_1b_0c_0=|\overline{A}BC|$... и выразите требуемые условия на объемы множеств через данные величины.

[Mr.Cherry]

ничего не понимаю...

вот картинка, те 4 элемента, что в жёлтой области можно выбрать 8*7*6*5 способами. так?
тот, что в синей - 4. так?
оставшиеся три могут распределиться по трём белым частям - 3 ^ 3 = 27.
В сумме - 1711.
так или я что то напутал?

[PAV]

Хорошая картинка. На самом деле в задаче явно не указано, предполагаются ли элементы различимыми или нет. Рассмотрим два случая.

Если элементы различимы, то сперва действительно поместим четыре из них в желтую часть. Но нужно понять, что так как результат нашей деятельности - это множество, то от порядка, в котором мы будем размещать эти элементы, ничего не зависит. Поэтому правильное число способов равно $\frac{8*7*6*5}{4!}=C_8^4$

Далее нужно ровно один элемент разместить ровно в одну из синих частей. Сам элемент из оставшихся можно выбрать четырьмя способами, и еще три способа выбрать синюю часть, куда его положить. Всего получается 4*3=12 способов.

После этого у нас остается еще 3 элемента, которые нужно разложить в оставшиеся белые части. Подумайте сами, сколько способов это сделать, но не забывайте, что кроме трех белых частей внутри С есть еще одна возможность - элемент можно класть в дополнение ко всем трем множествам (т.е. в $\overline{ABC}$), так как в условии не сказано, что множества A,B,C должны обязательно содержать все элементы.

Если же элементы неразличимы, то это значит, что нам нужно только расставить числа - сколько объектов в каждую часть пойдет. Число 4 уже стоит; далее в одну из синих частей нужно написать 1, а в остальные - нули; это можно сделать тремя способами. После этого надо посчитать число способов расставить числа в белые части так, чтобы их сумма не превосходила 3.

Добавлено спустя 1 минуту 26 секунд:

Да, забыл самое важное. ПОЧЕМУ ВЫ СКЛАДЫВАЕТЕ ВАРИАНТЫ? Это неправильно. Вспомните, когда в комбинаторике применяется "правило суммы", а когда - "правило произведения".

[Mr.Cherry]

спасибо. вроде разобрался...