Number of ways to put $k$ different numbers in $n$ place

Question

I am working on problem which simplifies to the following which I can't solve. Please help.

There are $n$ places and I want to put number $1$ through $k$ in these places. Each place must have one number, and each number has to appear at least once. Of course, $n\geq k$.

For example, if $n=3$ and $k=2$, then there are 6 ways:

• 112
• 121
• 122
• 211
• 212
• 221

What is the total number of ways of doing this?

Answer 1

Try with inclusion-exclusion principle. For $1\leq i \leq k$ define $A_i$ as the set of all arrangements in which number $i$ does not appear and find $|(A_1 \cup \cdots \cup A_k)^c|$.

Just for fun, the number you get can also be expressed in terms of Stirling numbers of the second kind, since it equals $S(n,k)k!$. Also, this is the number of surjective maps from a set with $n$ elements to a set with $k$ elements.

So, let's compute it. It is obvious that

• all $k\choose 1$ sets $A_{i}$ ($A_1$, $A_2$, $\dots$, $A_n$) are of the same size,

• all $k\choose 2$ sets $ A_{i_1} \cap A_{i_2}$, $i_1<i_2$, are of the same size

  $\vdots$

• all of the $k\choose k$ ($=1$) sets $A_{i_1}\cap \dots \cap A_{i_{k}}$, $i_1 <\cdots < i_{k}$, are of the same size

Therefore, we just have to compute $a_i = |A_1 \cap \dots\cap A_i|$ for all $1\leq i\leq k$, which is quite simple. Since we can put any of the numbers $i+1$, $\cdots$, $k-1$ and $k$ (that is $k-i$ numbers) in the first, in the second, ... , and in the $n$-th place, we conlcude that $$a_i = (k-i)^n\text{.}$$

Thus, by inclusion-exclusion prinicple, we have

$$|(A_1 \cup \cdots \cup A_k)^c| = k^n -\sum_{i = 1}^k (-1)^{i+1} {k\choose i}a_i = \sum_{i=1}^k (-1)^i{k\choose i} (k-i)^n\text{,}$$ which can be simplified to $$|(A_1 \cup \cdots \cup A_k)^c| = \sum_{i=0}^k (-1)^{i}{k\choose i} (k-i)^n\text{.}$$

Answer 2

The answer is $$\binom{n}{k}k!$$ Indeed there are $\binom{n}{k}$ ways to choose the $k$ places among the $n$ available ones and for each such choice you can lodge your $k$ numbers in $k!$ ways in the $k$ elected places.

Edit
This is an answer to a previous version of the question, which in my interpretation meant that you couldn't repeat numbers nor have two different numbers in one place.