Задача
Имеется множество C, состоящее из n элементов. Сколькими способами можно выбрать в C два подмножества A и B так, чтобы
а) множества A и B не пересекались;
б) множество A содержалось бы в множестве B?
Решение
а) Задача эквивалентна разбиению множества C на три подмножества A, B и D = C \ (A ∪ B). Это, в свою очередь, эквивалентно разложению n различных монет по трём карманам (см. задачу 160348). б) Вместо выбора подмножеств A и B можно выбрать непересекающиеся подмножества A и E, а потом положить B = A ∪ E. Поэтому пункты а) и б) эквивалентны.
Ответ
3n способами (в обоих случаях).
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет