Skip to main content
8 of 8
added 239 characters in body
JMP
  • 1.2k
  • 5
  • 13
  • 21

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.

JMP
  • 1.2k
  • 5
  • 13
  • 21