TOPICS
Search

Partial Derangement


A partial derangement is a permutation of distinct items with a specified number of fixed points, generalizing a derangement, which has none (Evans et al. 2002, p. 385).

Let R(n,k) count the permutations of n distinct items with exactly k items in their original positions, where n is a nonnegative integer and 0<=k<=n. These counts include the cases in which all or none of the items remain in place. Then

R(n,n)=1
(1)
R(n,n-1)=0
(2)
R(n,k)=(n; k)!(n-k),
(3)

where (n; k) is a binomial coefficient and !(n-k) is the subfactorial. The second identity assumes n>=1. The counts R(n,k) are called rencontres numbers. In particular, R(n,0)=!n is the subfactorial, and the name rencontres numbers is also used for this one-parameter sequence.

The following table lists R(n,n-k) for n=0, 1, ..., 8, with k running from 0 to n in each row:

 1
1,0
1,0,1
1,0,3,2
1,0,6,8,9
1,0,10,20,45,44
1,0,15,40,135,264,265
1,0,21,70,315,924,1855,1854
1,0,28,112,630,2464,7420,14832,14833
(4)

(OEIS A098825).

The enumeration of permutations by their number of fixed points is known as the rencontres problem.


See also

Derangement, Discordant Permutation, Permutation, Subfactorial

Portions of this entry contributed by Gerald Del Fiacco

Explore with Wolfram|Alpha

References

Evans, C. D. H.; Hughes, J.; and Houston, J. "Significance-Testing the Validity of Idiographic Methods: A Little Derangement Goes a Long Way." Brit. J. Math. Stat. Psych. 55, 385-390, 2002. https://doi.org/10.1348/000711002760554525.Pitman, J. "Some Probabilistic Aspects of Set Partitions." Amer. Math. Monthly 104, 201-209, 1997.Riordan, J. An Introduction to Combinatorial Analysis. New York: Wiley, pp. 57-58 and 65, 1980.Skiena, S. "Derangements." §1.4.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 33-34, 1990.Sloane, N. J. A. Sequence A098825 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Partial Derangement

Cite this as:

Weisstein, Eric W., with contributions by Gerald Del Fiacco. "Partial Derangement." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PartialDerangement.html

Subject classifications