3. Подмножества

Сначала нужно вывести формулу для расчета количества подмножеств, начинающихся с определенной буквы. Это просто произведение увеличенных на 1 количеств букв, так как если у нас есть `K` букв 'D' ее можно брать в количестве 0, 1, …, `K` (то есть `K+1` вариант для выбора).

Рассмотрим подмножества, начинающиеся с одинаковой подстроки (префикса). Они упорядочены следующим образом: сначала идут подмножества, в которых количество одинаковых букв (очередной буквы алфавита после последней буквы префикса) постепенно возрастает. Таких строк `K`, если количество букв `K`. Затем идет `(K+1)` группа, у которых число букв (очередной буквы алфавита после последней буквы префикса) постепенно убывает до 0. Формула для количества строк в группе уже выведена.

Алгоритм достаточно простой – проходим по буквам алфавита и набираем нужное их количество, пока не дойдем до нужного номера и в результате получаем подмножество.