About permutation with repeated identical elements.

Question

First up, I do know the general solution but somehow am unable to use it to solve this kind of problem. I am simply lost. The problem is like this:

How many r arrangements of n items are possible with k identical elements?

Had it been simply

How many r arrangements of n items are possible?

the answer is nPr.

Had it been simply

How many arrangements of n items are possible with k identical elements?

the answer is n!/k! (There could be any j number of k's, in which case, as I said, I know the formula is n!/(ki!*k2!...kj!))

However, I am lost how to use that to solve the problem when r and k are involved.

Answer 1

You have to split into cases depending on the number of "identical items" that are chosen. I will call these $k$ identical items "marked", and the distinct $n - k$ items "unmarked".

We try to find the number of $r$ arrangements with $i$ marked items. First, there will be $r - i$ unmarked items and $i$ marked items. There are $$ \binom{n - k}{r - i} $$ ways to pick $r - i$ unmarked items. There's only one way to pick $i$ marked items. With these $r$ items in hand, we can permute them. The number of permutations is $$ \frac{r!}{i!}. $$ Therefore, the number of $r$ arrangements with $i$ marked items is $$ \binom{n - k}{r - i} \frac{r!}{i!}. $$

Add these values up for all $i$ going from $0$ to $k$ to get the final answer: $$ \sum_{i=0}^k \binom{n - k}{r - i} \frac{r!}{i!}. $$

I'm not sure if this can be simplified...

Answer 2

Tunococ explanations are perfect, but as it depends whether the amount of repeated elements k is below or not r; we should have: $$ \sum_{i=0}^{min(r, k)} \binom{n - k}{r - i} \frac{r!}{i!}. $$