"Ordered" Permutations

Question

Consider the following problem. I have $n$ placeholders. On each placeholder, I can place a number from $1$ to $9$. Now there are $9^n$ possible ways to fill the places, but I am only interested in the number of ways of sorted placements, i.e. for $n=3$, I would like to have

1,1,1
1,1,2 # but neither 2,1,1 nor 1,2,1
1,1,3 # but neither 3,1,1, nor 1,3,1
...

From brute force I know that for $n=3$ the number of placements is $165$, and for $n=4$ it is $495$ and for $n=5$ it is $1287$. But I wish to compute the number of placements for $n=50$.

Is there a mathematical notion for this kind of procedure?

Answer 1

With $n$ placeholders and $k$ numbers to put in there in ordered fashion (for you, $k=9$), the answer is

$$ \binom{n+k-1}{n} $$ To provide some intuition to the answer, and as an interesting aside, if you have a block pyramid of dimension $n$ and with $k$ blocks along an edge, then the answer to your question is also the number of blocks in the pyramid. The pyramid below has dimension $n=3$ and blocks along an edge $k=15$.

Answer 2

You have $n$ places. Each one of your «ordered permutations» is completely determined by the numbers $m_1$, $m_2$, $\dots$, $m_9$ which count the number of times $1$, $2$, $\dots, $9$ appear in it.

So to each such permutation we may assign the $9$-tuple $(m_1,\dots,m_9)$. Notice that $m_1+\cdots+m_9=n$. Moreover, if $(m_1,\dots,m_9)$ is any $9$-tu ple which satisfies this condition, there is a corresponding «ordered permutation».

All this means that you are really counting the number of $9$-tuples $(m_1,\dots,m_9)$ of non-negative integers which add up to $n$.

Answer 3

One way to look at this is to say that you have to place $8$ tokens, anywhere in between your placeholders, and then fill in each placeholder with the number $1+n$ where $n$ is the amount of tokens located before that placeholder. For example if all $8$ tokens are before the first placeholder, this gives you the sequence $(9,\ldots,9)$.

In how many ways can you place the tokens? That is a binomial coefficient, something choose $8$. Drawing a picture will help you.

Edit: MikeY spilled the beans, the answer is indeed $\left (\matrix {n+8\\8}\right)$.