TOPICS
Search

Partial Derangement


A partial derangment is a permutation of n distinct, ordered items in which none of the items is in its original ordered position is known as a derangement. If some, but not necessarily all, of the items are not in their original ordered positions, the configuration can be referred to as a partial derangement (Evans et al. 2002, p. 385).

Among the n! possible permutations of n distinct items, examine the number R(n,k) of these permutations in which exactly k items are in their original ordered positions. 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

Here is a table of the number of partial derangements R(n,n-k) for n=0, 1, ..., 8:

 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).

Finding a partial derangement is sometimes known as the recontres problem, and the numbers in a triangle of numbers in a partial derangeament are called recontres numbers.


See also

Derangement

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.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:

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

Subject classifications