Take non decreasing, get non negative (Posted on 2007-05-29)

	Submitted by K Sengupta
Rating: 4.3333 (3 votes)
Solution:	(Hide)
The required total number of non-negative integers is: 50C9 = 2505433700 EXPLANATION: 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 + ... + 49C8 decimal numbers with at most 41 digits and all digits non-decreasing. Applying the lemma again, this sum is 50C9 = 2505433700. ********************************** Also check out Charlie's methodology provided in this location . **************************************** *** Adapted from a problem appearing in 10th Balkan Math Olympiad.

	Subject	Author	Date
	Solution	Praneeth	2007-08-31 03:46:54
	No Answer (spoiler)	Vernon Lewis	2007-05-29 20:51:07
	re: solution	George	2007-05-29 18:29:45
	solution	Charlie	2007-05-29 16:49:02
	Solution	Guest	2007-05-29 16:31:48