Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many non-decreasing sequences of $7$ decimal digits are there? ($3334559$ and $0223448$ are two examples).

Solution:

If we add a $0$ to the beginning and a $9$ to the end, every sequence of $7$ nondecreasing decimal digits defines a unique sequence of $8$ non-negative gaps which must sum to $9$ (e.g. for $3334559$ the gaps are $3+0+0+1+1+0+4+0 = 9$, and for $0223448$ the gaps are $0+2+0+1+1+0+4+1 = 9$). We need $7$ separators to count the partitions (the digits themselves separate the gaps), and we then find that there are $\binom{9+7}{7} = 11,440$ of them.

I am having some trouble in understanding the very first statement of this solution, in spite of the given example. I just couldn't understand what they exactly meant there. Could anybody explain this to me more lucidly?

However,the second sentence is consistent to the stars and bars idea and I have no doubt in understanding it.

PS:This is the #$6$ problem from here.


Added:

I guess now I have understood the trick, but this seems something new to me. I was wondering how to approach this problem in different way? Any ideas?

share|improve this question
1  
Re your addendum, I would have approached the problem as follows: I have ten buckets, labeled 0 through 9, and 7 balls. How many different ways are there of placing the balls in the buckets? It's still stars and bars (this time 9 bars and 7 stars) but maybe is a more intuitive approach. –  user7530 Oct 17 '11 at 13:04
add comment

1 Answer

up vote 4 down vote accepted

If you have seven digits $d_1 d_2 d_3 d_4 d_5 d_6 d_7$ and pad it with 0 and 9 as indicated ($0d_1 d_2 d_3 d_4 d_5 d_6 d_79)$, you can look at the eight differences of consecutive digits (I have no idea why the author called them "gaps," which may be the source of confusion) $$\begin{align*}d_1 &- 0\\ d_2 &- d_1\\ d_3 &- d_2,\end{align*}$$ and so on. Since the digits are nondecreasing each of these differences is nonnegative, and their sum telescopes leaving 9: $$9-d_7 + d_7 - d_6 + \ldots + d_2 - d_1 + d_1 - 0 = 9-0 = 9.$$

The number of ways to pick eight nonnegative numbers that sum to 9 is then the "stars and bars" problem, with 9 stars and 7 bars.

share|improve this answer
1  
Aha,thanks,and I agree "gaps" made things confusing for me ...however the overall solving trick seems to be a very good one! –  Quixotic Oct 17 '11 at 12:17
    
Do you have any idea about why such a choice of padding?I mean is this problem specific or something that is more common? –  Quixotic Oct 17 '11 at 12:19
    
@FoolForMath: This choice of padding gives known values to the ends, reducing it to a known problem. Alternately you could do it for each possibility of $d_1$ and $d_7$, but there are a bunch of cases. –  Ross Millikan Oct 17 '11 at 12:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.