Это комбинаторика.
Если бы не было ограничения на то, что первый символ не 0, то было бы гораздо проще. Частый прием в комбинаторике - подсчитать количество всех возможных вариантов, а потом вычесть количество "плохих" вариантов. Временно разрешим нулю быть первой цифрой, решим задачу. Потом зафиксируем ноль на первой позиции и подсчитаем сколько таких вариантов и вычтем их. Для этого можно вычеркнуть один ноль из числа, решить ту же самую задачу.
Еще, в вашей формуле направшивается добавить пустое число ("") в ответ. Давайте разрешим его и вычтем в конце 1.
Еще, очевидно, результат зависит только от количества каждой цифры в исходном числе, но не от их порядка.
Поэтому пусть f(a0,a1,...a9) - сколько есть способов расставить некторые из a0 нулей, a1 единиц, a2 двоек, и т.д. (ноль может идти в начале, число может быть пустым).
Ответ к задаче f(a0,a1,...a9)-1-min(a0,1)*f(a0-1,a1,...a9). Последнее слагаемое считает варианты, начинающиеся с нуля. Оно не вычитается, если нулей в числе нет. -1 посередине вычитает пустое число из ответа (но ее нет в последнем слагаемом, ведь мы там еще 0 в начале приписываем и пустое число надо считать).
Теперь самое интересное, формула для f(a0,a1,...a9). Замкнутой формулы я не нашел, но придумал, как считать алгоритмом.
Можно все варинаты разделить по количеству символов в числе (n), от 0 до суммы a0...a9. Давайте подумаем, где могуть быть девятки? i <= a9 из них попадут в ответ. Они могут быть на C(n, i) позициях. Останется разместить остальные цифры на n-i позиций.
Вырисовывается следующее динамическое программирование:
F(i, n) - сколько способов разместить первые i цифр на n позициях (возможно, беря не все цифры).
F(i,n) = sum (j=0..min(a[i-1], n)) F(i-1, n-j)*C(n, j)
F(0, n>0) = 0
F(i,0) = 1.
Ответ - sum(k=0..a0+...+a9) F(9, k)
У функции как бы неявный параметр массив a[] количеств всех цифр, но я его не включаю в параметры динамики, потому что по нему не надо мемоизировать.
Не забудьте, что для подсчета второй динамики, для f(a0-1,...a9) надо будет полностью отчистить мемеоизацию, потому что массив a поменялся же.
Этот алгоритм работает за O(9*n), где n - длина входного числа.
Вот пример для входного числа 112: все цифры, которых в числе нет можно выкинуть из рассмотрения и работать с массивом a={2,1} (для всех десяти цифр слишком много писать).
F(0,0) = 1
F(0,1) = 0
F(0,2) = 0
F(0,3) = 0
F(1, 0) = 1
F(1,1) = F(0, 1)*C(1,0) + F(0,0)*C(1,1) = 1
F(1,2) = F(0,2)*C(2, 0)+ F(0,1)*C(2,1) + F(0,0)*C(2,2) = 1
F(1,3) = F(0,3)*C(3, 0)+ F(0,2)*C(3,1) + F(0,1)*C(3,2) = 0
F(2,0) = 1
F(2,1) = F(1,1)*C(1, 0) + F(1,0)*C(1,1) = 2
F(2,2) = F(1,2)*C(2, 0) + F(1,1)*C(2,1) = 3
F(2,3) = F(1,3)*C(3, 0) + F(1,2)*C(3,1) = 3
Ответ F(2,3)+F(2,2)+F(2,1)+F(2,0) = 3+3+2+1= 9.
Вычитаем 1 (пустое число) и получаем 8 чисел, как у вас в примере для 112.
Средний
