Задача 60399

Темы:    [ Правило произведения ] [ Объединение, пересечение и разность множеств ] [ Раскладки и разбиения ]

Сложность: 3- Классы: 8,9

Условие

Имеется множество C, состоящее из n элементов. Сколькими способами можно выбрать в C два подмножества A и B так, чтобы
а) множества A и B не пересекались;
б) множество A содержалось бы в множестве B?

Решение

  а) Задача эквивалентна разбиению множества C на три подмножества A, B и   D = C \ (A ∪ B).  Это, в свою очередь, эквивалентно разложению n различных монет по трём карманам (см. задачу 60348).

  б) Вместо выбора подмножеств A и B можно выбрать непересекающиеся подмножества A и E, а потом положить  B = A ∪ E.  Поэтому пункты а) и б) эквивалентны.

Ответ

3ⁿ способами (в обоих случаях).

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	2
Название	Комбинаторика
Тема	Комбинаторика
параграф
Номер	3
Название	Размещения, перестановки и сочетания
Тема	Классическая комбинаторика
задача
Номер	02.065