WikiLean Articles · Brain · Recent changes · Proposals · Flags · Stats · About

Diff — Permutation

Revision #2623 → #3742 · back to history

modifiedPermutation as bijection2bfefe418441
FieldFrom #2623To #3742
anchors[{"section":"(Lead)","snippet":"a permutation of a set S is defined as a bijection from S to itself"},{"type":"math_alttext","value":"{\\displaystyle \\sigma (1)=3,\\quad \\sigma (2)=1,\\quad \\sigma (3)=2.}"}]—
modifiedPermutation (3,1,2) as function2b00f96e5920
FieldFrom #2623To #3742
anchors[{"section":"(Lead)","snippet":"the permutation (3, 1, 2) corresponds to the function"},{"type":"math_alttext","value":"{\\displaystyle \\sigma (1)=3,\\quad \\sigma (2)=1,\\quad \\sigma (3)=2.}"}]—
modifiedSymmetric groupc211872a91f5
FieldFrom #2623To #3742
anchors[{"section":"(Lead)","snippet":"The collection of all permutations of a set form a group called the symmetric group of the set"},{"type":"math_alttext","value":"{\\displaystyle \\sigma (1)=3,\\quad \\sigma (2)=1,\\quad \\sigma (3)=2.}"}]—
modifiedPermutation as bijectioncc95b6522e9f
FieldFrom #2623To #3742
anchors[{"section":"Definition","snippet":"A permutation can be defined as a bijection"},{"type":"math_alttext","value":"{\\displaystyle \\sigma :S\\ {\\stackrel {\\sim }{\\longrightarrow }}\\ S.}"}]—
modifiedIdentity permutation96890c9e6495
FieldFrom #2623To #3742
anchors[{"section":"Definition","snippet":"The identity permutation is defined by"},{"type":"math_alttext","value":"{\\displaystyle \\sigma :S\\ {\\stackrel {\\sim }{\\longrightarrow }}\\ S.}"}]—
mathlib.moduleMathlib.GroupTheory.Perm.BasicMathlib.Algebra.Group.End
modifiedSymmetric group structure1b66c38c1b2b
FieldFrom #2623To #3742
anchors[{"section":"Definition","snippet":"The set of all permutations of a set with n elements forms the symmetric group"},{"type":"math_alttext","value":"{\\displaystyle \\pi (i)=\\sigma (\\tau (i)).}"}]—
modifiedComposition not commutative5c1afccb6c42
FieldFrom #2623To #3742
anchors[{"section":"Definition","snippet":"composition of two permutations is not commutative"},{"type":"math_alttext","value":"{\\displaystyle \\pi (i)=\\sigma (\\tau (i)).}"}]—
modifiedDisjoint cycles commutee8537d8fd8ba
FieldFrom #2623To #3742
anchors[{"section":"Cycle notation","snippet":"While permutations in general do not commute, disjoint cycles do"},{"type":"math_alttext","value":"{\\displaystyle \\sigma =(126)(35)(4)=(126)(35).}"},{"type":"math_alttext","value":"{\\displaystyle \\kappa _{1}=(126)=(126)(3)(4)(5),\\quad \\kappa _{2}=(35)=(35)(1)(2)(4)(6).}"},{"type":"math_alttext","value":"{\\displaystyle \\sigma =(126)(35)=(35)(126).}"},{"type":"math_alttext","value":"{\\displaystyle \\sigma =(126)(35)=(261)(53).}"}]—
modifiedInverse via reversing cyclesc9e33d40509b
FieldFrom #2623To #3742
anchors[{"section":"Cycle notation","snippet":"inverting the permutation is given by reversing the order of the elements in each cycle"},{"type":"math_alttext","value":"{\\displaystyle \\sigma ^{-1}=\\left({\\vphantom {A^{2}}}(126)(35)\\right)^{-1}=(621)(53).}"}]—
addedComposition is associative707a6febfc54
addedEach permutation has an inversed344f5b2362c
modifiedk-permutation of n7175445e9501
FieldFrom #2623To #3742
anchors[{"section":"k -permutations of n","snippet":"means an ordered arrangement (list) of a k -element subset of an n -set"},{"type":"math_alttext","value":"{\\displaystyle P(n,k)=\\underbrace {n\\cdot (n-1)\\cdot (n-2)\\cdots (n-k+1)} _{k\\ \\mathrm {factors} },}"}]—
modifiedNumber of k-permutations6bb7d2888c9b
FieldFrom #2623To #3742
anchors[{"section":"k -permutations of n","snippet":"The number of such k -permutations"},{"type":"math_alttext","value":"{\\displaystyle P(n,k)=\\underbrace {n\\cdot (n-1)\\cdot (n-2)\\cdots (n-k+1)} _{k\\ \\mathrm {factors} },}"}]—
modifiedPochhammer / falling factorial60e17a1475d3
FieldFrom #2623To #3742
anchors[{"section":"k -permutations of n","snippet":"it is known as the Pochhammer symbol"},{"type":"math_alttext","value":"{\\displaystyle P(n,k)={_{n}}P_{k}=(n)_{k}=n^{\\underline {k}}.}"}]—
modifiedk-combination4c41626dc4dd
FieldFrom #2623To #3742
anchors[{"section":"k -permutations of n","snippet":"a k-combination of a set S is a k- element (unordered) subset of S"},{"type":"math_alttext","value":"{\\displaystyle C(n,k)={\\frac {P(n,k)}{P(k,k)}}={\\frac {n^{\\underline {k}}}{k!}}={\\frac {n!}{(n-k)!\\,k!}}.}"}]—
modifiedRelation of combinations to permutations20b68a1e815e
FieldFrom #2623To #3742
anchors[{"section":"k -permutations of n","snippet":"The number of k -combinations of an n -set"},{"type":"math_alttext","value":"{\\displaystyle C(n,k)={\\frac {P(n,k)}{P(k,k)}}={\\frac {n^{\\underline {k}}}{k!}}={\\frac {n!}{(n-k)!\\,k!}}.}"}]—
modifiedBinomial coefficients1c6d071a5d33
FieldFrom #2623To #3742
anchors[{"section":"k -permutations of n","snippet":"These numbers are also known as binomial coefficients"},{"type":"math_alttext","value":"{\\displaystyle C(n,k)={_{n}}C_{k}={\\binom {n}{k}}.}"}]—
modifiedMultiset permutation356bd595aad1
FieldFrom #2623To #3742
anchors[{"section":"Permutations of multisets","snippet":"a multiset permutation is an ordered arrangement of elements of M"},{"type":"math_alttext","value":"{\\displaystyle {n \\choose m_{1},m_{2},\\ldots ,m_{l}}={\\frac {n!}{m_{1}!\\,m_{2}!\\,\\cdots \\,m_{l}!}}={\\frac {\\left(\\sum _{i=1}^{l}{m_{i}}\\right)!}{\\prod _{i=1}^{l}{m_{i}!}}}.}"},{"type":"math_alttext","value":"{\\displaystyle {\\frac {11!}{1!\\,4!\\,4!\\,2!}}=34650.}"}]—
modifiedMultinomial count of multiset permutations1513a7b6159f
FieldFrom #2623To #3742
anchors[{"section":"Permutations of multisets","snippet":"the number of multiset permutations of M is given by a multinomial coefficient"},{"type":"math_alttext","value":"{\\displaystyle {n \\choose m_{1},m_{2},\\ldots ,m_{l}}={\\frac {n!}{m_{1}!\\,m_{2}!\\,\\cdots \\,m_{l}!}}={\\frac {\\left(\\sum _{i=1}^{l}{m_{i}}\\right)!}{\\prod _{i=1}^{l}{m_{i}!}}}.}"},{"type":"math_alttext","value":"{\\displaystyle {\\frac {11!}{1!\\,4!\\,4!\\,2!}}=34650.}"}]—
mathlib.declMultiset.countPermsNat.multinomial
note`Multiset.countPerms` is defined as the multinomial coefficient, but its equality to the cardinality of distinct arrangements is not established.`Nat.multinomial` defines the multinomial coefficient, but its equality to the cardinality of distinct arrangements of a multiset is not established.
provenanceaiai-moderated
modifiedAnagrams of MISSISSIPPI220083dd98c7
FieldFrom #2623To #3742
anchors[{"section":"Permutations of multisets","snippet":"the number of distinct anagrams of the word MISSISSIPPI is"},{"type":"math_alttext","value":"{\\displaystyle {n \\choose m_{1},m_{2},\\ldots ,m_{l}}={\\frac {n!}{m_{1}!\\,m_{2}!\\,\\cdots \\,m_{l}!}}={\\frac {\\left(\\sum _{i=1}^{l}{m_{i}}\\right)!}{\\prod _{i=1}^{l}{m_{i}!}}}.}"},{"type":"math_alttext","value":"{\\displaystyle {\\frac {11!}{1!\\,4!\\,4!\\,2!}}=34650.}"}]—
modifiedMISSISSIPPI generating function283fd11ed1e0
FieldFrom #2623To #3742
anchors[{"section":"Permutations of multisets","snippet":"in the case of the multiset of letters in MISSISSIPPI"},{"type":"math_alttext","value":"{\\displaystyle {\\begin{aligned}&(1+x)\\cdot (1+x+x^{2}/2)\\cdot (1+x+x^{2}/2+x^{3}/6+x^{4}/24)^{2}=\\\\&1+4x+{\\frac {15}{2!}}x^{2}+{\\frac {53}{3!}}x^{3}+{\\frac {176}{4!}}x^{4}+{\\frac {550}{5!}}x^{5}+{\\frac {1610}{6!}}x^{6}+{\\frac {4340}{7!}}x^{7}+{\\frac {10430}{8!}}x^{8}+{\\frac {21420}{9!}}x^{9}+{\\frac {34650}{10!}}x^{10}+{\\frac {34650}{11!}}x^{11}.\\end{aligned}}}"}]—
addedCycle type is a partition of n3f64b18db14a
addedCycle type preserved by conjugation09fc54c9d3a9
addedSign is multiplicative8d81eefc2140
modifiedPermutation matrixc493b4de1879
FieldFrom #2623To #3742
anchors[{"section":"Matrix representation","snippet":"A permutation matrix is an n × n matrix"},{"type":"math_alttext","value":"{\\displaystyle M_{\\sigma }M_{\\tau }=M_{\\sigma \\tau }.}"},{"type":"math_alttext","value":"{\\displaystyle M_{\\sigma }M_{\\tau }={\\begin{pmatrix}0&1&0\\\\1&0&0\\\\0&0&1\\end{pmatrix}}{\\begin{pmatrix}0&0&1\\\\1&0&0\\\\0&1&0\\end{pmatrix}}={\\begin{pmatrix}1&0&0\\\\0&0&1\\\\0&1&0\\end{pmatrix}}=M_{\\sigma \\tau }.}"}]—
modifiedMatrix construction respects composition0b4fa216eed3
FieldFrom #2623To #3742
anchors[{"section":"Matrix representation","snippet":"this construction is compatible with composition of permutations"},{"type":"math_alttext","value":"{\\displaystyle M_{\\sigma }M_{\\tau }=M_{\\sigma \\tau }.}"},{"type":"math_alttext","value":"{\\displaystyle M_{\\sigma }M_{\\tau }={\\begin{pmatrix}0&1&0\\\\1&0&0\\\\0&0&1\\end{pmatrix}}{\\begin{pmatrix}0&0&1\\\\1&0&0\\\\0&1&0\\end{pmatrix}}={\\begin{pmatrix}1&0&0\\\\0&0&1\\\\0&1&0\\end{pmatrix}}=M_{\\sigma \\tau }.}"}]—
modifiedProduct of permutation matrices632ebef5ba9a
FieldFrom #2623To #3742
anchors[{"section":"Matrix representation","snippet":"For example, the one-line permutations"},{"type":"math_alttext","value":"{\\displaystyle M_{\\sigma }M_{\\tau }=M_{\\sigma \\tau }.}"},{"type":"math_alttext","value":"{\\displaystyle M_{\\sigma }M_{\\tau }={\\begin{pmatrix}0&1&0\\\\1&0&0\\\\0&0&1\\end{pmatrix}}{\\begin{pmatrix}0&0&1\\\\1&0&0\\\\0&1&0\\end{pmatrix}}={\\begin{pmatrix}1&0&0\\\\0&0&1\\\\0&1&0\\end{pmatrix}}=M_{\\sigma \\tau }.}"}]—
modifiedFoata's fundamental bijection7a2024a6e30c
FieldFrom #2623To #3742
anchors[{"section":"Foata's transition lemma","snippet":"Foata 's fundamental bijection transforms a permutation"},{"type":"math_alttext","value":"{\\displaystyle \\sigma =(513)(6)(827)(94)={\\begin{pmatrix}1&2&3&4&5&6&7&8&9\\\\3&7&5&9&1&6&8&2&4\\end{pmatrix}},}"}]—
modifiedRecords equal cycles9d6907dd8a6d
FieldFrom #2623To #3742
anchors[{"section":"Foata's transition lemma","snippet":"the number of n -permutations with exactly k records is equal to the number of n -permutations with exactly k cycles"},{"type":"math_alttext","value":"{\\displaystyle {\\begin{array}{l|l}{\\hat {\\sigma }}=f(\\sigma )&\\sigma =f^{-1}({\\hat {\\sigma }})\\\\\\hline \\mathbf {123} =(\\,1\\,)(\\,2\\,)(\\,3\\,)&123=\\mathbf {(\\,1\\,)(\\,2\\,)(\\,3\\,)} \\\\\\mathbf {132} =(\\,1\\,)(\\,3\\,2\\,)&132=\\mathbf {(\\,1\\,)(\\,3\\,2\\,)} \\\\\\mathbf {213} =(\\,2\\,1\\,)(\\,3\\,)&213=\\mathbf {(\\,2\\,1\\,)(\\,3\\,)} \\\\\\mathbf {231} =(\\,3\\,1\\,2\\,)&321=\\mathbf {(\\,2\\,)(\\,3\\,1\\,)} \\\\\\mathbf {312} =(\\,3\\,2\\,1\\,)&231=\\mathbf {(\\,3\\,1\\,2\\,)} \\\\\\mathbf {321} =(\\,2\\,)(\\,3\\,1\\,)&312=\\mathbf {(\\,3\\,2\\,1\\,)} \\end{array}}}"}]—
modifiedFoata maps weak exceedances to ascents6d7a3691d844
FieldFrom #2623To #3742
anchors[{"section":"Foata's transition lemma","snippet":"Foata's mapping takes an n -permutation with k weak exceedances to an n -permutation with k − 1 ascents"},{"type":"math_alttext","value":"{\\displaystyle {\\begin{array}{l|l}{\\hat {\\sigma }}=f(\\sigma )&\\sigma =f^{-1}({\\hat {\\sigma }})\\\\\\hline \\mathbf {123} =(\\,1\\,)(\\,2\\,)(\\,3\\,)&123=\\mathbf {(\\,1\\,)(\\,2\\,)(\\,3\\,)} \\\\\\mathbf {132} =(\\,1\\,)(\\,3\\,2\\,)&132=\\mathbf {(\\,1\\,)(\\,3\\,2\\,)} \\\\\\mathbf {213} =(\\,2\\,1\\,)(\\,3\\,)&213=\\mathbf {(\\,2\\,1\\,)(\\,3\\,)} \\\\\\mathbf {231} =(\\,3\\,1\\,2\\,)&321=\\mathbf {(\\,2\\,)(\\,3\\,1\\,)} \\\\\\mathbf {312} =(\\,3\\,2\\,1\\,)&231=\\mathbf {(\\,3\\,1\\,2\\,)} \\\\\\mathbf {321} =(\\,2\\,)(\\,3\\,1\\,)&312=\\mathbf {(\\,3\\,2\\,1\\,)} \\end{array}}}"}]—
addedBruhat order3134b43c43d6
modifiedKobayashi enumeration formula7eac56ed8ada
FieldFrom #2623To #3742
anchors[{"section":"Inversions","snippet":"Kobayashi (2011) proved the enumeration formula"},{"type":"math_alttext","value":"{\\displaystyle \\sum _{i<j,\\sigma (i)>\\sigma (j)}(\\sigma (i)-\\sigma (j))=|\\{\\tau \\in S_{n}\\mid \\tau \\leq \\sigma ,\\tau {\\text{ is bigrassmannian}}\\}}"}]—
addedFactorial number systemcaa05e92603d
addedFisher–Yates shuffle727525fc14af
addedHeap's algorithm13285e3f2df8