>>14187119Look at the non-decreasing case first.
Without loss of generality, assume it is a 7 digit number that starts with 0 and ends with n (your 6 digit number will be the last 6 digits).
Digit i minus digit i-1 will be non-negative.
The sum of these differences will be n.
The first difference must be positive since the first digit of your number can't be 0.
The coefficient of x^n in (x+x^2+...+x^9)(1+x+x^2+...+x^9)^5 will give the answer since the differences sum to n.
You can modify this to x(1+x+x^2+...)^6 = x/(1-x)^6 without changing the answer.
[x^n] x/(1-x)^6 = D^n[x/(1-x)^6](x=0)/n! = n*D^(n-1)[1/(1-x)^6](x=0)/n!
= n(5+n-1)/(5!*n!) will be the non-decreasing count for a last digit = n.
The non-increasing case can be done similarly (just do 9 minus each digit to turn it into a non-decreasing number)
n is 9 minus the last digit.
The first digit isn't 9 (this would mean a leading 0) (if it were 9, the non-decreasing number must be 999999 which corresponds to 000000 non-increasing)
[x^n] (1+x+x^2+...+x^9)^6 = [x^n] 1/(1-x)^6 = D^n[1/(1-x)^6](x=0)/n! = (5+n)!/(5!*n!)
subtract 1 for n=9 for the special case 000000
let n = 9-m
(5+9-m)!/(5!*(9-m)!) - I[m=0] will be the non-increasing count for last digit = m
for last digit = n not 0, nnnnnn is counted in both.
subtract 1 for last digit not 0.
The subtotal from both for last digit n is n(5+n-1)/(5!*n!) + (5+9-n)!/(5!*(9-n)!) - I[n=0] - I[n!=0]
= n(5+n-1)/(5!*n!) + (5+9-n)!/(5!*(9-n)!) - 1
