Permutation

A name from the enumeratio catalogue with no kernel of its own yet; this page carries its crosswalk only.

The singular-inhabitant constructor for a permutation, as a one-line word.

WikipediaPermutation↗Derangementvia Derangements↗Involution (mathematics)via Involutions↗MathWorldPermutation↗WikidataQ161519↗Encyclopedia of MathematicsPermutation↗nLabpermutation↗Britannicatopic/permutation↗OEISWolfram LanguageQFactorialvia Permutations↗Subfactorialvia Derangements↗StirlingS1via KCyclePermutations↗SageMathSymPygenerate_bellvia Permutations↗generate_derangementsvia Derangements↗generate_involutionsvia Involutions↗mathlib4Equiv.Perm (Fin n)via Permutations↗derangements (Fin n)via Derangements↗Nat.stirlingFirstvia KCyclePermutations↗MATLABpermsvia Permutations↗

Permutation(list)The singular-inhabitant constructor for a permutation, as a one-line word.

Typed signatures

Type	Package	Applies
((list<integer>) -> permutation) & ((cycle_decomposition) -> permutation) & ((subexcedant_seq) -> permutation)	combinatorics	always

Domain: Collections·Drawn as Graphics

Statistics

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

• AntiexcedancesSt000703Positions with p(i) < i.
• AscentsSt000245Positions i with p(i) < p(i+1).
• CycleCountThe number of cycles in the disjoint-cycle decomposition.
• CyclicDescentsDescents of p read cyclically, counting position n when p(n) > p(1).
• DenertSum of the excedance positions, plus the inversions within each of the excedance and non-excedance subwords.
• DepthSt000029Half the total displacement, (1/2) * sum |p(i) - i|.
• DescentsSt000021Positions i with p(i) > p(i+1).
• DistinctCycleLengthsHow many distinct cycle sizes occur.
• ExcedancesSt000155Positions with p(i) > i.
• FirstDescentThe smallest descent position, or 0 when p is increasing.
• FixedPointsSt000022Positions with p(i) = i.
• InversionsSt000018Pairs i < j with p(i) > p(j).
• LargestCycleLengthSt000485The size of the largest cycle.
• LargestRunLengthThe length of the longest increasing run (the catalog's second spelling of LongestRun).
• LastDescentSt000653The largest descent position, or 0 when p is increasing.
• LeftToRightMaximaSt000314Positions larger than everything before them.
• LeftToRightMinimaSt000542Positions smaller than everything before them.
• LongestCycleLengthSt000485The size of the largest cycle (the catalog's second spelling).
• LongestDecreasingSubsequenceThe length of a longest decreasing subsequence.
• LongestIncreasingSubsequenceSt000062The length of a longest increasing subsequence.
• LongestRunThe length of the longest run of consecutive increases.
• MajorIndexSt000004The SUM of the descent positions — not their count.
• MinorIndexThe sum of the ascent positions (the comajor index).
• OccurrencesOf123St000002Triples i < j < k with p(i) < p(j) < p(k).
• OccurrencesOf132St000220Triples i < j < k with p(i) < p(k) < p(j).
• OccurrencesOf213Triples i < j < k with p(j) < p(i) < p(k).
• PeaksSt000023Interior positions with p(i-1) < p(i) > p(i+1).
• PermutationLengthThe number of points p moves.
• PermutationMaxThe largest point p moves; 0 for the identity.
• PermutationMinThe smallest point p moves; infinity for the identity.
• PermutationOrderSt000058The order of p in the symmetric group — the lcm of its cycle lengths.
• PermutationSupportThe points p moves, in increasing order.
• ReflectionLengthSt000216n minus the number of cycles — the minimum number of transpositions.
• RightToLeftMaximaSt000007Positions larger than everything after them.
• RightToLeftMinimaSt000991Positions smaller than everything after them.
• RunsSt000325St000470Maximal increasing runs — one more than the number of descents.
• SignSt000037The sign of p: +1 when the inversion count is even, -1 when odd.
• StackSortable1 when p avoids the pattern 231, 0 otherwise — exactly the stack-sortable permutations.
• ThreeCycleCountCycles of size exactly three.
• TwoCycleCountCycles of size exactly two.
• ValleysSt000353Interior positions with p(i-1) > p(i) < p(i+1).
• WeakExceedancesSt000213Positions with p(i) >= i.

Maps

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

From Permutation

• BinarySearchTreePermutation → BinaryTreeSurjectionGraded 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.
• 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.
• CycleDecompositionPermutation → CycleDecompositioninverseA permutation in cycle notation, fixed points kept: each cycle from its least point, cycles in order of those points.
• CyclePartitionPermutation → SetPartitionSurjectionGraded mapMp00151The orbits, as a set partition of the positions.
• CycleTypePermutation → IntegerPartitionSurjectionGraded mapMp00108The multiset of cycle lengths, as a partition.
• CyclicShiftPermutation → PermutationinverseBijectionGraded mapMp00279Rotate the word one place to the left.
• DescentCompositionPermutation → CompositionSurjectionGraded mapMp00071The composition of n cut at the descent positions.
• DescentSetPermutation → FinsetThe positions where the word falls.
• FoataPermutation → PermutationBijectionGraded mapMp00087Foata's fundamental bijection: cycles rotated to their max, ordered by increasing max, parentheses erased.
• 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.
• KnuthClassRepresentativePermutation → PermutationidempotentThe row reading word of σ's RSK insertion tableau — the canonical word of its Knuth (plactic) class.
• KrewerasComplementPermutation → PermutationBijectionGraded mapMp00088w⁻¹c, for w below the long cycle c = (1 2 ... n) in absolute order.
• 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 → StandardTableauSurjectionGraded mapMp00059The insertion tableau of the RSK correspondence.
• RskRecordingPermutation → StandardTableauSurjectionGraded mapMp00070The recording tableau of the RSK correspondence, as its rows.
• RskShapePermutation → IntegerPartitionSurjectionGraded mapMp00060The common shape of the RSK tableaux: the row lengths, as a partition of n.
• 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).

To Permutation

• PermutationCycleDecomposition → PermutationinverseThe permutation a cycle decomposition describes.
• PermutationSubexcedantSeq → PermutationinverseThe permutation a subexcedant sequence is the inversion sequence of.
• ToPermutationStandardTableauPair → PermutationThe permutation an RSK pair comes from: inverse RSK.

68 more in FindStat, not implemented here

• Mp00002AlternatingSignMatrix → PermutationSurjectionGraded mapto left key permutation
• Mp00014BinaryTree → PermutationInjectionGraded mapto 132-avoiding permutation
• Mp00017BinaryTree → PermutationInjectionGraded mapto 312-avoiding permutation
• Mp00023DyckPath → PermutationInjectionGraded mapto non-crossing permutation
• Mp00024DyckPath → PermutationInjectionGraded mapto 321-avoiding permutation
• Mp00025DyckPath → PermutationInjectionGraded mapto 132-avoiding permutation
• Mp00031DyckPath → PermutationInjectionGraded mapto 312-avoiding permutation
• Mp00053ParkingFunction → PermutationSurjectionGraded mapto car permutation
• Mp00055ParkingFunction → PermutationSurjectionGraded mapto labelling permutation
• Mp00058PerfectMatching → PermutationInjectionGraded mapto permutation
• Mp00061Permutation → BinaryTreeSurjectionGraded mapto increasing tree
• Mp00062Permutation → PermutationBijectionGraded mapLehmer-code to major-code bijection
• Mp00063Permutation → AlternatingSignMatrixInjectionGraded mapto alternating sign matrix
• Mp00065Permutation → PosetsGraded mappermutation poset
• Mp00067Permutation → PermutationBijectionGraded mapFoata bijection
• Mp00068Permutation → PermutationIdempotentGraded mapSimion-Schmidt map
• Mp00073Permutation → PermutationBijectionGraded mapmajor-index to inversion-number bijection
• Mp00075SemistandardTableau → PermutationGraded mapreading word permutation
• Mp00080SetPartition → PermutationInjectionGraded mapto permutation
• Mp00081StandardTableau → PermutationInjectionGraded mapreading word permutation
• Mp00086Permutation → PermutationBijectionGraded mapfirst fundamental transformation
• Mp00089Permutation → PermutationBijectionGraded mapInverse Kreweras complement
• Mp00090Permutation → PermutationGraded mapcycle-as-one-line notation
• Mp00109Permutation → BinaryWordSurjectionGraded mapdescent word
• Mp00114Permutation → BinaryWordSurjectionGraded mapconnectivity set
• Mp00119DyckPath → PermutationInjectionGraded mapto 321-avoiding permutation (Krattenthaler)
• Mp00126Permutation → PermutationBijectionGraded mapInvolutioncactus evacuation
• Mp00127Permutation → DyckPathSurjectionGraded mapleft-to-right-maxima to Dyck path
• Mp00129DyckPath → PermutationInjectionGraded mapto 321-avoiding permutation (Billey-Jockusch-Stanley)
• Mp00130Permutation → BinaryWordSurjectionGraded mapdescent tops
• Mp00131Permutation → BinaryWordSurjectionGraded mapdescent bottoms
• Mp00149Permutation → PermutationBijectionGraded mapLehmer code rotation
• Mp00159Permutation → PermutationGraded mapDemazure product with inverse
• Mp00160Permutation → GraphsGraded mapgraph of inversions
• Mp00163SignedPermutation → PermutationSurjectionGraded mappermutation
• Mp00170Permutation → SignedPermutationInjectionGraded mapto signed permutation
• Mp00175Permutation → PermutationBijectionGraded mapinverse Foata bijection
• Mp00201DyckPath → PermutationInjectionGraded mapRingel
• Mp00204Permutation → IntegerPartitionSurjectionGraded mapLLPS
• Mp00208Permutation → Latticeslattice of intervals
• Mp00209Permutation → Posetspattern poset
• Mp00223Permutation → PermutationIdempotentGraded maprunsort
• 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
• Mp00240Permutation → SetPartitionSurjectionGraded mapweak exceedance partition
• Mp00241Permutation → PermutationBijectionGraded mapInvolutioninvert Laguerre heap
• Mp00245SignedPermutation → PermutationSurjectionGraded mapstandardize
• Mp00248Permutation → CompositionGraded mapDEX composition
• Mp00252Permutation → PermutationSurjectionrestriction
• Mp00253DecoratedPermutation → PermutationSurjectionGraded mappermutation
• Mp00254Permutation → PermutationIdempotentInverse fireworks map
• Mp00255DecoratedPermutation → PermutationGraded maplower permutation
• Mp00256DecoratedPermutation → PermutationGraded mapupper permutation
• Mp00257Permutation → PermutationBijectionGraded mapInvolutionAlexandersson Kebede
• Mp00265Permutation → PermutationBijectionGraded mapconjugation by long cycle
• Mp00277Permutation → PermutationGraded mapcatalanization
• Mp00283PerfectMatching → PermutationInjectionGraded mapnon-nesting-exceedence permutation
• Mp00286SetComposition → PermutationSurjectionGraded mapto permutation
• Mp00305Permutation → ParkingFunctionInjectionGraded mapparking function
• Mp00309Permutation → PermutationBijectionGraded mapinverse toric promotion
• Mp00310Permutation → PermutationBijectionGraded maptoric promotion
• Mp00325Permutation → PermutationBijectionGraded mapones to leading
• Mp00326Permutation → PermutationBijectionGraded mapweak order rowmotion
• Mp00329Permutation → PermutationBijectionTanimoto
• Mp00336BinaryWord → PermutationGraded mapstandard permutation

Examples

Basic #

A permutation as its one-line word, held as written

live ↗

In${\operatorname{Permutation}}([2, 3, 1])$Out${\operatorname{Permutation}}([2, 3, 1])$

About

Examples	1
Checked against	SymPy 1 agree
Crosswalk	Wikipedia ×3MathWorldWikidataEncyclopedia of MathematicsnLabBritannicaOEIS ×17Wolfram Language ×3SageMath ×16SymPy ×3mathlib4 ×3MATLAB