Derangement

A derangement is a permutation of the elements of a set in which no element appears in its original position, so that, for instance, arranging four labelled letters into four addressed envelopes so that not one letter reaches its correct envelope is a derangement of the four. The number of derangements of a set of a given size, often written with a subfactorial notation, was first studied by the French mathematician Pierre Remond de Montmort in 1708 in connection with a card matching game known as the problem of coincidences, and the problem was later taken up and extended by Leonhard Euler. The number of derangements can be computed from the total number of permutations by an inclusion-exclusion formula, and as the size of the set grows, the fraction of all permutations that are derangements approaches a fixed value, the reciprocal of Euler's number, a striking early appearance of that constant in a purely combinatorial setting.