notatio

Derangements ​

The permutations of {1,…,n}\{1, \dots, n\} with no fixed point.

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaDerangementMathWorldDerangementWikidataQ1207920Encyclopedia of MathematicsDerangementBritannicatopic/derangementOEISA000166✓A257953✓A260091✓A260115✓A260216✓Wolfram LanguageSubfactorialSageMathDerangements(n)SymPygenerate_derangementsmathlib4derangements (Fin n)
Derangements(n)the fixed-point-free permutations of nn elements
CombinatoricaDerangements[Range[n]]
Typed signatures
TypePackageApplies
(integer<0..>) -> indexed_collection<permutation>combinatoricsalways

Domain: Combinatorial collections

Details

Definition

Epsil, as the implementation runs it.

count(_n)

Apply((prefix: list<integer>) => Apply((filled: integer) => Apply(
                                                                   (taken: list<integer>) => Apply(
                                                                                                    (m: integer) => Fold(Function(dsum +
                                                                                                                                  (-1) ^ di *
                                                                                                                                  Binomial(m, di) *
                                                                                                                                  (_n - filled -
                                                                                                                                   di)!, dsum, di), 0, Range(0, m, 1)),
                                                                                                    Fold(
                                                                                                          Function(dm +
                                                                                                                   (0 if taken[dp] != 0 else 1), dm, dp),
                                                                                                          0,
                                                                                                          Range(filled + 1, _n, 1),
                                                                                                        ),
                                                                                                  ) if Fold(
                                                                                                            Function(ok &&
                                                                                                                     prefix[dq] != dq, ok, dq),
                                                                                                            True,
                                                                                                            Range(1, filled, 1),
                                                                                                          ) else 0,
                                                                   Map(
                                                                        Function(0, lr_t0),
                                                                        Range(1, _n, 1),
                                                                      ),
                                                                 ), 0), Map(
                                                                            Function(0, lr_y),
                                                                            Range(1, _n, 1),
                                                                          ))

unrank(_n, _r)

Take(Fold(
           Function(Apply((lr_tk: list<integer>) => Apply(
                                                           (lr_chosen: list<integer>) => ReplaceAt(
                                                                                                    ReplaceAt(
                                                                                                               ReplaceAt(lr_s, lr_j, lr_chosen[2]),
                                                                                                               _n + 1,
                                                                                                               lr_chosen[1],
                                                                                                             ),
                                                                                                    _n + 1 + lr_chosen[2],
                                                                                                    lr_j,
                                                                                                  ),
                                                           Fold(
                                                                 Function(lr_pick if lr_pick[2] != 0 else lr_pick if lr_s[_n + 1 + lr_v] !=
                                                                                                                     0 else Apply(
                                                                                                                                  (lr_c: integer) => [lr_pick[1], lr_v] if lr_pick[1] < lr_c else [lr_pick[1] - lr_c, 0],
                                                                                                                                  Apply(
                                                                                                                                         (prefix: list<integer>) => Apply((filled: integer) => Apply((taken: list<integer>) => Apply(
                                                                                                                                                                                                                                      (m: integer) => Fold(Function(dsum +
                                                                                                                                                                                                                                                                    (-1) ^ di *
                                                                                                                                                                                                                                                                    Binomial(m, di) *
                                                                                                                                                                                                                                                                    (_n - filled -
                                                                                                                                                                                                                                                                     di)!, dsum, di), 0, Range(0, m, 1)),
                                                                                                                                                                                                                                      Fold(Function(dm +
                                                                                                                                                                                                                                                    (0 if taken[dp] != 0 else 1), dm, dp), 0, Range(filled + 1, _n, 1)),
                                                                                                                                                                                                                                    ) if Fold(Function(ok &&
                                                                                                                                                                                                                                                      prefix[dq] != dq, ok, dq), True, Range(1, filled, 1)) else 0, ReplaceAt(lr_tk, lr_v, lr_j)), lr_j),
                                                                                                                                         ReplaceAt(lr_s, lr_j, lr_v),
                                                                                                                                       ),
                                                                                                                                ), lr_pick, lr_v),
                                                                 [
                                                                   lr_s[_n + 1],
                                                                   0,
                                                                 ],
                                                                 Range(1, _n, 1),
                                                               ),
                                                         ), Take(
                                                                 Drop(
                                                                       lr_s,
                                                                       _n + 1,
                                                                     ),
                                                                 _n,
                                                               )), lr_s, lr_j),
           Join(
                 Map(Function(0, lr_y), Range(1, _n, 1)),
                 [_r],
                 Map(Function(0, lr_y2), Range(1, _n, 1)),
               ),
           Range(1, _n, 1),
         ), _n)

rank(_n, _x)

Apply(
       (lr_where: list<integer>) => Fold(Function(lr_r + Apply(
                                                                (lr_base: list<integer>) => Apply(
                                                                                                   (lr_tk: list<integer>) => Fold(Function(lr_r2 +
                                                                                                                                           (Apply(
                                                                                                                                                   (prefix: list<integer>) => Apply((filled: integer) => Apply((taken: list<integer>) => Apply(
                                                                                                                                                                                                                                                (m: integer) => Fold(Function(dsum +
                                                                                                                                                                                                                                                                              (-1) ^ di *
                                                                                                                                                                                                                                                                              Binomial(m, di) *
                                                                                                                                                                                                                                                                              (_n - filled -
                                                                                                                                                                                                                                                                               di)!, dsum, di), 0, Range(0, m, 1)),
                                                                                                                                                                                                                                                Fold(Function(dm +
                                                                                                                                                                                                                                                              (0 if taken[dp] != 0 else 1), dm, dp), 0, Range(filled + 1, _n, 1)),
                                                                                                                                                                                                                                              ) if Fold(Function(ok &&
                                                                                                                                                                                                                                                                prefix[dq] != dq, ok, dq), True, Range(1, filled, 1)) else 0, ReplaceAt(lr_tk, lr_v, lr_j)), lr_j),
                                                                                                                                                   ReplaceAt(lr_base, lr_j, lr_v),
                                                                                                                                                 ) if lr_where[lr_v] > lr_j else 0), lr_r2, lr_v), 0, Range(1, _x[lr_j] - 1, 1)),
                                                                                                   Map(
                                                                                                        Function(lr_where[lr_u] if lr_where[lr_u] < lr_j else 0, lr_u),
                                                                                                        Range(1, _n, 1),
                                                                                                      ),
                                                                                                 ),
                                                                Map(
                                                                     Function(
                                                                               _x[lr_q] if lr_q < lr_j else 0,
                                                                               lr_q,
                                                                             ),
                                                                     Range(
                                                                            1,
                                                                            _n,
                                                                            1,
                                                                          ),
                                                                   ),
                                                              ), lr_r, lr_j), 0, Range(1, _n, 1)),
       Fold(
             Function(ReplaceAt(lr_at, _x[lr_p], lr_p), lr_at, lr_p),
             Map(Function(0, lr_y3), Range(1, _n, 1)),
             Range(1, _n, 1),
           ),
     )

valid(_n, _x)

(Apply((prefix: list<integer>) => Apply((filled: integer) => Apply(
                                                                    (taken: list<integer>) => Apply(
                                                                                                     (m: integer) => Fold(Function(dsum +
                                                                                                                                   (-1) ^ di *
                                                                                                                                   Binomial(m, di) *
                                                                                                                                   (_n - filled -
                                                                                                                                    di)!, dsum, di), 0, Range(0, m, 1)),
                                                                                                     Fold(
                                                                                                           Function(dm +
                                                                                                                    (0 if taken[dp] != 0 else 1), dm, dp),
                                                                                                           0,
                                                                                                           Range(filled + 1, _n, 1),
                                                                                                         ),
                                                                                                   ) if Fold(
                                                                                                             Function(ok &&
                                                                                                                      prefix[dq] != dq, ok, dq),
                                                                                                             True,
                                                                                                             Range(1, filled, 1),
                                                                                                           ) else 0,
                                                                    Fold(
                                                                          Function(
                                                                                    ReplaceAt(lr_iv, _x[lr_ip], lr_ip),
                                                                                    lr_iv,
                                                                                    lr_ip,
                                                                                  ),
                                                                          Map(
                                                                               Function(0, lr_t1),
                                                                               Range(1, _n, 1),
                                                                             ),
                                                                          Range(1, _n, 1),
                                                                        ),
                                                                  ), _n), _x) ==
 1 if Fold(Function(
                    (ReplaceAt(lr_d_seen, _x[lr_d_j], 1) if lr_d_seen[_x[lr_d_j]] ==
                                                            0 else ReplaceAt(
                                                                             lr_d_seen,
                                                                             _n +
                                                                             1,
                                                                             1,
                                                                           )) if 1 <= _x[lr_d_j] &&
                                                                                _x[lr_d_j] <= _n else ReplaceAt(lr_d_seen, _n + 1, 1),
                    lr_d_seen,
                    lr_d_j,
                  ), Map(Function(0, lr_d_z), Range(1, _n + 1, 1)), Range(
                                                                          1,
                                                                          _n,
                                                                          1,
                                                                        ))[_n + 1] ==
     0 else False) if Length(_x) == _n else False

Statistics

On Permutation, called as CombinatorialStat(x, "Name").

Maps

Into and out of Permutation, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.

From Permutation

  • BinarySearchTreePermutation → BinaryTreesurjectionSurjectionGraded mapMp00072The tree built by inserting σ(1), σ(2), ... into an empty binary search tree.
  • BinarySearchTreeParentArrayPermutation → BinaryTreeParentArrayThe binary search tree of σ as its parent array: entry v is the value v is inserted under, 0 for the root.
  • CactusEvacuationPermutation → PermutationinvolutionBijectionGraded mapInvolutionMp00126The permutation with the same insertion tableau and the evacuation of the recording tableau.
  • ComplementPermutation → PermutationinvolutionBijectionGraded mapInvolutionMp00069Each entry replaced by n + 1 minus itself.
  • ConjugacyClassRepresentativePermutation → PermutationidempotentThe canonical permutation with the same cycle type.
  • ConjugateAfterCycleTypePermutation → IntegerPartitionThe conjugate partition of the cycle type.
  • ConnectivityWordPermutation → BinaryWordsurjectionSurjectionGraded mapMp00114Letter i is 1 when the first i entries are all smaller than the rest: the connectivity set as a binary word.
  • CycleAsOneLineNotationPermutation → PermutationGraded mapMp00090The cycles, each written from its least point and in order of those points, read as one word.
  • CycleDecompositionPermutation → CycleDecompositioninverseA permutation in cycle notation, fixed points kept: each cycle from its least point, cycles in order of those points.
  • CyclePartitionPermutation → SetPartitionsurjectionSurjectionGraded mapMp00151The orbits, as a set partition of the positions.
  • CycleTypePermutation → IntegerPartitionsurjectionSurjectionGraded mapMp00108The multiset of cycle lengths, as a partition.
  • CyclicShiftPermutation → PermutationinverseBijectionGraded mapMp00279Rotate the word one place to the left.
  • DescentBottomWordPermutation → BinaryWordsurjectionSurjectionGraded mapMp00131Letter v is 1 when value v is a descent bottom: some larger value immediately precedes it.
  • DescentCompositionPermutation → IntegerCompositionsurjectionSurjectionGraded mapMp00071The composition of n cut at the descent positions.
  • DescentSetPermutation → FinsetThe positions where the word falls.
  • DescentTopWordPermutation → BinaryWordsurjectionSurjectionGraded mapMp00130Letter v - 1 is 1 when value v is a descent top: some smaller value immediately follows it.
  • DescentWordPermutation → BinaryWordsurjectionSurjectionGraded mapMp00109Letter i is 1 when the word falls between positions i and i + 1: the descent set as a binary word.
  • FoataPermutation → PermutationbijectionBijectionGraded mapMp00087Foata's fundamental bijection: cycles rotated to their max, ordered by increasing max, parentheses erased.
  • FoataInversionsToMajorPermutation → PermutationbijectioninverseBijectionGraded mapMp00175The inverse of Foata's major-to-inversions bijection: peel off the last letter, rotate the blocks of the rest back.
  • FoataMajorToInversionsPermutation → PermutationbijectioninverseBijectionGraded mapMp00067Foata's bijection: each letter is put on the end of the image so far, which is cut into blocks, and every block is rotated one place right.
  • FromPermutationPermutation → IncreasingBinaryTreeThe increasing binary tree built by minimum-splitting recursion: the position of the smallest value roots the tree, everything before it recurses to the left, everything after it to the right.
  • InversePermutation → PermutationinvolutionBijectionGraded mapInvolutionMp00066The inverse permutation: position of each value.
  • InverseAfterComplementAfterReversePermutation → PermutationReverse, then complement, then invert.
  • InverseCyclicShiftPermutation → PermutationinverseRotate the word one place to the right.
  • InverseFoataPermutation → PermutationbijectioninverseBijectionGraded mapMp00086The permutation whose cycles are the stretches of the word between successive left-to-right maxima, each read as a cycle.
  • InverseKrewerasComplementPermutation → PermutationbijectioninverseBijectionGraded mapMp00089cπ⁻¹ with the long cycle c = (1 2 ... n), FindStat's order: position i holds π⁻¹(c(i)).
  • InverseToricPromotionPermutation → PermutationbijectioninverseBijectionGraded mapMp00309The same swaps as ToricPromotion in the opposite order: n and 1, then n - 1 and n, down to 1 and 2.
  • KnuthClassRepresentativePermutation → PermutationidempotentThe row reading word of σ's RSK insertion tableau — the canonical word of its Knuth (plactic) class.
  • KrewerasComplementPermutation → PermutationbijectionBijectionGraded mapMp00088π⁻¹c with the long cycle c = (1 2 ... n), FindStat's order: position i holds c(π⁻¹(i)).
  • LeftToRightMaximaDyckPathPermutation → DyckPathsurjectionSurjectionGraded mapMp00127The Dyck path whose rises climb to each left-to-right maximum and whose falls run to the next one.
  • LehmerCodeRotationPermutation → PermutationbijectionBijectionGraded mapMp00149The permutation whose Lehmer code is this one's with every entry one larger, cyclically.
  • LehmerCodeToMajorCodePermutation → PermutationbijectioninverseBijectionGraded mapMp00062The permutation whose major code is this permutation's Lehmer code.
  • LongCycleConjugationPermutation → PermutationbijectionBijectionGraded mapMp00265Conjugation by the long cycle (1 2 ... n): each cycle's entries shifted up by one, cyclically.
  • MajorCodeToLehmerCodePermutation → PermutationbijectioninverseBijectionGraded mapMp00073The permutation whose Lehmer code is this permutation's major code.
  • PeakSetPermutation → FinsetThe interior positions that rise then fall.
  • PermutahedronVertexPermutation → FinsetThe vertex (σ(1), …, σ(n)), or its Loday point, is an ordered tuple of coordinates, while finset is an unordered set of positions (the carrier DescentSet and PeakSet use). Reordering the coordinates gives a different vertex but the same finset, so the map would not be injective. A finset-valued PermutahedronVertex is a type mismatch, not a gap to close.
  • ReversePermutation → PermutationinvolutionBijectionGraded mapInvolutionMp00064The word read backwards.
  • ReverseComplementPermutation → PermutationinvolutionReverse, then complement.
  • RskPermutation → StandardTableauPairThe RSK correspondence: the insertion and recording tableaux, as a pair.
  • RskInsertionPermutation → StandardTableausurjectionSurjectionGraded mapMp00059The insertion tableau of the RSK correspondence.
  • RskRecordingPermutation → StandardTableausurjectionSurjectionGraded mapMp00070The recording tableau of the RSK correspondence, as its rows.
  • RskShapePermutation → IntegerPartitionsurjectionSurjectionGraded mapMp00060The common shape of the RSK tableaux: the row lengths, as a partition of n.
  • RunSortPermutation → PermutationidempotentIdempotentGraded mapMp00223The permutation with its increasing runs sorted lexicographically.
  • SignedPermutationPermutation → SignedPermutationInjectionGraded mapMp00170A permutation as the signed permutation with every sign positive.
  • SimionSchmidtPermutation → PermutationidempotentIdempotentGraded mapMp00068The left-to-right minima stay in place and the other positions take the remaining values, largest first: a 123-avoiding permutation.
  • SubexcedantSeqPermutation → SubexcedantSeqinverseEntry i counts the earlier entries larger than p(i): the permutation's inversion sequence.
  • ToLehmerCodePermutation → PermutationInversionEntry i counts the later entries smaller than p(i).
  • ToricPromotionPermutation → PermutationbijectioninverseBijectionGraded mapMp00310Toric promotion of the path graph: swap the values 1 and 2, then 2 and 3, and so on up to n and 1, each swap skipped when the two values sit next to each other.
  • WeakExceedancePartitionPermutation → SetPartitionSurjectionGraded mapMp00240The coarsest set partition containing every arc from i to π(i) with i ≤ π(i).

To Permutation

  • Avoiding132PermutationDyckPath → PermutationInjectionGraded mapMp00025The 132-avoiding permutation of Krattenthaler's bijection, built from the path's area sequence read from the end.
  • Avoiding312PermutationDyckPath → PermutationInjectionGraded mapMp00031The 312-avoiding permutation of Bandlow and Killpatrick: from the identity, each area-sequence entry swaps neighbouring positions that many times.
  • Avoiding321PermutationDyckPath → PermutationInjectionGraded mapMp00024The 321-avoiding permutation whose RSK pair is the pair of two-row tableaux read off the first and last halves of the path.
  • BilleyJockuschStanleyPermutationDyckPath → PermutationInjectionGraded mapMp00129The 321-avoiding permutation with entry (ups through a valley) + 1 at the position of its downs through that valley: the Billey-Jockusch-Stanley bijection.
  • BlockConcatenationSetComposition → PermutationsurjectionSurjectionGraded mapMp00286The permutation that lists the blocks in order, each sorted increasingly.
  • CarPermutationParkingFunction → PermutationSurjectionGraded mapMp00053Spot j holds the car that parks there, each car taking the first free spot at or after its preference.
  • IncreasingCyclePermutationSetPartition → PermutationInjectionGraded mapMp00080The permutation whose cycles are the blocks, each cycle increasing: every element goes to the next larger in its block, the largest to the least.
  • KrattenthalerPermutationDyckPath → PermutationInjectionGraded mapMp00119The 321-avoiding permutation whose left-to-right maxima are the path's peaks: Krattenthaler's bijection.
  • LabelingPermutationParkingFunction → PermutationSurjectionGraded mapMp00055The labeling of the parking function's support Dyck path: the positions of the entries, smallest entry first and equal entries left to right.
  • NoncrossingPermutationDyckPath → PermutationInjectionGraded mapMp00023The noncrossing permutation Stump's bijection gives the path: the cycles of its touch points, peeled off round by round.
  • PermutationCycleDecomposition → PermutationinverseThe permutation a cycle decomposition describes.
  • PermutationSubexcedantSeq → PermutationinverseThe permutation a subexcedant sequence is the inversion sequence of.
  • ReadingWordStandardTableau → PermutationInjectionGraded mapMp00081The rows read left to right, from the bottom row up, as a permutation.
  • RingelDyckPath → PermutationInjectionGraded mapMp00201The Ringel permutation of the Nakayama algebra whose Kupisch series the path gives, one size up.
  • StandardizationSignedPermutation → PermutationsurjectionSurjectionGraded mapMp00245The permutation of the same relative order, taking 1 < … < n < −n < … < −1.
  • StandardPermutationBinaryWord → PermutationGraded mapMp00336The permutation ranking the letters of the word, equal letters from left to right.
  • ToPermutationStandardTableauPair → PermutationinverseThe permutation an RSK pair comes from: inverse RSK.
  • UnderlyingPermutationSignedPermutation → PermutationsurjectionSurjectionGraded mapMp00163The permutation left when the signs are forgotten.
32 more in FindStat, not implemented here
  • Mp00002AlternatingSignMatrix → PermutationSurjectionGraded mapto left key permutation
  • Mp00014BinaryTree → PermutationInjectionGraded mapto 132-avoiding permutation
  • Mp00017BinaryTree → PermutationInjectionGraded mapto 312-avoiding permutation
  • Mp00058PerfectMatching → PermutationInjectionGraded mapto permutation
  • Mp00061Permutation → BinaryTreeSurjectionGraded mapto increasing tree
  • Mp00063Permutation → AlternatingSignMatrixInjectionGraded mapto alternating sign matrix
  • Mp00065Permutation → PosetsGraded mappermutation poset
  • Mp00075SemistandardTableau → PermutationGraded mapreading word permutation
  • Mp00159Permutation → PermutationGraded mapDemazure product with inverse
  • Mp00160Permutation → LabeledGraphGraded mapgraph of inversions
  • Mp00204Permutation → IntegerPartitionSurjectionGraded mapLLPS
  • Mp00208Permutation → Latticeslattice of intervals
  • Mp00209Permutation → Posetspattern poset
  • Mp00235Permutation → PermutationBijectionGraded mapdescent views to invisible inversion bottoms
  • Mp00236Permutation → PermutationBijectionGraded mapClarke-Steingrimsson-Zeng inverse
  • Mp00237Permutation → PermutationBijectionGraded mapdescent views to invisible inversion bottoms
  • Mp00238Permutation → PermutationBijectionGraded mapClarke-Steingrimsson-Zeng
  • Mp00239Permutation → PermutationBijectionGraded mapInvolutionCorteel
  • Mp00241Permutation → PermutationBijectionGraded mapInvolutioninvert Laguerre heap
  • Mp00248Permutation → IntegerCompositionGraded mapDEX composition
  • Mp00252Permutation → PermutationSurjectionrestriction
  • Mp00253DecoratedPermutation → PermutationSurjectionGraded mappermutation
  • Mp00254Permutation → PermutationIdempotentInverse fireworks map
  • Mp00255DecoratedPermutation → PermutationGraded maplower permutation
  • Mp00256DecoratedPermutation → PermutationGraded mapupper permutation
  • Mp00257Permutation → PermutationBijectionGraded mapInvolutionAlexandersson Kebede
  • Mp00277Permutation → PermutationGraded mapcatalanization
  • Mp00283PerfectMatching → PermutationInjectionGraded mapnon-nesting-exceedence permutation
  • Mp00305Permutation → ParkingFunctionInjectionGraded mapparking function
  • Mp00325Permutation → PermutationBijectionGraded mapones to leading
  • Mp00326Permutation → PermutationBijectionGraded mapweak order rowmotion
  • Mp00329Permutation → PermutationBijectionTanimoto

Enumeration

Examples

Basic #

!4!4

live ↗
InCount(Derangements(4))\mathrm{Count}(\mathrm{Derangements}(4))Out99
Statistics #

derangements of 5 by cycles: a 5-cycle, or a 3-cycle and a 2-cycle

live ↗
InTally(CombinatorialStat(Derangements(5),CycleCount))\mathrm{Tally}(\mathrm{CombinatorialStat}(\mathrm{Derangements}(5), \text{CycleCount}))OutTuple⁡([2,1],[20,24])\operatorname{Tuple}(\bigl\lbrack2, 1\bigr\rbrack,\bigl\lbrack20, 24\bigr\rbrack)
About
Examples2
Checked againstCombinatorica 1 agreemathlib4 1 agree
CrosswalkWikipediaMathWorldWikidataEncyclopedia of MathematicsBritannicaOEIS ×5Wolfram LanguageCombinatoricaSageMathSymPymathlib4

Implementation

mappedcombinatoricapackages/oracle/src/mappings.ts

Combinatorica lists the derangements of a permutation; ours are those of 1..n.

mappedmathlib4packages/oracle/src/mappings.ts

Mathlib's derangements of Fin n, each as a 1-based one-line list, in lexicographic order

See also: SymmetricGroup, Involutions, Subfactorial