4
$\begingroup$

Determine the number of permutations of $ \ \{1,2,3,4,5,6,7,8,9,10\} \ $ that have exactly 3 numbers in their natural position. $$ $$ Is it $ \ \ \begin{pmatrix} 10 \\ 3 \end{pmatrix} \times 7 ! \ $ ?

$\endgroup$
  • $\begingroup$ The answer is no, because some of those $7!$ orderings will put additional numbers in their natural position. $\endgroup$ – vadim123 Apr 18 '17 at 18:44
2
$\begingroup$

No, because $7!$ allows for extra elements to be in their natural position. After the $3$ fixed position items are selected, you need a derangement of the remaining $7$ items.

$\endgroup$
1
$\begingroup$

You need choose $3$ elements that stay on their positions in $\binom{10}{3} = 120$ and multiply it by the number $!7$ of permutations of special kind called derangement on remaining $7$ elements. There are many ways to compute number $!k$ (see link), particularly it is known to be equal to $\frac{k!}{e}$ rounded to the nearest integer. Therefore $\frac{5040}{e} \approx 1854 =\,!7$ and the desired number of permutations on $10!$ elements keeping exactly $3$ of them in place is $\binom{10}{3} \cdot\,!7 = 120 \cdot 1854 = 222\,480$.


Another way to compute number of such permutation is inclusion-exclusion principle. There are $\binom{10}{3}\cdot 7!$ ways to select $3$ elements to stay in place and permute all remaining. But for each of $\binom{10}{4}$ ways to select $4$ elements each permutation that keeps them in place was computed $4$ times, but should not be computed at all. Continuing these thoughts we get that the right number of desired permutations is $$\binom{10}{3}\cdot 7! - \binom{10}{4} \cdot 6! \cdot \binom{4}{3} + \binom{10}{5} \cdot 5! \cdot \binom{5}{3} - \binom{10}{6} \cdot 4! \cdot \binom{6}{3}\\ + \binom{10}{7} \cdot 3! \cdot \binom{7}{3} - \binom{10}{8} \cdot 2! \cdot \binom{8}{3} + \binom{10}{9} \cdot 1! \cdot \binom{9}{3} - \binom{10}{10} \cdot 0! \cdot \binom{10}{3}\\ = 604800 - 604800 + 302400 - 100800 + 25200 - 5040 + 840 - 120 = 222480.$$

$\endgroup$
0
$\begingroup$

$\binom{n}{3}[!(n-3)]$ where $n=10$ and $$!k = k! \sum_{i=0}^k \frac{(-1)^i}{i!}$$.

$\endgroup$
0
$\begingroup$

No. The number of permutations in $S_{10}$ which have exactly $3$ fixed points is ${10 \choose 3} \times D_7$, where $D_7$ denotes the number of permutations of a $7$-element set which contain no fixed points (the number $D_7$ of derangements in $S_7$ can be computed using the principle of inclusion-exclusion).

$\endgroup$

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.