Number of combination with a unique number 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.
 A: 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$.
A: For $j=1,\dots,n$ let $A_{j}$ denote the set of tuples that have
$j$ as unique number.
Then to be found is $\left|A_{1}\cup\cdots\cup A_{n}\right|$ and
for this we can use inclusion/exclusion and symmetry: $$\left|A_{1}\cup\cdots\cup A_{n}\right|=\sum_{j=1}^{n}\binom{n}{j}\left(-1\right)^{j-1}\left|A_{1}\cap\cdots\cap A_{j}\right|$$
Observe that for $j>k$ term $\left|A_{1}\cap\cdots\cap A_{j}\right|$
takes value $0$ so that these terms can be left out.
Further we have: $$\left|A_{1}\cap\cdots\cap A_{j}\right|=\frac{k!}{\left(k-j\right)!}\left(n-j\right)^{k-j}$$
resulting in:
$$\sum_{j=1}^{\min\left(n,k\right)}\binom{n}{j}\left(-1\right)^{j-1}\frac{k!}{\left(k-j\right)!}\left(n-j\right)^{k-j}$$
Also observe that: $$\binom{n}{j}\frac{k!}{(k-j)!}=\binom{k}{j}\frac{n!}{(n-j)!}$$showing that this corresponds with the answer of Joriki.
