2
$\begingroup$

I was doing some counting in $S_n$ symmetric group I encountered the following problem, which also someway related to central factorial number. So given a $n$ cycle say $(1,2,\ldots,n)$, what are the monotonic 2 -tuples, of the form $(a,b)(c,d)$, monotonicity in on the 2nd coordinate that is $b<d$ such that. By default transposition $(a,b)$ imply $a<b$.

$$(1,2,\ldots,n)(a,b)(c,d)=\, \text{is still a $n$ cycle } $$ I have succesfully answer the question that is that is having chosen $a,b ,d$, $c\in [a,b)$ that is c can take the value $a$ and all the integer between $a$ and $b$ not $b$.

Let me give you an example say, let's take the 3 cycles $(1,2,3)$ then say you give me $(1,3)(c,3)$ then $ 1\leq c <3$ are the tuples that multiply with $(1,2,3)$ gives back 3 cycle. For this case there are only two other choice $(1,2)(1,3)$ and $(1,2)(1,2)$. This work for all $n$ cycle. Now question start from here. Say I am given an arbitrary $n$ cycle say what would the above classification look like? I still want my cycle to be monotonic in 2 nds coordinate. Let me give some examples to make my problem explicit.

Say I have been given a 4 cycle $(1,4,2,3)$. Now I want to find all the tuples $\{(a,b)(c,d)\mid b\leq d\}$ such that it multiplies to give back the 4 cycles.

To start with we have $( 1,4 )(c,4)$ what should the condition we put on $c$? The cycle $(1,4)(2,4)$ is not answer as it multiply to give a cycle of type $(2,1,1)$.

The natural thing that comes to my mind is there is something to do with the order of the integer. In the first natural cycle, we have the natural order $1 < 2 < 3 < 4$.

For the cycle in example say we attempt to put an order $1<4<2<3 $ these order only for the first coordinates to give conditions for monotonic tuples to give back $n$ cycles. With this order in mind, I can create the following tuples $(2,4)(3,4)$ which when multiplied give back 4 cycles. This also explains why $(1,4)(2,4)$ is not an example as in the above order 2 is greater than 4 hence it's not an answer. Is this can be generalised? Or I am doing something that can be explained nicer more mathematically?

$\endgroup$

1 Answer 1

2
$\begingroup$

EDITED. If we represent a given cycle as a circle with $n$ vertices, and transpositions $(a,b)$ with $a<b$ and $(c,d)$ with $c<d$ as chords in this circle, then their product is a cycle if and only if

  • the chords cross; or
  • coincide, i.e. $(a,b)=(c,d)$; or
  • one of $c,d$ equals $a$ and the other is clockwise strictly in between $b$ and $a$; or
  • one of $c,d$ equals $b$ and the other is clockwise strictly in between $a$ and $b$.

Example. A cycle $(1,8,4,7,2,5,3,6)$ and $(a,b)=(4,6)$ have graphical representation:

enter image description here

Then for $(c,d)$ with $d\geq b=6$ we have the following options:

  • $c\in\{1,6\}$ and $d=7$;
  • $c\in\{2,3,4,5\}$ and $d\in\{6,8\}$;
  • $c=7$ and $d=8$.

ADDED. It can be shown that independently of a given cycle of length $n$ the total number of pairs of transpositions $(a,b)$, $(c,d)$ with $a<b$, $c<d$, and $b\leq d$ equals $\binom{n+2}{4}$.

$\endgroup$
23
  • $\begingroup$ I didn't get it, so the tuples must me $(a ,b)(c,d)$ where $b\leq d$ it's always $a<b$ and $c<d$ as in transposition. I gave the condition on $c$ so I guess you want to say something about $\pi_c$? $\endgroup$
    – GGT
    Mar 2, 2022 at 21:40
  • $\begingroup$ As I want monotonic sequence $b,d$ are fixed like $(a,2)(c,3)$ or $(a,2)(c,2)$ so on, we cannot change the position $b,d$ $\endgroup$
    – GGT
    Mar 2, 2022 at 22:43
  • $\begingroup$ In the case of 4 cycles all possible things are $(a,4)(c,4)$, $(a,3)(c,4)$, $(a,2)(c,4)$, $(a,3)(c,3)$, $(a,2)(c,3)$ and we need to fill in condition of $a,c$ $\endgroup$
    – GGT
    Mar 2, 2022 at 23:08
  • $\begingroup$ A transposition in a symmetric group given by $(a,b)$ always implied $a<b$. Maybe I should add it, as I thought it's universal. Yes $a< b \leq d$ also $c<d$ hold by default. $\endgroup$
    – GGT
    Mar 3, 2022 at 1:33
  • 1
    $\begingroup$ Hi Max, I posted mathoverflow.net/questions/428503/… $\endgroup$
    – GGT
    Sep 3, 2022 at 2:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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