# Thread: A "permutation-counting" problem

1. ## A "permutation-counting" problem

Hello,

I have been struggling in vain to solve this problem for a while, here it is:

Let E be a finite set of cardinal n, p a natural integer. Let S(E) be the group of permutations of E.
Let $\displaystyle \psi \in S(E)$. Find : The problem is quite easy if you remove the 'switching' hypothesis between all $\displaystyle s_i$, you get $\displaystyle n!^{p-1}$.
But here, I don't know where to begin.

Thanks a lot in advance for your help.

3. ## Re: A "permutation-counting" problem

Of course. I apologise, I'm not used to writing math in English…

I meant by 'switching hypothesis' the fact that the permutations of the tuple must commute two-by-two (which corresponds to the second condition). I have the feeling that when n gets big, this hypothesis sharply reduces the cardinal -- but again, without ideas about how to prove it.

I hope it sheds light on the problem a bit.

4. ## Re: A "permutation-counting" problem Originally Posted by Jeze Of course. I apologise, I'm not used to writing math in English…

I meant by 'switching hypothesis' the fact that the permutations of the tuple must commute two-by-two (which corresponds to the second condition). I have the feeling that when n gets big, this hypothesis sharply reduces the cardinal -- but again, without ideas about how to prove it.

I hope it sheds light on the problem a bit.
Yes, I updated my response.

5. ## Re: A "permutation-counting" problem

I get that

$\displaystyle \forall i,\, s_i \in \left (\bigcap_{j}C(s_j)\cap C(\psi ) \right )$

where C(.) is the centralizer.

Apart from that...

6. ## Re: A "permutation-counting" problem

Because the centralizer of a subset of a group is itself a subgroup, $\psi$ must be in $C(\{a_1,\ldots , a_p\})$. Basically, you are taking arbitrary elements of $C(\psi)$. You have a choice for the first $p-1$ permutations. Can you say it is

$$|C(\psi)|^{p-1}$$

I am not sure about that.

7. ## Re: A "permutation-counting" problem Originally Posted by SlipEternal Because the centralizer of a subset of a group is itself a subgroup, $\psi$ must be in $C(\{a_1,\ldots , a_p\})$. Basically, you are taking arbitrary elements of $C(\psi)$. You have a choice for the first $p-1$ permutations. Can you say it is

$$|C(\psi)|^{p-1}$$

I am not sure about that.
I do not think I can help with getting the exact count, but a range is definitely possible.

$$|Z(S(E))|^{p-1} \le \left| \left\{ (s_1,\ldots , s_p) \in S(E)^p \mid \begin{cases}s_1\circ \cdots \circ s_p = \psi \\ \forall i,j \in [p], i\neq j \Longrightarrow s_i \circ s_j = s_j \circ s_i\end{cases} \right\} \right| \le |C(\psi)|^{p-1}$$

8. ## Re: A "permutation-counting" problem

Hello,

Thank you very much for your thoughts.
How do you couch it, for the range?

I have been trying to outline a bijection that would work, something like (F is our set) :

$\displaystyle C(\psi )^{p-1}\rightarrow F$

$\displaystyle (a_2,...,a_p) \mapsto (\psi ,a_2\circ \psi ,a_2^{-1}\circ a_3\circ \psi ,...,a_{\left \lfloor \frac{p}{2} \right \rfloor-1}^{-1}\circ a_{\left \lfloor \frac{p}{2} \right \rfloor}\circ \psi ,a_{\left \lfloor \frac{p}{2} \right \rfloor}^{-1}\circ a_{\left \lfloor \frac{p}{2} \right \rfloor+1}\circ \psi ^{-1},...,a_{p}^{-1})$

(the count must not be valid but just to give an idea)

Problem is, they have to commute...

9. ## Re: A "permutation-counting" problem Originally Posted by Jeze Hello,

Thank you very much for your thoughts.
How do you couch it, for the range?

I have been trying to outline a bijection that would work, something like (F is our set) :

$\displaystyle C(\psi )^{p-1}\rightarrow F$

$\displaystyle (a_2,...,a_p) \mapsto (\psi ,a_2\circ \psi ,a_2^{-1}\circ a_3\circ \psi ,...,a_{\left \lfloor \frac{p}{2} \right \rfloor-1}^{-1}\circ a_{\left \lfloor \frac{p}{2} \right \rfloor}\circ \psi ,a_{\left \lfloor \frac{p}{2} \right \rfloor}^{-1}\circ a_{\left \lfloor \frac{p}{2} \right \rfloor+1}\circ \psi ^{-1},...,a_{p}^{-1})$

(the count must not be valid but just to give an idea)

Problem is, they have to commute...
Perhaps this is a translation issue. What does "How do you couch it, for the range" mean? But, I agree, this appears to be a fairly non-trivial problem for general groups.

Perhaps there are simplifications for the symmetric group that make it easier to calculate. I would start with small symmetric groups (try $S_3, S_4, S_5$) and see if you can recognize any patterns.

10. ## Re: A "permutation-counting" problem

I meant 'how do you justify it properly'?

Ok, I'll take a closer look.