# 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.

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$$.

• Thanks. I didn't know about the inclusion-exclusion formula. Could you please expand on the first expression for the fulfilment of $j$ conditions? How did you arrive to that expression? – Tohiko Apr 16 '20 at 12:14
• @Tohiko: To fulfill $j$ particular conditions, we need $j$ unique numbers. The first can have any of $n$ different values, the next any of the remaining $n-1$ different values, and so on, so there are $\frac{n!}{(n-j)!}$ ways to choose the unique numbers. The remaining $k-j$ numbers can each be any of the remaining $n-j$ numbers, so there are $(n-j)^{k-j}$ ways to choose them. – joriki Apr 16 '20 at 12:31

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.