0
$\begingroup$

How many 6-digit sequences are ascending, like 023689, 033588, or 222222?

A number may begin with 0 and can be repeated, but must be increasing.

I am not entirely certain how to approach this problem.

$\endgroup$
2
$\begingroup$

Notice that since the digits in the string are ascending, such a number is completely determined by how many times each digit appears in the string. For example, if the six digits $0, 2, 3, 6, 8, 9$ each appear once, we obtain the string $023689$. If the digits $0$ and $5$ each appear once and the digits $3$ and $8$ each appear twice in the six-digit string, then we obtain the string $033588$.

Let $x_i$, $0 \leq i \leq 9$, be the number of times that the digit $i$ appears in the six-digit string. Then $$x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 = 6$$ is an equation in the nonnegative integers. The number of ascending strings of length six is the number of solutions of this equation in the nonnegative integers.

A particular solution of the equation $$x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 = 6$$ 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 = 1, x_1 = 0, x_2 = x_3 = 1, x_4 = x_5 = 0, x_6 = 1, x_7 = 0, x_8 = x_9 = 1$ and the string $023689$, while $$1 + + + 1 1 + + 1 + + + 1 1 +$$ corresponds to the solution $x_0 = 1, x_1 = x_2 = 0, x_3 = 2, x_4 = 0, x_5 = 1, x_6 = x_7 = 0, x_8 = 2, x_9 = 0$ and the string $033588$. The number of such solutions is $$\binom{6 + 10 - 1}{10 - 1} = \binom{15}{9}$$ since we must choose which nine of the fifteen symbols required for six ones and nine addition signs will be filled with addition signs.

$\endgroup$
  • $\begingroup$ Thank you very much for the explanation. This corresponds to the stars and bars problem. I was wondering whether I would apply a similar formula but I never considered to represent the string in such format. There is so much information to probability and statistics. $\endgroup$ – Libor Zachoval Jul 27 '19 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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