Derangements

If n letters are placed randomly into n envelopes (with address), what is the expected number of envelopes with the correct letter inside?

Before addressing that, let’s look at a derangement problem. It is the probability of no match. For n items, it is the number of derangements divided by the number of permutations.

!n/n! = (n!/e)/n! ~ 1/e = 0.37

Let’s do a Monte Carlo and see what we get

itr <- 100000

let_env <- replicate(itr, {
  
  n <- 100
  
  env <- seq(1:n)
  let <- sample(seq(1:n), n, replace = FALSE, prob = rep(1/n, n))

  counter <- 0
for (i in 1:n) {
  if(env[i] == let[i]){
    counter <- counter + 1
  }else{
    counter <- counter 
  }
}

  if(counter == 1) {
    sounder <- 1  
  }else{
    sounder <- 0
  }
  

})

mean(let_env)

0.36827

So what about the original question of the expected number?

itr <- 100000

let_env <- replicate(itr, {
  
  n <- 100
  #env <- sample(seq(1:n), n, replace = FALSE, prob = rep(1/n, n))
  env <- seq(1:n)
  let <- sample(seq(1:n), n, replace = FALSE, prob = rep(1/n, n))

  counter <- 0
for (i in 1:n) {
  if(env[i] == let[i]){
    counter <- counter + 1
  }else{
    counter <- counter 
  }
}
  
 counter 
})

mean(let_env)

 1.00014