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

  • $\begingroup$ 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? $\endgroup$ – Tohiko Apr 16 '20 at 12:14
  • 1
    $\begingroup$ @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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.