I have $1,2,\ldots, n$ numbers and I want pick $k$ of them with replacement and such that order matters.
So for $n=10$ and $k=4$ I can get: $(1,2,2,4), (1,2,4,2), (1,2,3,10)$,…etc
I then have $n^k$ possible combinations. But now I only want to count the tuples which have a unique number. So $(1,2,2,4)$ and $(1,1,1,2)$ would be included but $(1,1,2,2)$ would not be included since both 1 and 2 are not unique? How do I count these?
I figured that I can pick a number out of $n$ for the first element in my tuple and then the remaining $k-1$ elements out of the remaining $n-1$ numbers, so the number of combinations would be $n\,(n-1)^{k-1}$. Since I have $k$ possible locations for the unique number I get $k\, n\, (n-1)^{k-1}$. However, clearly I am counting some combinations multiple times and I am not sure how to discount them.
Best Answer
You can do this using inclusion–exclusion.
There are $k$ conditions, one for each of the $k$ positions containing a unique number. Any $j$ particular conditions can be fulfilled in
$$ \frac{n!}{(n-j)!}(n-j)^{k-j} $$
different ways (which for $j=1$ is your expression for one particular condition). Thus, by inclusion–exclusion the number of ways to fulfill at least one of the conditions is
$$ \sum_{j=1}^k(-1)^{j+1}\binom kj\frac{n!}{(n-j)!}(n-j)^{k-j}\;. $$
For $n=10$ and $k=4$, this is
$$ \sum_{j=1}^4(-1)^{j+1}\binom4j\frac{10!}{(10-j)!}(10-j)^{4-j}=9720\;. $$
Of course, for this particular small case we could have counted more easily that there are $\binom42\binom{10}2=270$ tuples with two pairs and $10$ with four identical entries, for a count of $10^4-270-10=9720$.