7
$\begingroup$

Given a permutation $\pi$ we can write $\pi=s_{i_1} ... s_{i_l}$ as a product of simple transpositions $s_i=(i,i+1)$ in a minimal way.

Question 1: Is there an "official" name for the permutation statistic given by the cardinality of the set $\{i_1,...,i_l \}$ ? (such as Coxeter length seems to be the official name for $l$)

See http://www.findstat.org/StatisticsDatabase/St000019 for this statistic.

Question 2: Is there a reference that the generating function for this permutation statistic restricted to 321-avoiding permutations is given by Catalan's triangle: http://oeis.org/A009766 ?

$\endgroup$
6
  • 3
    $\begingroup$ Q1: I have seen $\{i_1,\dots,i_l\}$ being called support of $\pi$ as it is independent of the chosen word the Matsumoto's property that all reduced expressions are connected by braid relations. $\endgroup$ Mar 8 '20 at 10:31
  • 4
    $\begingroup$ Just looking at St000019: what is wrong with cardinality of support ? $\endgroup$ Mar 8 '20 at 10:41
  • 1
    $\begingroup$ The support of a permutation can also mean the set of all of its non-fixed points. That is a different set. $\endgroup$ Mar 8 '20 at 16:09
  • 1
    $\begingroup$ I think Bridget Tenner is someone worth asking about this (or at least looking into her papers). $\endgroup$ Mar 8 '20 at 16:10
  • 1
    $\begingroup$ Not directly related but in the case of 312-avoiding permutation, the map in Section 3 of the Bandlow-Killpatrick paper might be useful. combinatorics.org/ojs/index.php/eljc/article/view/v8i1r40/pdf $\endgroup$
    – user35313
    Mar 8 '20 at 21:41
2
+50
$\begingroup$

For Q1, the sequence corresponding to Stat19 is given in A263484 and comes from a 2005 article by Richard Stanley (developing ideas from Comtet) on connectivity sets, connectedness, cut points, etc.

It may not have a standard name because it is the reflection of the decomposition/block number Stat56, i.e., for $\pi \in S_n$, $\text{Stat19}(\pi) = n - \text{Stat56}(\pi)$. See A059438. Another related statistic is global ascents Stat234.

For Q2, the connection between block numbers of 321-avoiding permutations and Catalan's triangle was established by Adin, Bagno, and Roichman, arXiv 1611.06979, later J. Algebraic Combinatorics. The related abstract for Bagno's talk at the Permutation Patterns 2017 conference is more expository.

$\endgroup$
1
$\begingroup$

For the first part of your question, support doesn't appear to be an appropriate word, as in the context of permutations it is normally used for the set of non-fixed points. In general, a mathematical support means as an assistance to the main act.

To try to define the term, we can first define the process that arrives at the statistic:

Let $T_n$ be the set of all non-trivial simple transpositions on a set of size $n$, say $S$.

Let $\pi$ be a permutation of $S$, and let $$\;_\pi T_n=\left\{\{t_1,\dots t_k\}\in T_n^k:\pi\prod_\limits{i=1}^k t_i=S\right\}$$

i.e. $\;_\pi T_n$ is the set of sets of simple transpositions that take $\pi$ to the identity $S$.

Define:

$$\;_\pi U_n(t\in \;_\pi T_n) =\{u:u\in t\}$$

as the set of unique elements of a set $t$, and

$$_\pi U_n=\bigcup_t \;_\pi U_n(t)$$

as the set of sets that contain the unique elements of simple transposition sets from $\;_\pi T_n$.

Define $\;_\pi V_n=\{|v|:v\in \;_\pi U_n\}$ and then the statistic we want is $\min(\;_\pi V_n)$.

So, minimum cardinality of the identifying simple transposition sets for a permutation $\pi$, or perhaps, the minimum number of simple transpositions needed to return $\pi$ to $S$.

The actual statistic can be easily calculated by creating an array of $n-1$, and ticking every cell that is crossed by returning an element in a straight path to it's original position, and counting the number of ticks, max 1 per cell.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.