# Derangements#

AUTHORS:

• Alasdair McAndrew (2010-05): Initial version

• Travis Scrimshaw (2013-03-30): Put derangements into category framework

class sage.combinat.derangements.Derangement(parent, *args, **kwds)[source]#

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

>>> from sage.all import *
>>> D = Derangements(Integer(4))
>>> elt = D([Integer(4),Integer(3),Integer(2),Integer(1)])
>>> TestSuite(elt).run()

to_permutation()[source]#

Return the permutation corresponding to self.

EXAMPLES:

sage: D = Derangements(4)
sage: p = D([4,3,2,1]).to_permutation(); p
[4, 3, 2, 1]
sage: type(p)
<class 'sage.combinat.permutation.StandardPermutations_all_with_category.element_class'>
sage: D = Derangements([1, 3, 3, 4])
sage: D[0].to_permutation()
Traceback (most recent call last):
...
ValueError: can only convert to a permutation for derangements of [1, 2, ..., n]

>>> from sage.all import *
>>> D = Derangements(Integer(4))
>>> p = D([Integer(4),Integer(3),Integer(2),Integer(1)]).to_permutation(); p
[4, 3, 2, 1]
>>> type(p)
<class 'sage.combinat.permutation.StandardPermutations_all_with_category.element_class'>
>>> D = Derangements([Integer(1), Integer(3), Integer(3), Integer(4)])
>>> D[Integer(0)].to_permutation()
Traceback (most recent call last):
...
ValueError: can only convert to a permutation for derangements of [1, 2, ..., n]

class sage.combinat.derangements.Derangements(x)[source]#

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]

>>> from sage.all import *
>>> D1 = Derangements([Integer(2),Integer(3),Integer(4),Integer(5)])
>>> 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]]
>>> D1.cardinality()
9
>>> D1.random_element() # random
[4, 2, 5, 3]
>>> D2 = Derangements([Integer(1),Integer(2),Integer(3),Integer(1),Integer(2),Integer(3)])
>>> D2.cardinality()
10
>>> 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]]
>>> D2.random_element() # random
[2, 3, 1, 3, 1, 2]

Element[source]#

alias of Derangement

cardinality()[source]#

Counts the number of derangements of a positive integer, a list, or a string. The list or string may contain repeated elements. If an integer $$n$$ is given, the value returned is the number of derangements of $$[1, 2, 3, \ldots, n]$$.

For an integer, or a list or string with all elements distinct, the value is obtained by the standard result $$D_2 = 1, D_3 = 2, D_n = (n-1) (D_{n-1} + D_{n-2})$$.

For a list or string with repeated elements, the number of derangements is computed by Macmahon’s theorem. If the numbers of repeated elements are $$a_1, a_2, \ldots, a_k$$ then the number of derangements is given by the coefficient of $$x_1 x_2 \cdots x_k$$ in the expansion of $$\prod_{i=0}^k (S - s_i)^{a_i}$$ where $$S = x_1 + x_2 + \cdots + x_k$$.

EXAMPLES:

sage: D = Derangements(5)
sage: D.cardinality()
44
sage: D = Derangements([1,44,918,67,254])
sage: D.cardinality()
44
sage: D = Derangements(['A','AT','CAT','CATS','CARTS'])
sage: D.cardinality()
44
sage: D.cardinality()
481066515734
sage: D = Derangements([1,1,2,2,3,3])
sage: D.cardinality()
10
sage: D = Derangements('SATTAS')
sage: D.cardinality()
10
sage: D = Derangements([1,1,2,2,2])
sage: D.cardinality()
0

>>> from sage.all import *
>>> D = Derangements(Integer(5))
>>> D.cardinality()
44
>>> D = Derangements([Integer(1),Integer(44),Integer(918),Integer(67),Integer(254)])
>>> D.cardinality()
44
>>> D = Derangements(['A','AT','CAT','CATS','CARTS'])
>>> D.cardinality()
44
>>> D.cardinality()
481066515734
>>> D = Derangements([Integer(1),Integer(1),Integer(2),Integer(2),Integer(3),Integer(3)])
>>> D.cardinality()
10
>>> D = Derangements('SATTAS')
>>> D.cardinality()
10
>>> D = Derangements([Integer(1),Integer(1),Integer(2),Integer(2),Integer(2)])
>>> D.cardinality()
0

random_element()[source]#

Produce all derangements of a positive integer, a list, or a string. The list or string may contain repeated elements. If an integer $$n$$ is given, then a random derangements of $$[1, 2, 3, \ldots, n]$$ is returned

For an integer, or a list or string with all elements distinct, the value is obtained by an algorithm described in [MPP2008]. For a list or string with repeated elements the derangement is formed by choosing an element at random from the list of all possible derangements.

OUTPUT:

A single list or string containing a derangement, or an empty list if there are no derangements.

EXAMPLES:

sage: D = Derangements(4)
sage: D.random_element() # random
[2, 3, 4, 1]
sage: D = Derangements(['A','AT','CAT','CATS','CARTS','CARETS'])
sage: D.random_element() # random
['AT', 'CARTS', 'A', 'CAT', 'CARETS', 'CATS']
sage: D.random_element() # random
['C', 'U', 'I', 'H', 'O', 'G', 'N', 'B', 'E', 'L', 'A', 'R', 'P', 'Y', 'T']
sage: D = Derangements([1,1,1,1,2,2,2,2,3,3,3,3])
sage: D.random_element() # random
[3, 2, 2, 3, 1, 3, 1, 3, 2, 1, 1, 2]
sage: D = Derangements('ESSENCES')
sage: D.random_element() # random
['N', 'E', 'E', 'C', 'S', 'S', 'S', 'E']
sage: D = Derangements([1,1,2,2,2])
sage: D.random_element()
[]

>>> from sage.all import *
>>> D = Derangements(Integer(4))
>>> D.random_element() # random
[2, 3, 4, 1]
>>> D = Derangements(['A','AT','CAT','CATS','CARTS','CARETS'])
>>> D.random_element() # random
['AT', 'CARTS', 'A', 'CAT', 'CARETS', 'CATS']