Let n be a positive integer. Find the number of permutations of ( 1 , 2 , . . . , n ) such that no number remains in its original place.Solution: To do this, first we are going to count the number of permutations where at least one number remains in its place, according to the inclusion-exclusion principle, we must first add the permutations where a given number is fixed, then subtract the permutations where 2 given numbers are fixed and so on.To find a permutation that fixes k given elements, we only have to arrange the rest, which can be done in ( n − k ) ! ways. However, if we do this for every choice of k elements, we are counting ( n k ) ( n − k ) ! = n ! k ! permutations. Since in total there are n ! permutations we get as our result: n ! − ( n ! 1 ! + n ! 2 ! − n ! 3 ! + . . . + ( − 1 ) n + 1 n ! n ! ) I'm a bit confused about a point of the solution, when we fix k elements and rearrange the other n − k, some of the remaining elements will stay fixed in their position right? so why does this work?

Question

Let n be a positive integer. Find the number of permutations of   (  1  ,  2  ,  .  .  .  ,  n  ) such that no number remains in its original place.Solution: To do this, first we are going to count the number of permutations where at least one number remains in its place, according to the inclusion-exclusion principle, we must first add the permutations where a given number is fixed, then subtract the permutations where 2 given numbers are fixed and so on.To find a permutation that fixes   k given elements, we only have to arrange the rest, which can be done in   (  n  −  k  )  ! ways. However, if we do this for every choice of   k elements, we are counting                               (                            n        k                              )                      (  n  −  k  )  !  =            n      !              k      !       permutations. Since in total there are   n  ! permutations we get as our result:  n  !  −      (                  n        !                    1        !              +                  n        !                    2        !              −                  n        !                    3        !              +    .    .    .    +    (    −    1          )              n        +        1                            n        !                    n        !              )  I&#039;m a bit confused about a point of the solution, when we fix   k elements and rearrange the other   n  −  k, some of the remaining elements will stay fixed in their position right? so why does this work?

Leroy Lowery · Accepted Answer

Your confusion seems to be with the inclusion-exclusion principle in itself: when we say that       |    A  ∪  B      |    =      |    A      |    +      |    B      |    −      |    A  ∩  B      |   it is precisely because   A and   B have some elements in common, those of   A  ∩  B, and we are counting them twice, once in       |    A      |   and again in       |    B      |  . In your problem it is the same, you look first at those permutations which have at least one fixed element, so you continue with the inclusion-exclusion principle until you take into account all the ``common elements&#039;&#039;.

Let n be a positive integer. Find the number of permutations of ( 1 , 2 , . .

Answered question

Answer & Explanation

New Questions in High school probability