If one allows non-leading zeros then there will be infinitely many solutions. Even if one excludes those, the count will be huge. I restrict further by enforcing that digits be (non-strictly) increasing. One can get all possible values from these solutions simply by reordering and, if desired, inserting zeros.
The idea is to use Solve
, giving restrictions on the variables as noted above, and using the Integers
domain setting. Solve
will then use integer linear programming under the hood and cough up a solution set in reasonable (I think) time.
n = 36;
vars = Array[x, n];
AbsoluteTiming[
soln = Solve[
Flatten[{Total[vars] == n, Map[0 <= # <= 9 &, vars],
Table[vars[[j]] >= vars[[j + 1]], {j, Length[vars] - 1}]}],
vars, Integers];]
Length[soln]
(* Out[71]= {32.0909, Null}
Out[72]= 7657 *)
Check the first and last ten.
10^Range[0, n - 1].vars /. soln[[1 ;; 10]]
10^Range[0, n - 1].vars /. soln[[-10 ;; -1]]
(* Out[73]= {111111111111111111111111111111111111, \
11111111111111111111111111111111112, \
1111111111111111111111111111111122, \
111111111111111111111111111111222, 11111111111111111111111111112222, \
1111111111111111111111111122222, 111111111111111111111111222222, \
11111111111111111111112222222, 1111111111111111111122222222, \
111111111111111111222222222}
Out[74]= {225999, 135999, 45999, 1116999, 126999, 36999, 117999, \
27999, 18999, 9999} *)