This chapter is dedicated to the different sets of permutations with the same properties.
An inversion in a permutation \(\tau=\tau_{1}\ldots\tau_{n}\) is a pair \((i,j)\) such that \(1\leq i<j\leq n\) and \(\tau_{i}>\tau_{j}\) [CJS11].
‣ InversionAut( k ) | ( function ) |
Returns: An automaton that accepts all permutations with exactly k inversions.
The rational language of all permutations with a given number , k, of inversions is computed by InversionAut.
gap> a:=InversionAut(1); < deterministic automaton on 2 letters with 4 states > gap> AutToRatExp(a); a*baa* gap> Spectrum(a); [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ] gap> b:=InversionAut(5); < deterministic automaton on 6 letters with 14 states > gap> AutToRatExp(b); ((a*ba*bUa*c)a*bUa*ba*cUa*d)a*(ba*baa*Ucaaa*)U(a*ba*bUa*c)a*(ca*baa*Udaaaa*)U(\ a*ba*daUa*eaa)a*baa*Ua*ba*(dbUeaa)aaa*U(a*eabUa*(ebUfaa)a)aaa* gap> Spectrum(b); [ 0, 0, 0, 3, 22, 71, 169, 343, 628, 1068, 1717, 2640, 3914, 5629, 7889 ] gap>
‣ InversionAutOfClass( aut, inv ) | ( function ) |
Returns: An automaton accepting all permutations of a class with inv inversions.
InversionAutOfClass intersects the rational pattern class with the rational language containing all permutations under the rank encoding that have exactly inv inversions.
gap> a:=MinimalAutomaton(GraphToAut(Seqstacks(2,2),1,6)); < deterministic automaton on 3 letters with 3 states > gap> Spectrum(a); [ 1, 2, 6, 18, 54, 162, 486, 1458, 4374, 13122, 39366, 118098, 354294, 1062882, 3188646 ] gap> b:=InversionAutOfClass(a,4); < deterministic automaton on 5 letters with 23 states > gap> Spectrum(b); [ 0, 0, 0, 3, 13, 35, 75, 140, 238, 378, 570, 825, 1155, 1573, 2093 ] gap>
‣ PlusDecomposableAut( aut ) | ( function ) |
Returns: An automaton that accepts the subset of the class aut containing the plus-decomposable permutations of aut.
The PlusDecomposableAut automaton accepts the language of all plus-decomposable permutations of the encoded class accepted by aut.
gap> xa:=MinimalAutomaton(GraphToAut(Parstacks(2,2),1,6)); < deterministic automaton on 4 letters with 9 states > gap> Spectrum(xa); [ 1, 2, 6, 23, 89, 345, 1338, 5189, 20122, 78024, 302529, 1172993, 4547973, 17633432, 68368135 ] gap> a:=PlusDecomposableAut(xa); < deterministic automaton on 4 letters with 16 states > gap> Spectrum(a); [ 0, 1, 3, 11, 47, 196, 808, 3306, 13433, 54265, 218145, 873303, 3483654, 13853682, 54945158 ] gap>
‣ PlusIndecomposableAut( aut ) | ( function ) |
Returns: An automaton that accepts all permutations of aut that are not plus-decomposable.
The PlusIndecomposableAutomaton automaton accepts the language of all plus-indecomposable permutations of the encoded class accepted by aut, by rejecting every rank encoding that in the original automaton would have entered and left the accept state before the last letter in the rank encodedpermutation.
gap> xa:=MinimalAutomaton(GraphToAut(Parstacks(2,2),1,6)); < deterministic automaton on 4 letters with 9 states > gap> Spectrum(xa); [ 1, 2, 6, 23, 89, 345, 1338, 5189, 20122, 78024, 302529, 1172993, 4547973, 17633432, 68368135 ] gap> a:=PlusIndecomposableAut(xa); < deterministic automaton on 4 letters with 11 states > gap> Spectrum(a); [ 1, 1, 3, 12, 42, 149, 530, 1883, 6689, 23759, 84384, 299690, 1064319, 3779750, 13422977 ] gap>
‣ MinusDecomposableAut( aut ) | ( function ) |
Returns: An automaton that accepts the subset of the class aut containing the minus-decomposable permutations of aut.
The MinusDecomposableAut automaton accepts the language of all minus-decomposable permutations of the rank encoded class accepted by aut.
gap> xa:=MinimalAutomaton(GraphToAut(Parstacks(2,2),1,6)); < deterministic automaton on 4 letters with 9 states > gap> Spectrum(xa); [ 1, 2, 6, 23, 89, 345, 1338, 5189, 20122, 78024, 302529, 1172993, 4547973, 17633432, 68368135 ] gap> a:=MinusDecomposableAut(xa); < deterministic automaton on 4 letters with 12 states > gap> Spectrum(a); [ 0, 1, 3, 10, 24, 64, 180, 520, 1524, 4504, 13380, 39880, 119124, 356344, 1066980 ] gap>
‣ MinusIndecomposableAut( aut ) | ( function ) |
Returns: An automaton that accepts all permutations of aut that are not minus-decomposable.
The MinusIndecomposableAut automaton accepts the language of all minus-indecomposable permutations of the encoded class accepted by aut, which is the complement set of the set of minus-decomposable permutations within the class.
gap> xa:=MinimalAutomaton(GraphToAut(Parstacks(2,2),1,6)); < deterministic automaton on 4 letters with 9 states > gap> Spectrum(xa); [ 1, 2, 6, 23, 89, 345, 1338, 5189, 20122, 78024, 302529, 1172993, 4547973, 17633432, 68368135 ] gap> a:=MinusIndecomposableAut(xa); < deterministic automaton on 4 letters with 17 states > gap> Spectrum(a); [ 1, 1, 3, 13, 65, 281, 1158, 4669, 18598, 73520, 289149, 1133113, 4428849, 17277088, 67301155 ] gap>
The regular language of all non-simple rank encoded permutations with highest rank \(k\) is described by the following equation,
\[ E(NS_{k}) = E(\Omega_{k}) \cap ( \bigcup_{l=1}^{k-1} P_{l} \bigcup_{m=l}^{k-1} E(\hat{\Omega}_{k-m})^{+m} \cup \bigcup_{j=1}^{k-1} E(\hat{\Omega}_{k-j})^{+j} \cup \]
\[ \cup \bigcup_{a=2}^{k-1} \bigcup_{b=0}^{k-1-a} Q_{a,b} \bigcup_{i=0}^{a-2} (E(\hat{\Omega}_{k-(b+i)})^{+b+i})^{(a-i)} ) \Sigma^{*} \cup E(\mathcal{D}_{P}(\Omega_{k})) \]
where \(\Sigma\) is the alphabet \(\{1,\ldots,k\}\), \(k\in\mathbb{N}\), \(k \geq 3\).
\(P_{l}\) is the language of prefixes of rank encoded permutations, where the prefix ends with the total sum of gap sizes to be equal to \(l\).
\(Q_{i,j}\) is the language of prefixes of rank encoded permutations, where the prefix ends with a gap of size \(i\) and the sum of the sizes of gaps below equals to \(j\).
\(E(\Omega_{k-i})^{+i}\) is the language of \(E(\Omega_{k-i})\) \(i \in \mathbb{N}\), with the alphabet shifted upwards by \(i\).
\(E(\Omega_{k})^{(i)}\) is the sublanguage of \(E(\Omega_{k})\) containing the words of length \(\leq i\), \(i \in \mathbb{N}\).
\(E(\hat{\Omega}_{k})\) is the sublanguage of \(E(\Omega_{k})\) excluding the words of length \(\leq 1\).
\(E(\mathcal{D}_{P}(\Omega_{k}))\) is the language of all plus-decomposable permutations as described in [HL13].
‣ LengthBoundAut( aut, min, i, k ) | ( function ) |
Returns: The subautomaton of aut that accepts words between (and including) the lengths min and i.
We are taking the automaton aut and it's alphabet k, and find the automaton that accepts all words of aut of length between (and including) min and i.
gap> a:=BoundedClassAutomaton(4); < deterministic automaton on 4 letters with 4 states > gap> Spectrum(a); [ 1, 2, 6, 24, 96, 384, 1536, 6144, 24576, 98304, 393216, 1572864, 6291456, 25165824, 100663296 ] gap> LengthBoundAut(a,4,8,4); < deterministic automaton on 4 letters with 22 states > gap> Spectrum(last); [ 0, 0, 0, 24, 96, 384, 1536, 6144, 0, 0, 0, 0, 0, 0, 0 ] gap>
‣ ShiftAut( i, k ) | ( function ) |
Returns: The automaton \(\Omega_{k-i}^{+i}\).
We are shifting the alphabet of \(\Omega_{k-i}\) in their values by \(i\) to expand to the alphabet \(\{1,\ldots,k\}\), but keeping the automaton structure of \(\Omega_{k-i}\).
gap> ShiftAut(2,4); < non deterministic automaton on 4 letters with 4 states > gap> Display(last); | 1 2 3 4 ----------------------------------- a | b | c | [ 2 ] [ 4 ] [ 4 ] [ 4 ] d | [ 3 ] [ 3 ] [ 3 ] [ 3 ] Initial state: [ 1 ] Accepting state: [ 4 ] gap> ShiftAut(1,4); < non deterministic automaton on 4 letters with 5 states > gap> Display(last); | 1 2 3 4 5 ------------------------------------------- a | b | [ 2 ] [ 5 ] [ 5 ] [ 3 ] [ 5 ] c | [ 3 ] [ 3 ] [ 3 ] [ 3 ] [ 3 ] d | [ 4 ] [ 4 ] [ 4 ] [ 4 ] [ 4 ] Initial state: [ 1 ] Accepting state: [ 5 ] gap>
‣ NextGap( gap, rank ) | ( function ) |
Returns: A list of gap sizes.
Knowing the current available gap sizes gap, which are the number of available spaces in a permutation plot. These gaps are separated by blocks where there are already points inserted. We determine where the next point (known to us as its rank) is being placed and what the next gap sizes are.
gap> NextGap([1,1],2); [ 1 ] gap> NextGap([1],3); [ 1, 1 ] gap> NextGap([2,1],4); [ 2, 1 ] gap>
‣ GapAut( k ) | ( function ) |
Returns: The non-deterministic automaton accepting the rank encoded language of \(\Omega_{k}\) and the list of all possible gap sizes.
The automaton accepts the rank encoded permutations of \(\Omega_{k}\), but the automaton is slightly extended through having each state corresponding to a gap size and the start state being the emptyset of gap sizes. The transitions of the automaton are determined through the knowledge of the available spaces and the rank. This is calculated in NextGap. Please note that the index of the gap sizes in the list corresponds to the state of the automaton.
gap> GapAut(3); [ < non deterministic automaton on 3 letters with 5 states >, [ [ ], [ 0 ], [ 1 ], [ 2 ], [ 1, 1 ] ] ] gap> Display(last[1]); | 1 2 3 4 5 ------------------------------------------- a | [ 2 ] [ 2 ] [ 2 ] [ 3 ] [ 3 ] b | [ 3 ] [ 3 ] [ 3 ] [ 3 ] [ 3 ] c | [ 4 ] [ 4 ] [ 5 ] [ 4 ] [ 5 ] Initial state: [ 1 ] Accepting states: [ 1, 2 ] gap>
‣ SumAut( sum, k ) | ( function ) |
Returns: The automaton accepting the language \(P_{sum}\).
This automaton is based on the GapAut where the accept states are chosen by their gap sizes, namely if the total sum of gap sizes equal to sum.
gap> SumAut(2,3); < non deterministic automaton on 3 letters with 5 states > gap> Display(last); | 1 2 3 4 5 ------------------------------------------- a | [ 2 ] [ 2 ] [ 2 ] [ 3 ] [ 3 ] b | [ 3 ] [ 3 ] [ 3 ] [ 3 ] [ 3 ] c | [ 4 ] [ 4 ] [ 5 ] [ 4 ] [ 5 ] Initial state: [ 1 ] Accepting states: [ 4, 5 ] gap>
‣ GapSumAut( gap, sum, k ) | ( function ) |
Returns: The automaton accepting the language \(Q_{gap,sum}\).
This automaton is based on the GapAut where the accept states are chosen by their gap sizes, namely if there is a gap size gap and the gap sizes before have a total sum of sum.
gap> GapSumAut(1,0,3); < non deterministic automaton on 3 letters with 5 states > gap> Display(last); | 1 2 3 4 5 ------------------------------------------- a | [ 2 ] [ 2 ] [ 2 ] [ 3 ] [ 3 ] b | [ 3 ] [ 3 ] [ 3 ] [ 3 ] [ 3 ] c | [ 4 ] [ 4 ] [ 5 ] [ 4 ] [ 5 ] Initial state: [ 1 ] Accepting states: [ 3, 5 ] gap>
‣ NonSimpleAut( k ) | ( function ) |
Returns: The automaton accepting all rank encoded non-simple permutations with rank encoding k.
We find the language of all non-simple permutations of the set of all \(k\) rank encoded permutations \(\Omega_{k}\) using the above equation.
gap> a:=NonSimpleAut(3); < deterministic automaton on 3 letters with 9 states > gap> Display(a); | 1 2 3 4 5 6 7 8 9 -------------------------------- a | 1 3 1 5 3 1 6 3 3 b | 3 3 3 3 9 9 3 9 3 c | 2 2 2 2 4 4 2 7 4 Initial state: [ 8 ] Accepting state: [ 1 ] gap>
The set of simple permutations of a class is the complement set of the class with the non-simple permutations. We are working in the rank encoding and so in language terms our set of simple permutations \(S_{k}\) will be the subset of \(\Omega_{k}\)
\[ E(S_{k}) = E(\Omega_{k}\setminus NS_{k}) = E(\Omega_{k}) \setminus E(NS_{k}) = E(\Omega_{k}) \cap E(NS_{k})^{C} \]
‣ SimplePermAut( k ) | ( function ) |
Returns: The automaton accepting all rank encoded simple permutations with highest rank encoding k.
We find the language of all simple permutations of the set of all \(k\) rank encoded permutations \(\Omega_{k}\) using the above equation.
gap> SimplePermAut(3); < deterministic automaton on 3 letters with 8 states > gap> Display(last); | 1 2 3 4 5 6 7 8 ----------------------------- a | 2 2 1 1 7 2 1 6 b | 2 2 4 2 2 4 4 2 c | 2 2 8 5 2 5 5 2 Initial state: [ 3 ] Accepting states: [ 1, 3 ] gap>
A permutation is said to be exceptional if it is of one of the following forms,
\[ 2 4 6 \ldots (2m) 1 3 5 \ldots (2m-1) \]
\[ (2m-1) (2m-3) \ldots 1 (2m) (2m-2) \ldots 2 \]
\[ (m+1) 1 (m+2) 2 (m+3) 3 \ldots (2m) m \]
\[ m (2m) (m-1) (2m-1) \ldots 1 (m+1) \]
where \(m \geq 2\) [PR12].
‣ IsExceptionalPerm( perm ) | ( function ) |
Returns: True if perm is exceptional, False otherwise.
The functions checks whether perm is one of the 4 types of exceptional permutations, that are described above.
gap> IsExceptionalPerm([1,2,5,3,4]); false gap> IsExceptionalPerm([1,1,3,1,1]); false gap> IsExceptionalPerm([2,4,6,1,3,5]); true gap> IsExceptionalPerm([2,3,4,1,1,1]); true gap>
‣ ExceptionalBoundedAutomaton( k ) | ( function ) |
Returns: The automaton which accepts all exceptional permutations with highest rank encoding k.
The language of k rank encoded exceptional permutations will be finite, and so it regular.
gap> ExceptionalBoundedAutomaton(8); < deterministic automaton on 8 letters with 41 states > gap> Spectrum(last,20); [ 0, 2, 0, 2, 0, 4, 0, 4, 0, 2, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0 ] gap> ExceptionalBoundedAutomaton(5); < deterministic automaton on 5 letters with 21 states > gap> Spectrum(last); [ 0, 2, 0, 2, 0, 4, 0, 2, 0, 0, 0, 0, 0, 0, 0 ] gap>
generated by GAPDoc2HTML