Задача
COM-B1-M04-P016 Пары вложенных подмножеств
#16
★★★☆☆ Уровень 3 из 5
Сколько пар \((A,B)\) подмножеств \(n\)-элементного множества удовлетворяют \(A\subset B\)?
Для каждого элемента есть три состояния.
Каждый элемент либо не входит в \(B\), либо входит в \(B\), но не входит в \(A\), либо входит в оба множества. Три независимых состояния для каждого из \(n\) элементов дают \(3^n\) пар.
Сильная кодировка объекта по элементам.