5
$\begingroup$

Let $\sigma=(1\;2)(3\;4)\cdots (n-1\; n)$ be a fixed-point-free involution in $S_{2n}$. I want to count permutations $\pi$ such that the group $\langle \pi,\sigma\rangle$ generated by $\pi$ and $\sigma$ is transitive on $\{1,...,2n\}$ and I want to do this according to the coset type of $\pi$ with respect to the hyperoctahedron subgroup $H_n\subset S_{2n}$ (the centralizer of $\sigma$). These coset types are labeled by partitions of $n$.

So I want $N(\lambda)$, the number of permutations $\pi$ of coset type $\lambda\vdash n$ such that $\langle \pi,\sigma\rangle$ is transitive.

The numbers I have obtained provide the following series (n=1,2,3,4 - partitions $\lambda$ in lexicographic order in the rows):

$$2$$ $$4, 16$$ $$16, 192, 384$$ $$96, 2304, 3840, 9216, 18432$$

Clearly the first element in each row is $2^n(n-1)!=2(2n-2)!!$.


Edit: Proof of the above statement. Suppose $\pi$ has coset type $(1^n)$ and $\langle \pi,\sigma\rangle$ is transitive. Take some initial number $i_1$. Then a) $\pi$ cannot map $i_1$ to itself, or having coset type $(1^n)$ would imply that $\pi$ also maps $\sigma(i_1)$ to itself and then transitivity would not hold;

b) $\pi$ cannot map $i_1$ to $\sigma(i_1)$, or having coset type $(1^n)$ would imply that $\pi$ also maps $\sigma(i_1)$ to $i_1$ and then transitivity would not hold;

c) so there are $(2n-2)$ possibilities for the image of $i_1$ under $\pi$, call this $i_2$;

d) the image of $i_2$ under $\pi$ cannot belong to $\{i_2,\sigma(i_2),i_1,\sigma(i_1)\}$, for the same reasons as above. So there are $(2n-4)$ possibilities for $\pi(i_2)=i_3$. And so on.

e) There are thus $(2n-2)(2n-4)\cdots=2^{n-1}(n-1)!$ possibilities for the list $[i_1,...,i_n]$. Finally, the image of $i_n$ can be either $i_1$ or $\sigma(i_1)$, which gives an extra factor of $2$.

End edit


Dividing every row of the triangle by $(2n-2)!!$, we get

$$2$$ $$2, 8$$ $$2, 24, 48$$ $$2, 48, 80, 192, 384$$

Now, second element seems to be $(2n)(2n-2)$ and last element seems to be $(2n)!!$

These numbers look very simple. Does anyone know of an explicit solution to this problem?

$\endgroup$
7
  • $\begingroup$ Maybe try to formulate things better. You're asking for a function from integers to integers (the number $p_n$ of those $\pi$ such that $\sigma,\pi$ generate a transitive subgroup on $2n$ elements), and then you're listing something which doesn't appear to just be a function from integers to integers... $\endgroup$
    – YCor
    Feb 3, 2018 at 17:33
  • $\begingroup$ @YCor It is not from integers to integers, because I am breaking down according to coset type. So it is a function from partitions to integers. $\endgroup$
    – thedude
    Feb 3, 2018 at 17:36
  • $\begingroup$ I've read your first sentence "I want to count permutations"... which is confusing. Please edit to clarify. $\endgroup$
    – YCor
    Feb 3, 2018 at 17:42
  • $\begingroup$ The coset set $S_{2n}/H_n$ has cardinal $\frac{(2n)!}{n!2^n}$; it identifies to the set of partitions of $2n$ elements into $n$ classes of cardinal 2. What is the the meaning of "coset type"? More precisely, given a partition $\lambda$ of $n$ and $\pi\in S_{2n}$, what do you mean by $\pi$ being of coset type $\lambda$? I'm not familiar with this vocabulary. $\endgroup$
    – YCor
    Feb 3, 2018 at 17:59
  • $\begingroup$ Ah, sorry about that. I didn't want to overburden the question with definitions. Coset type is defined in the classical book by MacDonald, or (very quickly) in section 2.1 of this paper: arxiv.org/pdf/1601.08206.pdf $\endgroup$
    – thedude
    Feb 3, 2018 at 18:08

2 Answers 2

3
$\begingroup$

Let $p_n$ be the number you're counting. Let $E'_n$ be the set of equivalences relations $\sim$ on $\{1,\dots,2n\}$ such that $2k-1\sim 2k$ for all $k$ (it can be identified the set of equivalence relations on $\{1,\dots,n\}$, which has $B_n$ elements, where $B_n$ is the $n$th Bell number). There's a mapping $\psi=\psi_{\{1,2,\dots,2n\}}:S_{2n}\to E'_n$ which maps $\pi$ to the orbit decomposition of the subgroup $\langle \sigma,\pi\rangle$. Your question consists in counting the cardinal of the fiber $\pi^{-1}(Z)$ of the equivalence relation with a single class $Z=\{1,\dots,2n\}^2$.

If $R$ is an equivalence relation on a set, let $c(R)$ be the set of classes of $R$. Then one can count elements of $S_{2n}$ according to their image by $\psi$. This yields: $$(2n)!=\sum_{R\in E'_n}|\psi^{-1}(R)|.$$ Now for $R$ with classes $C_1,\dots,C_k$, we can identify $\psi^{-1}(R)$ with $\prod_{i=1}^k\psi_{C_i}^{-1}(C_i^2)$. That is, an element of $\psi^{-1}(R)$ is determined by its restriction to each of the $C_i$, and each of these restriction should generate with $\sigma$ the transitive equivalence relation on $C_i$. Therefore $|\psi^{-1}(R)|=\prod_{i=1}^kp_{|C_i|/2}$, where $|\cdot|$ denotes the cardinal. This yields $$(2n)!=\sum_{R\in E'_n}\prod_{C\in c(R)}p_{|C|/2}=\sum_{R\in E_n}\prod_{C\in c(R)}p_{|C|}.$$ Thus we have the induction formula, denoting $E_n^*=E_n\smallsetminus\{\{1,\dots,n\}^2\}$, i.e., the set of equivalence relation with at least two classes:

$$p_n=(2n)!-\sum_{R\in E_n^*}\prod_{C\in c(R)}p_{|C|}.$$

On can gather terms in terms of the partition types. For this, denote $Y_n$ the set of partitions of $n$, that is, the set of finite sequences $q=(q_1,\dots,q_k)$ where $k$ ranges over nonnegative integers, $q_1\ge q_2\ge\dots q_k\ge 1$ and $\sum_{i=1}^kq_i=n$. Write $Y_n^*$ being $Y_n$ minus the partition $(n)$ into a single component. For $q\in Y_n$, write $q!=\prod_{i=1}^k q_i!$, $q¡=\prod_jq'_j!$, where $q'_j$ is the cardinal of $\{i\le k: q_i=j\}$. Thus the number of equivalence relations defining a partition of type $q$ is $n!/(q!q¡)$.

$$p_n=(2n)!-\sum_{q\in Y_n^*}\frac{n!}{q!q¡}\prod_{i=1}^kp_{q_i},$$ which rewrites as

$$\frac{p_n}{n!}=\frac{(2n)!}{n!}-\sum_{q\in Y_n^*}\frac1{q¡}\prod_{i=1}^k\frac{p_{q_i}}{q_i!}.$$

$\endgroup$
4
  • $\begingroup$ PS the first few terms of $p_n/(2^n(n-1)!)$, $n\ge 1$, according to the OP's post (just summing the rows of the second triangle) are 1, 5, 37, 353. Or equivalently $((2n)!-p_n)//(2^n(n-1)!)$ is given by 0, 1, 8, 67. I found both sequences in Sloane with 2 solutions and extrapolation to $n=5$ gives 4 possible candidates for $p_5/2^54!=p_5/768$: 4081, 4123, 4165, 4315. If anyone has something to run an easy program and compute the genuine value of $p_5/768$, it would be useful! $\endgroup$
    – YCor
    Feb 3, 2018 at 18:43
  • $\begingroup$ Your solution predicts $p_5/768=4081$ and it looks perfectly correct to me. Sadly, I don't see how to refine it to account for coset type. $\endgroup$
    – thedude
    Feb 3, 2018 at 18:58
  • $\begingroup$ I have no claim about the refinement! Thanks for the computation; then $p_n/(2^n(n-1)!)$ is very likely to be given by oeis.org/A004208 (I have checked in addition that the 6th term $p_6/7680=55205$ matches). Interestingly, the Sloane definition does not refer to permutations. $\endgroup$
    – YCor
    Feb 3, 2018 at 21:46
  • $\begingroup$ That sequence does not refer to permutations, but sequence oeis.org/A000698, which is twice that, is said to be "the number of indecomposable perfect matchings on [2n]", which seems related $\endgroup$
    – thedude
    Feb 4, 2018 at 19:11
1
+50
$\begingroup$

I think the case when the coset type of $\pi$ is $(n)$ can also be treated in the way you treated coset type $(1^n)$.

Namely, take some $i_1$. Its image under $\pi$, call it $i_2$, can be anything, so $2n$ possibilities.

The image of $\sigma(i_1)$ cannot be $i_2$ nor $\sigma(i_2)$, on account of the coset type, so $(2n-2)$ possibilities.

The next step is similar, just replacing $n\to n-1$.

The orbit of $i_1$ under $\pi$ will then lead to $(2n)!!$ while the orbit of $\sigma(i_1)$ will lead to $(2n-2)!!$.

Total number is $(2n)!!(2n-2)!!$ as you have.

$\endgroup$

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.