How many 6 digit positive integers have their digits in weakly decreasing order?

Question

How do I solve this combinatorically? I'm not quite sure how to approach this since each digit is dependent on the digit before it.

For example, if the first digit is a 9, then there are 10 possible choices for the second digit (0-9). 9 _ _ _ _ _. If we choose 5 to be the second digit, then the third digit has 6 possible choices (0-5). 9 5 _ _ _ _. If we choose 0 to be the third digit, then the fourth digit has 1 possible choices (0). 9 5 0 _ _ _. And for the rest of the digits, only 0 is possible. 9 5 0 0 0 0

What formula do I use to solve this? Could I use Stirling numbers or Permutations and Combinations in this situation?

Answer 1

HINT: This is the same as counting the $8$-digit numbers that start with $9$, end with $0$, and have their digits in weakly decreasing order, and the latter are easier to count.

Let $d_0d_1d_2d_3d_4d_5d_6d_7$ be such a number, so that

$$9=d_0\ge d_1\ge\ldots\ge d_6\ge d_7=0\,.$$

For $k=0,\ldots,6$ let $x_k=d_k-d_{k+1}$; each of these numbers is non-negative.

• Show that $x_0+x_1+\ldots+x_6=9$.
• Explain why there is a bijection between the numbers that we’re counting and solutions to this equation in non-negative integers.
• Use the stars and bars method to compute the number of such solutions.

Answer 2

Notice that each number with weakly decreasing digits is completely determined by the number of times each digit appears. For instance, if the number contains one 5, two 3s, one 2, and two 1s, it must be the number 533211.

Therefore, if we let $x_i, 1 \leq i \leq 9$, be the number of times digit $i$ appears in the number, the number of six-digit strings with weakly decreasing digits which can be formed is the number of solutions of the equation $$x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 = 6 \tag{1}$$ in the nonnegative integers.

A particular solution of this equation corresponds to the placement of $10 - 1 = 9$ addition signs in a row of six ones. For instance, $$+ 1 1 + 1 + 1 1 + + 1 + + + +$$ corresponds to the solution $x_0 = 0$, $x_1 = 2$, $x_2 = 1$, $x_3 = 2$, $x_4 = 0$, $x_5 = 1$, $x_6 = x_7 = x_8 = x_9 = 0$ and the number 533211.

Thus, the number of six-digit weakly decreasing strings is the number of solutions of equation 1 in the nonnegative integers.

The number of such solutions is $$\binom{6 + 10 - 1}{10 - 1} = \binom{15}{9}$$ since we must choose which nine of the $15$ positions required for six ones and nine addition signs will be filled with addition signs.

The astute reader will have noticed that I have referred to six-digit strings with weakly decreasing digits. These strings include 000000, which corresponds to the nonnegative number 0. Since we only wish to count positive numbers, we must subtract the zero string from the total.