# Factorielle de n
# = nombre de permutations de n objets
def factorielle(n)
  r=1
  for i in 2..n : r=r*i end
  return r
end

# Nombre de combinaisons de p objets parmi n
def combinaisons(n,p)
  return factorielle(n)/factorielle(p)/factorielle(n-p)
end

# Nombre de dérangements de n objets 
# = nombre de permutations de n objets ne laissant 
#   aucun objet à sa place
def derangements(n)
  return 1 if n<=0
  return n*derangements(n-1)+(-1)**n
end

# Nombre de permutations de n objets laissant k objets 
# exactement à leur place
def derangements_enplace(n,k)
  return combinaisons(n,k)*derangements(n-k)
end

# Nombre de permutations de n objets laissant au plus
# k objets à leur place
def derangements_auplus(n,k)
  r=derangements(n)
  for i in 1..k 
    r=r+derangements_enplace(n,i) 
  end
  return r
end