Я утверждаю, что эту проблему легко решить, если ее правильно рассмотреть. Вам не важен порядок элементов, только если они появляются в подмножестве not.
Подсчитайте, сколько раз каждый элемент появляется в наборе. Для одного набора элементов {A} сколько существует подмножеств? Очевидно, есть только два набора. Теперь предположим, что мы добавили еще один элемент B, отличный от A, для формирования множества {A, B}. Мы можем сформировать список всех наборов очень легко. Возьмите все наборы, которые мы сформировали, используя только A, и добавьте ноль или одну копию B. Фактически мы удваиваем количество наборов. Ясно, что мы можем использовать индукцию, чтобы показать, что для N различных элементов общее число наборов составляет всего 2 ^ N.
Предположим, что некоторые элементы появляются несколько раз? Рассмотрим множество с тремя копиями A. Таким образом, {A, A, A}. Сколько подмножеств вы можете сформировать? Опять же, это просто. У нас может быть 0, 1, 2 или 3 копии A, поэтому общее количество подмножеств равно 4, так как порядок не имеет значения.
Как правило, для N копий элемента A мы получим N + 1 возможных подмножеств. Теперь расширьте это, добавив некоторое количество M копий B. Итак, у нас есть N копий A и M копий B. Сколько всего подмножеств? Да, это тоже очевидно. К каждому возможному подмножеству, содержащему только A (их было N + 1), мы можем добавить от 0 до M копий B.
Таким образом, общее количество подмножеств, когда у нас есть N копий A и M копий B, просто. Это должно быть (N + 1) * (M + 1). Снова, мы можем использовать индуктивный аргумент, чтобы показать, что общее количество подмножеств является произведением таких терминов. Просто подсчитайте общее количество повторов для каждого отдельного элемента, добавьте 1 и возьмите произведение.
Посмотрите, что происходит с множеством {A, B, B}. Мы получаем 2 * 3 = 6.
Для множества {A, A, B, B} получаем 3 * 3 = 9.