Количество подпоследовательностей в данной последовательности

Question

Если мне дать последовательность X = {x1,x2,....xm}, то у меня будет (2^m) подпоследовательности. Кто-нибудь может объяснить, как я могу прийти к этой формуле интуитивно? Я могу начать с 3 элементов, затем 4, а затем 5 и прийти к этой формуле, но я не думаю, что понимаю. Откуда взялась «2»? Я не делю пополам или что-то здесь. Спасибо за помощь.

Answer 1

В основном у вас будет вдвое больше подпоследовательностей для каждого нового числа, поскольку у вас будет (2^(m-1)) «эквивалентных» подпоследовательностей, которые сдвинуты на один пробел вправо (при условии горизонтального упорядочения и сложения справа) плюс подпоследовательность всех элементы.

Answer 2

Каждый элемент находится в подпоследовательности или нет.Поэтому, начиная с первого x1, есть два набора подмножеств: те, в которые включен x1, и те, которые не включены.То же самое можно сделать с меньшей подзадачей {x2, ..., xm}.Таким образом, вы в итоге получаете 2 ^ м.