Количество наборов битовой строки

Как пользоваться формулой

1. Определите длину строки n.
2. Проверьте, что каждая позиция имеет ровно два варианта.
3. Вычислите 2^n.
4. Если есть ограничения на строки, формулу нужно уточнять под эти ограничения.

Историческая справка

Подсчет двоичных наборов основан на классическом правиле умножения в комбинаторике. Задолго до компьютеров математики считали варианты независимых выборов, а двоичный случай стал особенно важным после появления логики и вычислительных устройств.

В XIX веке Джордж Буль развил алгебру логики, где значения истинности можно связывать с двумя состояниями. В XX веке электронные компьютеры сделали двоичные состояния физической основой хранения и обработки данных: высокий или низкий уровень сигнала, включено или выключено.

Теория информации Шеннона придала биту количественный смысл, а степени двойки стали естественным языком для размеров памяти, кодов и адресов. Поэтому формула 2^n одновременно является простой комбинаторикой и фундаментальным правилом цифровой техники.

Пример

Задача. Сколько различных битовых строк длины 10 можно составить? Дано: n=10, каждая позиция может быть 0 или 1. По формуле N=2^n получаем N=2^10=1024. Ответ: существует 1024 разных битовых строки длины 10. Проверка: для 1 бита есть 2 строки, для 2 битов — 4, для 3 битов — 8. При добавлении каждого нового бита число вариантов удваивается, поэтому для 10 битов получается последовательное удвоение до 1024. Дополнительная проверка: 10 бит часто соответствуют числу 1024 в размерах памяти. Это не случайное округление, а точная степень двойки 2^10.

Частая ошибка

Часто считают 2n вместо 2^n и сильно занижают число вариантов. Вторая ошибка — начинать счет с нуля и говорить, что строк длины n равно 2^n-1; нулевая строка 000...0 тоже является допустимым набором. Еще путают длину строки n с числом единиц в ней. Если требуется ровно k единиц, нужна уже формула сочетаний, а не 2^n.