Define a matching problem to be the following:1) n numbered boxes and n numbered cards2) you have to place all the cards. No empty boxes and no left behind cards are allowed.So you end up with a permutation of length n. The number of possible permutations being n!Let X be the variable of x matching places in an ordering.Only 1 permutation is correct. So P ( X = n ) = 1 n ! I would like to calculate P ( X = 2 ), P ( X = 3 ) and so on. P ( X = 1 ) = 0 obviously...

Question

Define a matching problem to be the following:1) n numbered boxes and n numbered cards2) you have to place all the cards. No empty boxes and no left behind cards are allowed.So you end up with a permutation of length n. The number of possible permutations being n!Let X be the variable of x matching places in an ordering.Only 1 permutation is correct. So   P  (  X  =  n  )  =      1          n      !      I would like to calculate   P  (  X  =  2  ),   P  (  X  =  3  ) and so on.  P  (  X  =  1  )  =  0 obviously...

tradirasi · Accepted Answer

First of all, if I understand you correctly,   P  (  X  =  1  )  is not zero! Your X is a well known object, called the number of fixed points of a permutation, namely   X  (  π  )  =#  {  k  ∈  [  n  ]  :  π  (  k  )  =  k  }for any permutation   π  ∈      S    n  . It&#039;s easy to see that the distribution of X is given by  P  (  X  =  k  )  =      1          n      !                      (              n      k                  )            D          n      −      k      where       D    m   is the number permutations of m objects that are derangements, i.e. the number of permutations   π  ∈      S    m  with no fixed points. (This comes from choosing a k subset of [n] to be the fixed points, and then choosing a derangement on the remaining elements.) There are some formulas for       D    m  but I don&#039;t know if there is a simple explicit formula.To get the expectation of X, one can do the following simple expectation computation: note that   X  (  π  )  =      ∑          k      =      1        n    1  {  π  (  k  )  =  k  }so by linearity of expectation,  E  X  =      ∑          k      =      1        n    P  (  Π  (  k  )  =  k  )  =      ∑          k      =      1        n        1    n    =  1.A related fact: for large   n,   P  (  X  =  k  )  ≈      1          e      k      !      , i.e. X is asymptotically Poisson distributed (with rate 1).

Define a matching problem to be the following: 1) n numbered boxes and n numbered cards 2) you hav

Answered question

Answer & Explanation

New Questions in Precalculus