Derangements( list )
NrDerangements( list )
Derangements returns the set of all derangements of the list list.
NrDerangements returns the number of derangements of the list list.
A derangement is a fixpointfree permutation of list and is represented by a list that contains exactly the same elements as list, but in such an order that the derangement has at no position the same element as list. If the list list contains no element twice there are exactly |list|! (1/2! - 1/3! + 1/4! - .. (-1)^n/n!) derangements.
Note that the ratio NrPermutationsList([1..n])/NrDerangements([1..n]),
which is n! / (n! (1/2! - 1/3! + 1/4! - .. (-1)^n/n!)) is an
approximation for the base of the natural logarithm e = 2.7182818285,
which is correct to about n digits.
As an example of derangements suppose that you have to send four different letters to four different people. Then a derangement corresponds to a way to send those letters such that no letter reaches the intended person.
gap> Derangements( [1,2,3,4] );
[ [ 2, 1, 4, 3 ], [ 2, 3, 4, 1 ], [ 2, 4, 1, 3 ], [ 3, 1, 4, 2 ],
[ 3, 4, 1, 2 ], [ 3, 4, 2, 1 ], [ 4, 1, 2, 3 ], [ 4, 3, 1, 2 ],
[ 4, 3, 2, 1 ] ]
gap> NrDerangements( [1..10] );
1334961
gap> Int( 10^7*NrPermutationsList([1..10])/last );
27182816
gap> Derangements( [1,1,2,2,3,3] );
[ [ 2, 2, 3, 3, 1, 1 ], [ 2, 3, 1, 3, 1, 2 ], [ 2, 3, 1, 3, 2, 1 ],
[ 2, 3, 3, 1, 1, 2 ], [ 2, 3, 3, 1, 2, 1 ], [ 3, 2, 1, 3, 1, 2 ],
[ 3, 2, 1, 3, 2, 1 ], [ 3, 2, 3, 1, 1, 2 ], [ 3, 2, 3, 1, 2, 1 ],
[ 3, 3, 1, 1, 2, 2 ] ]
gap> NrDerangements( [1,2,2,3,3,3,4,4,4,4] );
338
The function PermutationsList (see PermutationsList) computes all
permutations of a list.
GAP 3.4.4