# Counting transitive generators according to coset type

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?

• 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... – YCor Feb 3 '18 at 17:33
• @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. – thedude Feb 3 '18 at 17:36
• I've read your first sentence "I want to count permutations"... which is confusing. Please edit to clarify. – YCor Feb 3 '18 at 17:42
• 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. – YCor Feb 3 '18 at 17:59
• 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 – thedude Feb 3 '18 at 18:08

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!}.$$

• 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! – YCor Feb 3 '18 at 18:43
• 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. – thedude Feb 3 '18 at 18:58
• 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. – YCor Feb 3 '18 at 21:46
• 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 – thedude Feb 4 '18 at 19:11

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.