Какую формулу комбинаторики использовать?
Посчитать количество нулей и единиц в исходном числе. Пусть это будут 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.
Сколько угодно если число разрядов не ограничено.
Если же такое ограничение есть, то 2 в степени k, где k – число оставшихся разрядов.
Это если речь о бинарной системе счисления, разумеется.