1
$\begingroup$

Two n-digit sequences of digits 0, 1.....9 are said to be of the same type if the digits of one are a permutation of the digits of the other. For n = 8, for example, the sequences 03088929 and 00238899 are the same type. How many types of n-digit integers are there?

$\endgroup$
  • 5
    $\begingroup$ Hint: This can be reformulated as a stars-and-bars problem -- $n$ stars, 9 bars. $\endgroup$ – Henning Makholm Mar 16 '13 at 14:46
1
$\begingroup$

I would reformulate the problem as follows. For $k\in\{0,1,\dots,9\}$ let $x_k$ be the number of copies of the digit $k$ in your $n$-digit type; then

$$x_0+x_1+x_2+x_3+x_4+x_5+x_6+x_7+x_8+x_9=n\;,\tag{1}$$

and each of the $x_k$’s is a non-negative integer. Conversely, each solution of $(1)$ in non-negative integers describes a type of $n$-digit number. The number of solutions in non-negative integers of $(1)$ is well-known; as Henning said in the comments, this is a stars-and-bars problem, and the solution is

$$\binom{n+10-1}{10-1}=\binom{n+9}9=\binom{n+9}n\;.$$

The reasoning behind this solution is explained quite well in the linked article.

$\endgroup$
2
$\begingroup$

This kind of problem can be usually be solved in various waysI always try to translate into counting lattice paths across a rectangle, since that gives easy comparison of solutions and less risk of off-by-one errors. The number of paths across a $a\times b$ rectangle is $\binom{a+b}a$, since the length of any path is $a+b$ steps, and we have to choose $a$ horizontal (say) steps among them, the remainder being vertical. Here are two possibilities.

The classes of numbers are characterised by their histogram of the digit frequencies. However that is ragged-shaped, so instead make the cumulative histogram, tabulating how many digits${}<1$, how many${}<2$, up to how many digits ${}<9$ (we know there are no digits${}<0$ and $n$ digits${}<10$, so there is no need to record those numbers). Since column lengths weakly increase, the boundary of the histogram is a path across a rectangle $9$ squares wide and $n$ squares high.

Another approach is to sort the digits into weakly increasing order, and represent each digit by a column of that height. Again the boundary is a path across a rectangle with left and up steps only; this time the rectangle is $n$ places wide and $9$ high.

Either way you find $\binom{n+9}9=\binom{n+9}n$ solutions.

$\endgroup$

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.