***************************************************************************** * www.FindStat.org - The Combinatorial Statistic Finder * * * * Copyright (C) 2019 The FindStatCrew * * * * This information is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * ***************************************************************************** ----------------------------------------------------------------------------- Statistic identifier: St000880 ----------------------------------------------------------------------------- Collection: Permutations ----------------------------------------------------------------------------- Description: The number of connected components of long braid edges in the graph of braid moves of a permutation. Given a permutation $\pi$, let $\operatorname{Red}(\pi)$ denote the set of reduced words for $\pi$ in terms of simple transpositions $s_i = (i,i+1)$. We now say that two reduced words are connected by a long braid move if they are obtained from each other by a modification of the form $s_i s_{i+1} s_i \leftrightarrow s_{i+1} s_i s_{i+1}$ as a consecutive subword of a reduced word. For example, the two reduced words $s_1s_3s_2s_3$ and $s_1s_2s_3s_2$ for $$(124) = (12)(34)(23)(34) = (12)(23)(34)(23)$$ share an edge because they are obtained from each other by interchanging $s_3s_2s_3 \leftrightarrow s_3s_2s_3$. This statistic counts the number connected components of such long braid moves among all reduced words. ----------------------------------------------------------------------------- References: [1] Fishel, S., Milićević, E., Patrias, R., Tenner, B. E. Enumerations relating braid and commutation classes [[arXiv:1708.04372]] ----------------------------------------------------------------------------- Code: def long_braid_move_graph(pi): V = [ tuple(w) for w in pi.reduced_words() ] is_edge = lambda w1,w2: w1 != w2 and any( w1[:i] == w2[:i] and w1[i+3:] == w2[i+3:] and w1[i] != w2[i] and w1[i+2] != w2[i+2] and w1[i] == w1[i+2]for i in range(len(w1)-2) ) return Graph([V,is_edge]) def statistic(pi): return len( long_braid_move_graph(pi).connected_components() ) ----------------------------------------------------------------------------- Statistic values: [1,2] => 1 [2,1] => 1 [1,2,3] => 1 [1,3,2] => 1 [2,1,3] => 1 [2,3,1] => 1 [3,1,2] => 1 [3,2,1] => 1 [1,2,3,4] => 1 [1,2,4,3] => 1 [1,3,2,4] => 1 [1,3,4,2] => 1 [1,4,2,3] => 1 [1,4,3,2] => 1 [2,1,3,4] => 1 [2,1,4,3] => 2 [2,3,1,4] => 1 [2,3,4,1] => 1 [2,4,1,3] => 2 [2,4,3,1] => 2 [3,1,2,4] => 1 [3,1,4,2] => 2 [3,2,1,4] => 1 [3,2,4,1] => 2 [3,4,1,2] => 2 [3,4,2,1] => 3 [4,1,2,3] => 1 [4,1,3,2] => 2 [4,2,1,3] => 2 [4,2,3,1] => 4 [4,3,1,2] => 3 [4,3,2,1] => 8 [1,2,3,4,5] => 1 [1,2,3,5,4] => 1 [1,2,4,3,5] => 1 [1,2,4,5,3] => 1 [1,2,5,3,4] => 1 [1,2,5,4,3] => 1 [1,3,2,4,5] => 1 [1,3,2,5,4] => 2 [1,3,4,2,5] => 1 [1,3,4,5,2] => 1 [1,3,5,2,4] => 2 [1,3,5,4,2] => 2 [1,4,2,3,5] => 1 [1,4,2,5,3] => 2 [1,4,3,2,5] => 1 [1,4,3,5,2] => 2 [1,4,5,2,3] => 2 [1,4,5,3,2] => 3 [1,5,2,3,4] => 1 [1,5,2,4,3] => 2 [1,5,3,2,4] => 2 [1,5,3,4,2] => 4 [1,5,4,2,3] => 3 [1,5,4,3,2] => 8 [2,1,3,4,5] => 1 [2,1,3,5,4] => 2 [2,1,4,3,5] => 2 [2,1,4,5,3] => 3 [2,1,5,3,4] => 3 [2,1,5,4,3] => 6 [2,3,1,4,5] => 1 [2,3,1,5,4] => 3 [2,3,4,1,5] => 1 [2,3,4,5,1] => 1 [2,3,5,1,4] => 3 [2,3,5,4,1] => 3 [2,4,1,3,5] => 2 [2,4,1,5,3] => 5 [2,4,3,1,5] => 2 [2,4,3,5,1] => 3 [2,4,5,1,3] => 5 [2,4,5,3,1] => 6 [2,5,1,3,4] => 3 [2,5,1,4,3] => 9 [2,5,3,1,4] => 4 [2,5,3,4,1] => 7 [2,5,4,1,3] => 11 [2,5,4,3,1] => 20 [3,1,2,4,5] => 1 [3,1,2,5,4] => 3 [3,1,4,2,5] => 2 [3,1,4,5,2] => 3 [3,1,5,2,4] => 5 [3,1,5,4,2] => 9 [3,2,1,4,5] => 1 [3,2,1,5,4] => 6 [3,2,4,1,5] => 2 [3,2,4,5,1] => 3 [3,2,5,1,4] => 9 [3,2,5,4,1] => 14 [3,4,1,2,5] => 2 [3,4,1,5,2] => 5 [3,4,2,1,5] => 3 [3,4,2,5,1] => 6 [3,4,5,1,2] => 5 [3,4,5,2,1] => 9 [3,5,1,2,4] => 5 [3,5,1,4,2] => 14 [3,5,2,1,4] => 11 [3,5,2,4,1] => 25 [3,5,4,1,2] => 16 [3,5,4,2,1] => 42 [4,1,2,3,5] => 1 [4,1,2,5,3] => 3 [4,1,3,2,5] => 2 [4,1,3,5,2] => 4 [4,1,5,2,3] => 5 [4,1,5,3,2] => 11 [4,2,1,3,5] => 2 [4,2,1,5,3] => 9 [4,2,3,1,5] => 4 [4,2,3,5,1] => 7 [4,2,5,1,3] => 14 [4,2,5,3,1] => 25 [4,3,1,2,5] => 3 [4,3,1,5,2] => 11 [4,3,2,1,5] => 8 [4,3,2,5,1] => 20 [4,3,5,1,2] => 16 [4,3,5,2,1] => 42 [4,5,1,2,3] => 5 [4,5,1,3,2] => 16 [4,5,2,1,3] => 16 [4,5,2,3,1] => 41 [4,5,3,1,2] => 28 [4,5,3,2,1] => 99 [5,1,2,3,4] => 1 [5,1,2,4,3] => 3 [5,1,3,2,4] => 3 [5,1,3,4,2] => 7 [5,1,4,2,3] => 6 [5,1,4,3,2] => 20 [5,2,1,3,4] => 3 [5,2,1,4,3] => 14 [5,2,3,1,4] => 7 [5,2,3,4,1] => 14 [5,2,4,1,3] => 25 [5,2,4,3,1] => 56 [5,3,1,2,4] => 6 [5,3,1,4,2] => 25 [5,3,2,1,4] => 20 [5,3,2,4,1] => 56 [5,3,4,1,2] => 41 [5,3,4,2,1] => 133 [5,4,1,2,3] => 9 [5,4,1,3,2] => 42 [5,4,2,1,3] => 42 [5,4,2,3,1] => 133 [5,4,3,1,2] => 99 [5,4,3,2,1] => 432 [1,2,3,4,5,6] => 1 [1,2,3,4,6,5] => 1 [1,2,3,5,4,6] => 1 [1,2,3,5,6,4] => 1 [1,2,3,6,4,5] => 1 [1,2,3,6,5,4] => 1 [1,2,4,3,5,6] => 1 [1,2,4,3,6,5] => 2 [1,2,4,5,3,6] => 1 [1,2,4,5,6,3] => 1 [1,2,4,6,3,5] => 2 [1,2,4,6,5,3] => 2 [1,2,5,3,4,6] => 1 [1,2,5,3,6,4] => 2 [1,2,5,4,3,6] => 1 [1,2,5,4,6,3] => 2 [1,2,5,6,3,4] => 2 [1,2,5,6,4,3] => 3 [1,2,6,3,4,5] => 1 [1,2,6,3,5,4] => 2 [1,2,6,4,3,5] => 2 [1,2,6,4,5,3] => 4 [1,2,6,5,3,4] => 3 [1,2,6,5,4,3] => 8 [1,3,2,4,5,6] => 1 [1,3,2,4,6,5] => 2 [1,3,2,5,4,6] => 2 [1,3,2,5,6,4] => 3 [1,3,2,6,4,5] => 3 [1,3,2,6,5,4] => 6 [1,3,4,2,5,6] => 1 [1,3,4,2,6,5] => 3 [1,3,4,5,2,6] => 1 [1,3,4,5,6,2] => 1 [1,3,4,6,2,5] => 3 [1,3,4,6,5,2] => 3 [1,3,5,2,4,6] => 2 [1,3,5,2,6,4] => 5 [1,3,5,4,2,6] => 2 [1,3,5,4,6,2] => 3 [1,3,5,6,2,4] => 5 [1,3,5,6,4,2] => 6 [1,3,6,2,4,5] => 3 [1,3,6,2,5,4] => 9 [1,3,6,4,2,5] => 4 [1,3,6,4,5,2] => 7 [1,3,6,5,2,4] => 11 [1,3,6,5,4,2] => 20 [1,4,2,3,5,6] => 1 [1,4,2,3,6,5] => 3 [1,4,2,5,3,6] => 2 [1,4,2,5,6,3] => 3 [1,4,2,6,3,5] => 5 [1,4,2,6,5,3] => 9 [1,4,3,2,5,6] => 1 [1,4,3,2,6,5] => 6 [1,4,3,5,2,6] => 2 [1,4,3,5,6,2] => 3 [1,4,3,6,2,5] => 9 [1,4,3,6,5,2] => 14 [1,4,5,2,3,6] => 2 [1,4,5,2,6,3] => 5 [1,4,5,3,2,6] => 3 [1,4,5,3,6,2] => 6 [1,4,5,6,2,3] => 5 [1,4,5,6,3,2] => 9 [1,4,6,2,3,5] => 5 [1,4,6,2,5,3] => 14 [1,4,6,3,2,5] => 11 [1,4,6,3,5,2] => 25 [1,4,6,5,2,3] => 16 [1,4,6,5,3,2] => 42 [1,5,2,3,4,6] => 1 [1,5,2,3,6,4] => 3 [1,5,2,4,3,6] => 2 [1,5,2,4,6,3] => 4 [1,5,2,6,3,4] => 5 [1,5,2,6,4,3] => 11 [1,5,3,2,4,6] => 2 [1,5,3,2,6,4] => 9 [1,5,3,4,2,6] => 4 [1,5,3,4,6,2] => 7 [1,5,3,6,2,4] => 14 [1,5,3,6,4,2] => 25 [1,5,4,2,3,6] => 3 [1,5,4,2,6,3] => 11 [1,5,4,3,2,6] => 8 [1,5,4,3,6,2] => 20 [1,5,4,6,2,3] => 16 [1,5,4,6,3,2] => 42 [1,5,6,2,3,4] => 5 [1,5,6,2,4,3] => 16 [1,5,6,3,2,4] => 16 [1,5,6,3,4,2] => 41 [1,5,6,4,2,3] => 28 [1,5,6,4,3,2] => 99 [1,6,2,3,4,5] => 1 [1,6,2,3,5,4] => 3 [1,6,2,4,3,5] => 3 [1,6,2,4,5,3] => 7 [1,6,2,5,3,4] => 6 [1,6,2,5,4,3] => 20 [1,6,3,2,4,5] => 3 [1,6,3,2,5,4] => 14 [1,6,3,4,2,5] => 7 [1,6,3,4,5,2] => 14 [1,6,3,5,2,4] => 25 [1,6,3,5,4,2] => 56 [1,6,4,2,3,5] => 6 [1,6,4,2,5,3] => 25 [1,6,4,3,2,5] => 20 [1,6,4,3,5,2] => 56 [1,6,4,5,2,3] => 41 [1,6,4,5,3,2] => 133 [1,6,5,2,3,4] => 9 [1,6,5,2,4,3] => 42 [1,6,5,3,2,4] => 42 [1,6,5,3,4,2] => 133 [1,6,5,4,2,3] => 99 [1,6,5,4,3,2] => 432 [2,1,3,4,5,6] => 1 [2,1,3,4,6,5] => 2 [2,1,3,5,4,6] => 2 [2,1,3,5,6,4] => 3 [2,1,3,6,4,5] => 3 [2,1,3,6,5,4] => 6 [2,1,4,3,5,6] => 2 [2,1,4,3,6,5] => 6 [2,1,4,5,3,6] => 3 [2,1,4,5,6,3] => 4 [2,1,4,6,3,5] => 8 [2,1,4,6,5,3] => 12 [2,1,5,3,4,6] => 3 [2,1,5,3,6,4] => 8 [2,1,5,4,3,6] => 6 [2,1,5,4,6,3] => 12 [2,1,5,6,3,4] => 10 [2,1,5,6,4,3] => 22 [2,1,6,3,4,5] => 4 [2,1,6,3,5,4] => 12 [2,1,6,4,3,5] => 12 [2,1,6,4,5,3] => 28 [2,1,6,5,3,4] => 22 [2,1,6,5,4,3] => 72 [2,3,1,4,5,6] => 1 [2,3,1,4,6,5] => 3 [2,3,1,5,4,6] => 3 [2,3,1,5,6,4] => 6 [2,3,1,6,4,5] => 6 [2,3,1,6,5,4] => 17 [2,3,4,1,5,6] => 1 [2,3,4,1,6,5] => 4 [2,3,4,5,1,6] => 1 [2,3,4,5,6,1] => 1 [2,3,4,6,1,5] => 4 [2,3,4,6,5,1] => 4 [2,3,5,1,4,6] => 3 [2,3,5,1,6,4] => 9 [2,3,5,4,1,6] => 3 [2,3,5,4,6,1] => 4 [2,3,5,6,1,4] => 9 [2,3,5,6,4,1] => 10 [2,3,6,1,4,5] => 6 [2,3,6,1,5,4] => 23 [2,3,6,4,1,5] => 7 [2,3,6,4,5,1] => 11 [2,3,6,5,1,4] => 26 [2,3,6,5,4,1] => 40 [2,4,1,3,5,6] => 2 [2,4,1,3,6,5] => 8 [2,4,1,5,3,6] => 5 [2,4,1,5,6,3] => 9 [2,4,1,6,3,5] => 16 [2,4,1,6,5,3] => 35 [2,4,3,1,5,6] => 2 [2,4,3,1,6,5] => 12 [2,4,3,5,1,6] => 3 [2,4,3,5,6,1] => 4 [2,4,3,6,1,5] => 16 [2,4,3,6,5,1] => 22 [2,4,5,1,3,6] => 5 [2,4,5,1,6,3] => 14 [2,4,5,3,1,6] => 6 [2,4,5,3,6,1] => 10 [2,4,5,6,1,3] => 14 [2,4,5,6,3,1] => 19 [2,4,6,1,3,5] => 16 [2,4,6,1,5,3] => 51 [2,4,6,3,1,5] => 24 [2,4,6,3,5,1] => 46 [2,4,6,5,1,3] => 56 [2,4,6,5,3,1] => 101 [2,5,1,3,4,6] => 3 [2,5,1,3,6,4] => 11 [2,5,1,4,3,6] => 9 [2,5,1,4,6,3] => 21 [2,5,1,6,3,4] => 21 [2,5,1,6,4,3] => 61 [2,5,3,1,4,6] => 4 [2,5,3,1,6,4] => 21 [2,5,3,4,1,6] => 7 [2,5,3,4,6,1] => 11 [2,5,3,6,1,4] => 30 [2,5,3,6,4,1] => 47 [2,5,4,1,3,6] => 11 [2,5,4,1,6,3] => 42 [2,5,4,3,1,6] => 20 [2,5,4,3,6,1] => 40 [2,5,4,6,1,3] => 56 [2,5,4,6,3,1] => 104 [2,5,6,1,3,4] => 21 [2,5,6,1,4,3] => 82 [2,5,6,3,1,4] => 40 [2,5,6,3,4,1] => 87 [2,5,6,4,1,3] => 117 [2,5,6,4,3,1] => 276 [2,6,1,3,4,5] => 4 [2,6,1,3,5,4] => 16 [2,6,1,4,3,5] => 16 [2,6,1,4,5,3] => 44 [2,6,1,5,3,4] => 38 [2,6,1,5,4,3] => 150 [2,6,3,1,4,5] => 7 [2,6,3,1,5,4] => 40 [2,6,3,4,1,5] => 14 [2,6,3,4,5,1] => 25 [2,6,3,5,1,4] => 66 [2,6,3,5,4,1] => 124 [2,6,4,1,3,5] => 24 [2,6,4,1,5,3] => 107 [2,6,4,3,1,5] => 54 [2,6,4,3,5,1] => 121 [2,6,4,5,1,3] => 163 [2,6,4,5,3,1] => 361 [2,6,5,1,3,4] => 49 [2,6,5,1,4,3] => 259 [2,6,5,3,1,4] => 130 [2,6,5,3,4,1] => 331 [2,6,5,4,1,3] => 481 [2,6,5,4,3,1] => 1356 [3,1,2,4,5,6] => 1 [3,1,2,4,6,5] => 3 [3,1,2,5,4,6] => 3 [3,1,2,5,6,4] => 6 [3,1,2,6,4,5] => 6 [3,1,2,6,5,4] => 17 [3,1,4,2,5,6] => 2 [3,1,4,2,6,5] => 8 [3,1,4,5,2,6] => 3 [3,1,4,5,6,2] => 4 [3,1,4,6,2,5] => 11 [3,1,4,6,5,2] => 16 [3,1,5,2,4,6] => 5 [3,1,5,2,6,4] => 16 [3,1,5,4,2,6] => 9 [3,1,5,4,6,2] => 16 [3,1,5,6,2,4] => 21 [3,1,5,6,4,2] => 38 [3,1,6,2,4,5] => 9 [3,1,6,2,5,4] => 35 [3,1,6,4,2,5] => 21 [3,1,6,4,5,2] => 44 [3,1,6,5,2,4] => 61 [3,1,6,5,4,2] => 150 [3,2,1,4,5,6] => 1 [3,2,1,4,6,5] => 6 [3,2,1,5,4,6] => 6 [3,2,1,5,6,4] => 17 [3,2,1,6,4,5] => 17 [3,2,1,6,5,4] => 66 [3,2,4,1,5,6] => 2 [3,2,4,1,6,5] => 12 [3,2,4,5,1,6] => 3 [3,2,4,5,6,1] => 4 [3,2,4,6,1,5] => 16 [3,2,4,6,5,1] => 22 [3,2,5,1,4,6] => 9 [3,2,5,1,6,4] => 35 [3,2,5,4,1,6] => 14 [3,2,5,4,6,1] => 22 [3,2,5,6,1,4] => 44 [3,2,5,6,4,1] => 67 [3,2,6,1,4,5] => 23 [3,2,6,1,5,4] => 112 [3,2,6,4,1,5] => 40 [3,2,6,4,5,1] => 73 [3,2,6,5,1,4] => 165 [3,2,6,5,4,1] => 318 [3,4,1,2,5,6] => 2 [3,4,1,2,6,5] => 10 [3,4,1,5,2,6] => 5 [3,4,1,5,6,2] => 9 [3,4,1,6,2,5] => 21 [3,4,1,6,5,2] => 44 [3,4,2,1,5,6] => 3 [3,4,2,1,6,5] => 22 [3,4,2,5,1,6] => 6 [3,4,2,5,6,1] => 10 [3,4,2,6,1,5] => 38 [3,4,2,6,5,1] => 67 [3,4,5,1,2,6] => 5 [3,4,5,1,6,2] => 14 [3,4,5,2,1,6] => 9 [3,4,5,2,6,1] => 19 [3,4,5,6,1,2] => 14 [3,4,5,6,2,1] => 28 [3,4,6,1,2,5] => 21 [3,4,6,1,5,2] => 65 [3,4,6,2,1,5] => 49 [3,4,6,2,5,1] => 116 [3,4,6,5,1,2] => 70 [3,4,6,5,2,1] => 183 [3,5,1,2,4,6] => 5 [3,5,1,2,6,4] => 21 [3,5,1,4,2,6] => 14 [3,5,1,4,6,2] => 30 [3,5,1,6,2,4] => 42 [3,5,1,6,4,2] => 105 [3,5,2,1,4,6] => 11 [3,5,2,1,6,4] => 61 [3,5,2,4,1,6] => 25 [3,5,2,4,6,1] => 47 [3,5,2,6,1,4] => 105 [3,5,2,6,4,1] => 208 [3,5,4,1,2,6] => 16 [3,5,4,1,6,2] => 56 [3,5,4,2,1,6] => 42 [3,5,4,2,6,1] => 104 [3,5,4,6,1,2] => 70 [3,5,4,6,2,1] => 186 [3,5,6,1,2,4] => 42 [3,5,6,1,4,2] => 147 [3,5,6,2,1,4] => 126 [3,5,6,2,4,1] => 334 [3,5,6,4,1,2] => 187 [3,5,6,4,2,1] => 618 [3,6,1,2,4,5] => 9 [3,6,1,2,5,4] => 44 [3,6,1,4,2,5] => 30 [3,6,1,4,5,2] => 74 [3,6,1,5,2,4] => 105 [3,6,1,5,4,2] => 320 [3,6,2,1,4,5] => 26 [3,6,2,1,5,4] => 165 [3,6,2,4,1,5] => 66 [3,6,2,4,5,1] => 139 [3,6,2,5,1,4] => 330 [3,6,2,5,4,1] => 761 ----------------------------------------------------------------------------- Created: Jul 03, 2017 at 16:58 by Christian Stump ----------------------------------------------------------------------------- Last Updated: Aug 24, 2017 at 23:36 by Martin Rubey