***************************************************************************** * 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: St000881 ----------------------------------------------------------------------------- Collection: Permutations ----------------------------------------------------------------------------- Description: The number of short 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 short braid move if they are obtained from each other by a modification of the form $s_i s_j \leftrightarrow s_j s_i$ for $|i-j| > 1$ as a consecutive subword of a reduced word. For example, the two reduced words $s_1s_3s_2$ and $s_3s_1s_2$ for $$(1243) = (12)(34)(23) = (34)(12)(23)$$ share an edge because they are obtained from each other by interchanging $s_1s_3 \leftrightarrow s_3s_1$. This statistic counts the number of such short braid moves among all reduced words. ----------------------------------------------------------------------------- References: ----------------------------------------------------------------------------- Code: def short_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+2:] == w2[i+2:] for i in range(len(w1)-1) ) return Graph([V,is_edge]) def statistic(pi): return len( short_braid_move_graph(pi).edges() ) ----------------------------------------------------------------------------- Statistic values: [1,2] => 0 [2,1] => 0 [1,2,3] => 0 [1,3,2] => 0 [2,1,3] => 0 [2,3,1] => 0 [3,1,2] => 0 [3,2,1] => 0 [1,2,3,4] => 0 [1,2,4,3] => 0 [1,3,2,4] => 0 [1,3,4,2] => 0 [1,4,2,3] => 0 [1,4,3,2] => 0 [2,1,3,4] => 0 [2,1,4,3] => 1 [2,3,1,4] => 0 [2,3,4,1] => 0 [2,4,1,3] => 1 [2,4,3,1] => 1 [3,1,2,4] => 0 [3,1,4,2] => 1 [3,2,1,4] => 0 [3,2,4,1] => 1 [3,4,1,2] => 1 [3,4,2,1] => 2 [4,1,2,3] => 0 [4,1,3,2] => 1 [4,2,1,3] => 1 [4,2,3,1] => 4 [4,3,1,2] => 2 [4,3,2,1] => 10 [1,2,3,4,5] => 0 [1,2,3,5,4] => 0 [1,2,4,3,5] => 0 [1,2,4,5,3] => 0 [1,2,5,3,4] => 0 [1,2,5,4,3] => 0 [1,3,2,4,5] => 0 [1,3,2,5,4] => 1 [1,3,4,2,5] => 0 [1,3,4,5,2] => 0 [1,3,5,2,4] => 1 [1,3,5,4,2] => 1 [1,4,2,3,5] => 0 [1,4,2,5,3] => 1 [1,4,3,2,5] => 0 [1,4,3,5,2] => 1 [1,4,5,2,3] => 1 [1,4,5,3,2] => 2 [1,5,2,3,4] => 0 [1,5,2,4,3] => 1 [1,5,3,2,4] => 1 [1,5,3,4,2] => 4 [1,5,4,2,3] => 2 [1,5,4,3,2] => 10 [2,1,3,4,5] => 0 [2,1,3,5,4] => 1 [2,1,4,3,5] => 1 [2,1,4,5,3] => 2 [2,1,5,3,4] => 2 [2,1,5,4,3] => 6 [2,3,1,4,5] => 0 [2,3,1,5,4] => 2 [2,3,4,1,5] => 0 [2,3,4,5,1] => 0 [2,3,5,1,4] => 2 [2,3,5,4,1] => 2 [2,4,1,3,5] => 1 [2,4,1,5,3] => 5 [2,4,3,1,5] => 1 [2,4,3,5,1] => 2 [2,4,5,1,3] => 5 [2,4,5,3,1] => 7 [2,5,1,3,4] => 2 [2,5,1,4,3] => 11 [2,5,3,1,4] => 4 [2,5,3,4,1] => 9 [2,5,4,1,3] => 16 [2,5,4,3,1] => 37 [3,1,2,4,5] => 0 [3,1,2,5,4] => 2 [3,1,4,2,5] => 1 [3,1,4,5,2] => 2 [3,1,5,2,4] => 5 [3,1,5,4,2] => 11 [3,2,1,4,5] => 0 [3,2,1,5,4] => 6 [3,2,4,1,5] => 1 [3,2,4,5,1] => 2 [3,2,5,1,4] => 11 [3,2,5,4,1] => 19 [3,4,1,2,5] => 1 [3,4,1,5,2] => 5 [3,4,2,1,5] => 2 [3,4,2,5,1] => 7 [3,4,5,1,2] => 5 [3,4,5,2,1] => 12 [3,5,1,2,4] => 5 [3,5,1,4,2] => 21 [3,5,2,1,4] => 16 [3,5,2,4,1] => 46 [3,5,4,1,2] => 26 [3,5,4,2,1] => 89 [4,1,2,3,5] => 0 [4,1,2,5,3] => 2 [4,1,3,2,5] => 1 [4,1,3,5,2] => 4 [4,1,5,2,3] => 5 [4,1,5,3,2] => 16 [4,2,1,3,5] => 1 [4,2,1,5,3] => 11 [4,2,3,1,5] => 4 [4,2,3,5,1] => 9 [4,2,5,1,3] => 21 [4,2,5,3,1] => 46 [4,3,1,2,5] => 2 [4,3,1,5,2] => 16 [4,3,2,1,5] => 10 [4,3,2,5,1] => 37 [4,3,5,1,2] => 26 [4,3,5,2,1] => 89 [4,5,1,2,3] => 5 [4,5,1,3,2] => 26 [4,5,2,1,3] => 26 [4,5,2,3,1] => 88 [4,5,3,1,2] => 52 [4,5,3,2,1] => 250 [5,1,2,3,4] => 0 [5,1,2,4,3] => 2 [5,1,3,2,4] => 2 [5,1,3,4,2] => 9 [5,1,4,2,3] => 7 [5,1,4,3,2] => 37 [5,2,1,3,4] => 2 [5,2,1,4,3] => 19 [5,2,3,1,4] => 9 [5,2,3,4,1] => 24 [5,2,4,1,3] => 46 [5,2,4,3,1] => 133 [5,3,1,2,4] => 7 [5,3,1,4,2] => 46 [5,3,2,1,4] => 37 [5,3,2,4,1] => 133 [5,3,4,1,2] => 88 [5,3,4,2,1] => 366 [5,4,1,2,3] => 12 [5,4,1,3,2] => 89 [5,4,2,1,3] => 89 [5,4,2,3,1] => 366 [5,4,3,1,2] => 250 [5,4,3,2,1] => 1386 [1,2,3,4,5,6] => 0 [1,2,3,4,6,5] => 0 [1,2,3,5,4,6] => 0 [1,2,3,5,6,4] => 0 [1,2,3,6,4,5] => 0 [1,2,3,6,5,4] => 0 [1,2,4,3,5,6] => 0 [1,2,4,3,6,5] => 1 [1,2,4,5,3,6] => 0 [1,2,4,5,6,3] => 0 [1,2,4,6,3,5] => 1 [1,2,4,6,5,3] => 1 [1,2,5,3,4,6] => 0 [1,2,5,3,6,4] => 1 [1,2,5,4,3,6] => 0 [1,2,5,4,6,3] => 1 [1,2,5,6,3,4] => 1 [1,2,5,6,4,3] => 2 [1,2,6,3,4,5] => 0 [1,2,6,3,5,4] => 1 [1,2,6,4,3,5] => 1 [1,2,6,4,5,3] => 4 [1,2,6,5,3,4] => 2 [1,2,6,5,4,3] => 10 [1,3,2,4,5,6] => 0 [1,3,2,4,6,5] => 1 [1,3,2,5,4,6] => 1 [1,3,2,5,6,4] => 2 [1,3,2,6,4,5] => 2 [1,3,2,6,5,4] => 6 [1,3,4,2,5,6] => 0 [1,3,4,2,6,5] => 2 [1,3,4,5,2,6] => 0 [1,3,4,5,6,2] => 0 [1,3,4,6,2,5] => 2 [1,3,4,6,5,2] => 2 [1,3,5,2,4,6] => 1 [1,3,5,2,6,4] => 5 [1,3,5,4,2,6] => 1 [1,3,5,4,6,2] => 2 [1,3,5,6,2,4] => 5 [1,3,5,6,4,2] => 7 [1,3,6,2,4,5] => 2 [1,3,6,2,5,4] => 11 [1,3,6,4,2,5] => 4 [1,3,6,4,5,2] => 9 [1,3,6,5,2,4] => 16 [1,3,6,5,4,2] => 37 [1,4,2,3,5,6] => 0 [1,4,2,3,6,5] => 2 [1,4,2,5,3,6] => 1 [1,4,2,5,6,3] => 2 [1,4,2,6,3,5] => 5 [1,4,2,6,5,3] => 11 [1,4,3,2,5,6] => 0 [1,4,3,2,6,5] => 6 [1,4,3,5,2,6] => 1 [1,4,3,5,6,2] => 2 [1,4,3,6,2,5] => 11 [1,4,3,6,5,2] => 19 [1,4,5,2,3,6] => 1 [1,4,5,2,6,3] => 5 [1,4,5,3,2,6] => 2 [1,4,5,3,6,2] => 7 [1,4,5,6,2,3] => 5 [1,4,5,6,3,2] => 12 [1,4,6,2,3,5] => 5 [1,4,6,2,5,3] => 21 [1,4,6,3,2,5] => 16 [1,4,6,3,5,2] => 46 [1,4,6,5,2,3] => 26 [1,4,6,5,3,2] => 89 [1,5,2,3,4,6] => 0 [1,5,2,3,6,4] => 2 [1,5,2,4,3,6] => 1 [1,5,2,4,6,3] => 4 [1,5,2,6,3,4] => 5 [1,5,2,6,4,3] => 16 [1,5,3,2,4,6] => 1 [1,5,3,2,6,4] => 11 [1,5,3,4,2,6] => 4 [1,5,3,4,6,2] => 9 [1,5,3,6,2,4] => 21 [1,5,3,6,4,2] => 46 [1,5,4,2,3,6] => 2 [1,5,4,2,6,3] => 16 [1,5,4,3,2,6] => 10 [1,5,4,3,6,2] => 37 [1,5,4,6,2,3] => 26 [1,5,4,6,3,2] => 89 [1,5,6,2,3,4] => 5 [1,5,6,2,4,3] => 26 [1,5,6,3,2,4] => 26 [1,5,6,3,4,2] => 88 [1,5,6,4,2,3] => 52 [1,5,6,4,3,2] => 250 [1,6,2,3,4,5] => 0 [1,6,2,3,5,4] => 2 [1,6,2,4,3,5] => 2 [1,6,2,4,5,3] => 9 [1,6,2,5,3,4] => 7 [1,6,2,5,4,3] => 37 [1,6,3,2,4,5] => 2 [1,6,3,2,5,4] => 19 [1,6,3,4,2,5] => 9 [1,6,3,4,5,2] => 24 [1,6,3,5,2,4] => 46 [1,6,3,5,4,2] => 133 [1,6,4,2,3,5] => 7 [1,6,4,2,5,3] => 46 [1,6,4,3,2,5] => 37 [1,6,4,3,5,2] => 133 [1,6,4,5,2,3] => 88 [1,6,4,5,3,2] => 366 [1,6,5,2,3,4] => 12 [1,6,5,2,4,3] => 89 [1,6,5,3,2,4] => 89 [1,6,5,3,4,2] => 366 [1,6,5,4,2,3] => 250 [1,6,5,4,3,2] => 1386 [2,1,3,4,5,6] => 0 [2,1,3,4,6,5] => 1 [2,1,3,5,4,6] => 1 [2,1,3,5,6,4] => 2 [2,1,3,6,4,5] => 2 [2,1,3,6,5,4] => 6 [2,1,4,3,5,6] => 1 [2,1,4,3,6,5] => 6 [2,1,4,5,3,6] => 2 [2,1,4,5,6,3] => 3 [2,1,4,6,3,5] => 9 [2,1,4,6,5,3] => 16 [2,1,5,3,4,6] => 2 [2,1,5,3,6,4] => 9 [2,1,5,4,3,6] => 6 [2,1,5,4,6,3] => 16 [2,1,5,6,3,4] => 12 [2,1,5,6,4,3] => 35 [2,1,6,3,4,5] => 3 [2,1,6,3,5,4] => 16 [2,1,6,4,3,5] => 16 [2,1,6,4,5,3] => 50 [2,1,6,5,3,4] => 35 [2,1,6,5,4,3] => 156 [2,3,1,4,5,6] => 0 [2,3,1,4,6,5] => 2 [2,3,1,5,4,6] => 2 [2,3,1,5,6,4] => 6 [2,3,1,6,4,5] => 6 [2,3,1,6,5,4] => 24 [2,3,4,1,5,6] => 0 [2,3,4,1,6,5] => 3 [2,3,4,5,1,6] => 0 [2,3,4,5,6,1] => 0 [2,3,4,6,1,5] => 3 [2,3,4,6,5,1] => 3 [2,3,5,1,4,6] => 2 [2,3,5,1,6,4] => 11 [2,3,5,4,1,6] => 2 [2,3,5,4,6,1] => 3 [2,3,5,6,1,4] => 11 [2,3,5,6,4,1] => 14 [2,3,6,1,4,5] => 6 [2,3,6,1,5,4] => 36 [2,3,6,4,1,5] => 9 [2,3,6,4,5,1] => 16 [2,3,6,5,1,4] => 47 [2,3,6,5,4,1] => 86 [2,4,1,3,5,6] => 1 [2,4,1,3,6,5] => 9 [2,4,1,5,3,6] => 5 [2,4,1,5,6,3] => 11 [2,4,1,6,3,5] => 24 [2,4,1,6,5,3] => 63 [2,4,3,1,5,6] => 1 [2,4,3,1,6,5] => 16 [2,4,3,5,1,6] => 2 [2,4,3,5,6,1] => 3 [2,4,3,6,1,5] => 23 [2,4,3,6,5,1] => 34 [2,4,5,1,3,6] => 5 [2,4,5,1,6,3] => 21 [2,4,5,3,1,6] => 7 [2,4,5,3,6,1] => 14 [2,4,5,6,1,3] => 21 [2,4,5,6,3,1] => 35 [2,4,6,1,3,5] => 24 [2,4,6,1,5,3] => 103 [2,4,6,3,1,5] => 47 [2,4,6,3,5,1] => 100 [2,4,6,5,1,3] => 124 [2,4,6,5,3,1] => 273 [2,5,1,3,4,6] => 2 [2,5,1,3,6,4] => 14 [2,5,1,4,3,6] => 11 [2,5,1,4,6,3] => 35 [2,5,1,6,3,4] => 34 [2,5,1,6,4,3] => 129 [2,5,3,1,4,6] => 4 [2,5,3,1,6,4] => 35 [2,5,3,4,1,6] => 9 [2,5,3,4,6,1] => 16 [2,5,3,6,1,4] => 55 [2,5,3,6,4,1] => 99 [2,5,4,1,3,6] => 16 [2,5,4,1,6,3] => 88 [2,5,4,3,1,6] => 37 [2,5,4,3,6,1] => 86 [2,5,4,6,1,3] => 123 [2,5,4,6,3,1] => 272 [2,5,6,1,3,4] => 34 [2,5,6,1,4,3] => 184 [2,5,6,3,1,4] => 89 [2,5,6,3,4,1] => 223 [2,5,6,4,1,3] => 307 [2,5,6,4,3,1] => 872 [2,6,1,3,4,5] => 3 [2,6,1,3,5,4] => 23 [2,6,1,4,3,5] => 23 [2,6,1,4,5,3] => 88 [2,6,1,5,3,4] => 73 [2,6,1,5,4,3] => 383 [2,6,3,1,4,5] => 9 [2,6,3,1,5,4] => 78 [2,6,3,4,1,5] => 24 [2,6,3,4,5,1] => 50 [2,6,3,5,1,4] => 151 [2,6,3,5,4,1] => 337 [2,6,4,1,3,5] => 47 [2,6,4,1,5,3] => 273 [2,6,4,3,1,5] => 134 [2,6,4,3,5,1] => 339 [2,6,4,5,1,3] => 453 [2,6,4,5,3,1] => 1199 [2,6,5,1,3,4] => 107 [2,6,5,1,4,3] => 744 [2,6,5,3,1,4] => 368 [2,6,5,3,4,1] => 1074 [2,6,5,4,1,3] => 1602 [2,6,5,4,3,1] => 5251 [3,1,2,4,5,6] => 0 [3,1,2,4,6,5] => 2 [3,1,2,5,4,6] => 2 [3,1,2,5,6,4] => 6 [3,1,2,6,4,5] => 6 [3,1,2,6,5,4] => 24 [3,1,4,2,5,6] => 1 [3,1,4,2,6,5] => 9 [3,1,4,5,2,6] => 2 [3,1,4,5,6,2] => 3 [3,1,4,6,2,5] => 14 [3,1,4,6,5,2] => 23 [3,1,5,2,4,6] => 5 [3,1,5,2,6,4] => 24 [3,1,5,4,2,6] => 11 [3,1,5,4,6,2] => 23 [3,1,5,6,2,4] => 34 [3,1,5,6,4,2] => 73 [3,1,6,2,4,5] => 11 [3,1,6,2,5,4] => 63 [3,1,6,4,2,5] => 35 [3,1,6,4,5,2] => 88 [3,1,6,5,2,4] => 129 [3,1,6,5,4,2] => 383 [3,2,1,4,5,6] => 0 [3,2,1,4,6,5] => 6 [3,2,1,5,4,6] => 6 [3,2,1,5,6,4] => 24 [3,2,1,6,4,5] => 24 [3,2,1,6,5,4] => 120 [3,2,4,1,5,6] => 1 [3,2,4,1,6,5] => 16 [3,2,4,5,1,6] => 2 [3,2,4,5,6,1] => 3 [3,2,4,6,1,5] => 23 [3,2,4,6,5,1] => 34 [3,2,5,1,4,6] => 11 [3,2,5,1,6,4] => 63 [3,2,5,4,1,6] => 19 [3,2,5,4,6,1] => 34 [3,2,5,6,1,4] => 83 [3,2,5,6,4,1] => 145 [3,2,6,1,4,5] => 36 [3,2,6,1,5,4] => 238 [3,2,6,4,1,5] => 78 [3,2,6,4,5,1] => 162 [3,2,6,5,1,4] => 403 [3,2,6,5,4,1] => 909 [3,4,1,2,5,6] => 1 [3,4,1,2,6,5] => 12 [3,4,1,5,2,6] => 5 [3,4,1,5,6,2] => 11 [3,4,1,6,2,5] => 34 [3,4,1,6,5,2] => 83 [3,4,2,1,5,6] => 2 [3,4,2,1,6,5] => 35 [3,4,2,5,1,6] => 7 [3,4,2,5,6,1] => 14 [3,4,2,6,1,5] => 73 [3,4,2,6,5,1] => 145 [3,4,5,1,2,6] => 5 [3,4,5,1,6,2] => 21 [3,4,5,2,1,6] => 12 [3,4,5,2,6,1] => 35 [3,4,5,6,1,2] => 21 [3,4,5,6,2,1] => 56 [3,4,6,1,2,5] => 34 [3,4,6,1,5,2] => 138 [3,4,6,2,1,5] => 107 [3,4,6,2,5,1] => 301 [3,4,6,5,1,2] => 159 [3,4,6,5,2,1] => 530 [3,5,1,2,4,6] => 5 [3,5,1,2,6,4] => 34 [3,5,1,4,2,6] => 21 [3,5,1,4,6,2] => 55 [3,5,1,6,2,4] => 84 [3,5,1,6,4,2] => 252 [3,5,2,1,4,6] => 16 [3,5,2,1,6,4] => 129 [3,5,2,4,1,6] => 46 [3,5,2,4,6,1] => 99 [3,5,2,6,1,4] => 252 [3,5,2,6,4,1] => 574 [3,5,4,1,2,6] => 26 [3,5,4,1,6,2] => 123 [3,5,4,2,1,6] => 89 [3,5,4,2,6,1] => 272 [3,5,4,6,1,2] => 158 [3,5,4,6,2,1] => 528 [3,5,6,1,2,4] => 84 [3,5,6,1,4,2] => 378 [3,5,6,2,1,4] => 336 [3,5,6,2,4,1] => 1036 [3,5,6,4,1,2] => 536 [3,5,6,4,2,1] => 2184 [3,6,1,2,4,5] => 11 [3,6,1,2,5,4] => 83 [3,6,1,4,2,5] => 55 [3,6,1,4,5,2] => 169 [3,6,1,5,2,4] => 252 [3,6,1,5,4,2] => 936 [3,6,2,1,4,5] => 47 [3,6,2,1,5,4] => 403 [3,6,2,4,1,5] => 151 [3,6,2,4,5,1] => 368 [3,6,2,5,1,4] => 938 [3,6,2,5,4,1] => 2530 ----------------------------------------------------------------------------- Created: Jul 03, 2017 at 16:58 by Christian Stump ----------------------------------------------------------------------------- Last Updated: Jul 03, 2017 at 16:58 by Christian Stump