How many non-negative integers with not more than 1993 decimal digits have non-decreasing digits? [For example, 55677 is acceptable, 54 is not.]
Solution
Answer: 2002C9 = 1,398,276,498,745,133,921,413,500.
Let mCn represent the binomial coefficient m!/(n! (m-n)! ). We prove first a simple lemma: kCk + (k+1)Ck + (k+2)Ck + ... + nCk = (n+1)C(k+1). This is an almost trivial induction. It is obviously true for n = k. Suppose it is true for n. Then the sum up to (n+1)Ck = (n+1)C(k+1) + (n+1)Ck = (n+2)C(k+1) as required.
Call numbers with non-decreasing digits NDDs. 0 is a special case, it is the only NDD involving the digit zero. It is convenient to regard 0 as having 0 digits. With this convention, we show that in base n there are (n+m-2)Cm NDDs with m digits. We use induction on m. Clearly the result is true for m = 1 (and any n) provided we accept the convention just stated. Suppose it is true for m. Now consider an m+1 digit number.
If its first digit is 1, then the remaining digits form an m digit NDD, so there are just (n+m-2)Cm possibilities. If the first digit is 2, then the remaining m digits are all at least 2, so the number of possibilities is the same as for m digit NDDs to base m-1, which is (n+m-3)Cm. Similarly, for first digit 3 we have (n+m-4)Cm possibilities, and so on down to (n+m-n)Cm = 1 possibilities for first digit n. Hence the total number of possibilities is mCm + (m+1)Cm + (m+2)Cm + ... + (m+n-2)Cm = (m+n-1)C(m+1), by the lemma. So the result is true for m+1. Hence for all m.
In particular, there are (n+8)C8 n-digit decimal NDDs. Note that n=0 also gives the correct number 1 for 0-digit numbers. Hence there are 8C8 + 9C8 + ... + 2001C8 decimal numbers with at most 1993 digits and all digits non-decreasing. Applying the lemma again, this sum is 2002C9.
© John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002