Техника

вопрос по комбинаторике...помогите пожалуйста)

Дано множество U из 9 элементов. Каким числом способов в нём можно выбрать три подмножества A, B, C так, чтобы выполнялись заданные условия? |A-B|=3, |B∩C-A|=5 заранее спасибо!
Из первого условия понятно, что ровно 3 элемента должны принадлежать A и при этом не принадлежать B.
Из второго условия - ровно 5 элементов таких, которые принадлежат одновременно B и C и не принадлежат A.
Значит, алгоритм построения таких множеств получается такой. Выбираем произвольно 3 элемента и впихиваем их в A (у нас C(3,9) вариантов) . Эти трое не могут принадлежать B, поэтому для B остаётся 6 элементов. Из этих 6 выбираем любые 5 и впихиваем в B (у нас C(5,6) = 6 вариантов) . Ту же пятерку "впихиваем" в C.
В множестве C у нас 5 элементов. Посмотрим, что можно сделать с теми первыми 3, которые мы засунули в A. Так как они в B точно не входят, то сунуть их в C или нет, они не будут принадлежать "B пересечь C" и на второе условие не повлияют, поэтому число вариантов возрастает в 2^3 = 8 раз (каждый элемент независимо может войти в C или не войти) .
Что касается остального 1 элемента, тут перебором вариантов находим, что он может
1) принадлежать A, B, C,
2) принадлежать A, B,
3) принадлежать B,
4) принадлежать C,
5) не принадлежать ни одному из них.
Так что умножаем число вариантов ещё на 5.
Итак, C(3,9) * C(5,6) * 8 * 5 = 20160 способа
Edi Islanov
Edi Islanov
54 366
Лучший ответ