Какую формулу комбинаторики использовать?

Всем привет. Помогите с формулой, не могу сообразить: количество чисел с числа, например, 100101, нули не могут стоять спереди
Буду очень благодарен
  • Вопрос задан
  • 98 просмотров
Пригласить эксперта
Ответы на вопрос 2
jcmvbkbc
@jcmvbkbc
http://dilbert.com/strip/1998-08-24
Посчитать количество нулей и единиц в исходном числе. Пусть это будут N0 и N1.
Если нули не могут стоять спереди, значит спереди может стоять только единица. Если N1 > 0, уменьшить N1 на 1, иначе нет решений.
Теперь нужно упорядочить N0 нулей и N1 - 1 единицу всеми возможными способами. Их будет (N0 + N1 - 1)!. Но поскольку все нули и все единицы одинаковы, то разных комбинаций будет в N0! * (N1 - 1)! раз меньше, (N0 + N1 - 1)! / (N0! * (N1 - 1)!). Это -- перестановки с повторениями. Для числа 100101 результат 10:
100011, 100101, 100110, 101001, 101010, 101100, 110001, 110010, 110100, 111000.
Ответ написан
sgjurano
@sgjurano
Разработчик
Сколько угодно если число разрядов не ограничено.
Если же такое ограничение есть, то 2 в степени k, где k – число оставшихся разрядов.

Это если речь о бинарной системе счисления, разумеется.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы