8
$\begingroup$

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?

  • 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.2011-10-17

1 Answers 1

5

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.

  • 0
    @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.2011-10-17