Derangements

AUTHORS:

  • Alasdair McAndrew (2010-05): Initial version
  • Travis Scrimshaw (2013-03-30): Put derangements into category framework
sage.combinat.derangements.Derangement

A derangement.

A derangement on a set \(S\) is a permutation \(\sigma\) such that \(\sigma(x) \neq x\) for all \(x \in S\), i.e. \(\sigma\) is a permutation of \(S\) with no fixed points.

EXAMPLES:

sage: D = Derangements(4)
sage: elt = D([4,3,2,1])
sage: TestSuite(elt).run()
sage.combinat.derangements.Derangements

The class of all derangements of a set or multiset.

A derangement on a set \(S\) is a permutation \(\sigma\) such that \(\sigma(x) \neq x\) for all \(x \in S\), i.e. \(\sigma\) is a permutation of \(S\) with no fixed points.

For an integer, or a list or string with all elements distinct, the derangements are obtained by a standard result described in [BV2004]. For a list or string with repeated elements, the derangements are formed by computing all permutations of the input and discarding all non-derangements.

INPUT:

  • x – Can be an integer which corresponds to derangements of \(\{1, 2, 3, \ldots, x\}\), a list, or a string

REFERENCES:

EXAMPLES:

sage: D1 = Derangements([2,3,4,5])
sage: D1.list()
[[3, 4, 5, 2],
 [5, 4, 2, 3],
 [3, 5, 2, 4],
 [4, 5, 3, 2],
 [4, 2, 5, 3],
 [5, 2, 3, 4],
 [5, 4, 3, 2],
 [4, 5, 2, 3],
 [3, 2, 5, 4]]
sage: D1.cardinality()
9
sage: D1.random_element() # random
[4, 2, 5, 3]
sage: D2 = Derangements([1,2,3,1,2,3])
sage: D2.cardinality()
10
sage: D2.list()
[[2, 1, 1, 3, 3, 2],
 [2, 1, 2, 3, 3, 1],
 [2, 3, 1, 2, 3, 1],
 [2, 3, 1, 3, 1, 2],
 [2, 3, 2, 3, 1, 1],
 [3, 1, 1, 2, 3, 2],
 [3, 1, 2, 2, 3, 1],
 [3, 1, 2, 3, 1, 2],
 [3, 3, 1, 2, 1, 2],
 [3, 3, 2, 2, 1, 1]]
sage: D2.random_element() # random
[2, 3, 1, 3, 1, 2]