Permutation with max repetition of a single element

639 Views Asked by At

I have 16 cells that must be filled with a single number $m$ where $0<=m<=15$. Only one number is allowed to be used twice, but that doesn't mean that it must be used twice, this means that all the cells can be different. Examples:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 $ok$

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 $ok$

0 1 2 3 4 5 6 7 8 9 10 11 12 0 13 0 not valid, there's a number repeated 3 times

0 1 2 3 4 5 6 7 8 9 10 11 12 0 13 13 not valid, only one number can be repeated twice

I think all the possible outcomes are: $$16!+{16!\over{2!}}$$ Which is basically the possible outcomes when they are all different plus the possible outcomes when there's a repetition. Is it right?

1

There are 1 best solutions below

4
On BEST ANSWER

1) As you say, there are $16!$ possibilities if the numbers are all different.

2) If one digit is repeated, there are 16 ways to choose the digit to be repeated, $\binom{16}{2}$ ways to choose the places for these digits, and then $P(15,14)=15!$ ways to fill the remaining cells.

This gives a total of $16!+16\cdot15!\cdot\binom{16}{2}=16!\big(1+120\big)=16!\cdot121$ choices.