Results 1 to 10 of 10
Like Tree1Thanks
  • 1 Post By SlipEternal

Thread: A "permutation-counting" problem

  1. #1
    Newbie
    Joined
    Jul 2018
    From
    France
    Posts
    7

    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 :

    A "permutation-counting" problem-44.gif

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,523
    Thanks
    1401

    Re: A "permutation-counting" problem

    Last edited by SlipEternal; Jul 11th 2018 at 10:02 AM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2018
    From
    France
    Posts
    7

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,523
    Thanks
    1401

    Re: A "permutation-counting" problem

    Quote Originally Posted by Jeze View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2018
    From
    France
    Posts
    7

    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...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,523
    Thanks
    1401

    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.
    Last edited by SlipEternal; Jul 11th 2018 at 05:03 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,523
    Thanks
    1401

    Re: A "permutation-counting" problem

    Quote Originally Posted by SlipEternal View Post
    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}$$
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Jul 2018
    From
    France
    Posts
    7

    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...
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,523
    Thanks
    1401

    Re: A "permutation-counting" problem

    Quote Originally Posted by Jeze View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Jul 2018
    From
    France
    Posts
    7

    Re: A "permutation-counting" problem

    I meant 'how do you justify it properly'?

    Ok, I'll take a closer look.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Jun 11th 2015, 07:16 AM
  2. Replies: 2
    Last Post: Aug 6th 2011, 03:00 PM
  3. Replies: 2
    Last Post: Apr 24th 2011, 07:01 AM
  4. Replies: 1
    Last Post: Oct 25th 2010, 04:45 AM
  5. "Counting problem"
    Posted in the Statistics Forum
    Replies: 1
    Last Post: May 30th 2008, 01:53 PM

/mathhelpforum @mathhelpforum