Is there a combinatorial interpretation of this array in terms of $S_{2n+1}$?

Question

I have recently encountered a triangular array $(a_{i,j})_{0\le i\le j}$, each line of which might (should?) have a combinatorial interpretation in terms of $S_{2n+1}$. Here it is (the first entry of each line is the label $2n+1$, and the first $1$ on the right is $a_{0,0}$):

1  |   1         
3  |   2           4 
5  |   24          80           16 
7  |   720         3136         1120         64 
9  |   40320       209408       102144       10752           256 
11 |   3628800     21441024     12869120     1892352         84480       1024 
13 |   479001600   3130103808   2188865536   402980864       25479168    585728      4096 
15 |   87178291200 618377527296 487356047360 105995681792    8484270080  278806528   3727360   16384

Since the entries in each line sum to $(2n+1)!$, I would expect these entries to correspond to certain subsets of $S_{2n+1}$. In particular $a_{n,0}=(2n)!$, which should naturally correspond to a subgroup $S_{2n}$. Further we have for example $$a_{n,n}=2^{2n};\ a_{n,n-1}=2^{2n-1}\binom {2n+1}3;\ a_{n,n-2}=2^{2n-1}\Bigl[2n\binom {2n+1}5-\binom {2n+2}6\Bigr].$$ If ever there is a combinatorial interpretation, it must be independent of the conjugacy classes, as e.g. in $S_7$, no classes could constitute $a_{3,3}=64$.

My goal is of course to find a direct formula (or a recursion formula) for these numbers. Note that $a_{n,1}$ can have big prime factors, e.g. $ a_{13,1}=3130103808=2^{11}×3^2×13×13063$.

An intriguing feature is that we can "interpolate" between the lines, more precisely between the diagonals, i.e. try to decompose $(2n)!$ similarly as $b_{n,0}+\cdots+b_{n,n}$ with the $b_{i,j}$ obeying the same formulas as the $a_{i,j}$, just with $2n$ instead of $2n+1$. But then it turns out that the row sums would be $(2n)!+(2n-1)!$, meaning that, if we look again for an interpretation in terms of $S_{2n}$, we'd have to disconsider the column $b_{n,0}$, as this gives just the 'superfluous' $(2n-1)!$ contribution. But this being said: why not? (And who knows, it might even give a hint towards coming up with a common interpretation combining even and odd rows.)

The first even rows would be logically

2  |     (1)         2 
4  |     (6)         16           8 
6  |     (120)       368          320        32 
8  |     (5040)      16896        19712      3584        128 

Answer 1

You can use https://www.findstat.org to obtain a candidate for a conjectural solution, see https://www.findstat.org/StatisticsDatabase/St000389oMp00093oMp00127oMp00066oMp00090 for details:

after adding 1 to every value
and applying
    Mp00090: cycle-as-one-line notation: Permutations -> Permutations
    Mp00066: inverse: Permutations -> Permutations
    Mp00127: left-to-right-maxima to Dyck path: Permutations -> Dyck paths
    Mp00093: to binary word: Dyck paths -> Binary words
to the objects (see `.compound_map()` for details)

your input matches
    St000389: The number of runs of ones of odd length in a binary word.

I did check the first few generating polynomials. From the definition of the map, it is easy to see that the leading term is $2^{n-1}$, the number of compositions of $n$. Since the first map sorts the cycles by their minimal elements, its image starts with $1$, which implies that the first ascent of the Dyck path has length one. Thus, the constant terms of the generating polynomials vanish. The linear terms vanish for even $n$, because there is no Dyck path of semilength $n$ with a single odd ascent.

1
q
2*q^2
4*q^3 + 2*q
8*q^4 + 16*q^2
16*q^5 + 80*q^3 + 24*q
32*q^6 + 320*q^4 + 368*q^2
64*q^7 + 1120*q^5 + 3136*q^3 + 720*q
128*q^8 + 3584*q^6 + 19712*q^4 + 16896*q^2
256*q^9 + 10752*q^7 + 102144*q^5 + 209408*q^3 + 40320*q
512*q^10 + 30720*q^8 + 462336*q^6 + 1838080*q^4 + 1297152*q^2
1024*q^11 + 84480*q^9 + 1892352*q^7 + 12869120*q^5 + 21441024*q^3 + 3628800*q

Answer 2

In fact, the oeis does help more than that. While it doesn't contain the array in question, it has a proportional one. First, we'll interlace the even and odd rows and so define $(c_{i,j})_{1\le j\le i}$ by$$c_{i,j}=\begin{cases} a_{\frac {i-1}2,\,j-1}& \text{for $i$ odd} \\b_{\frac i2,\,j-1}& \text{for $i$ even,}\end{cases}$$ then divide the row $c_{n,\cdot}$ by their gcd, which is the largest power of 2 which divides $n!$ (or, equivalently, divide the row by $n!$ and and consider the numerators when writing it over the least common denominator, which is the largest odd divisor of $n!$). It now suffices to insert $0$'s at every other place, and we have the triangle A064984. Bingo!

Note that the oeis gives a recursion formula for the corresponding polynomials, though it seems hard to get explicit formulas from that.

Fortunately, I found that only now, otherwise I would never have asked this whole question, missing out on the nice answer and comments of Martin Rubey and, I guess, Timothy Budd first!

To find that, I was lucky by searching the oeis for 83754 and 50270, numbers corresponding to two entries of the row $c_{11,\cdot}$ which are just big enough to yield essentially unique search results. In fact, the 3 other upcoming oeis sequences do not contain those numbers themselves, but are based on the (more or less) same polynomials for the $11^{th}$ row, featuring generating functions $\frac {(1 + x)^{10} }{ (1 - x)^{11}}$ for A008421 and $\frac {x(1 + x)^{10} }{ (1 - x)^{12}}$ for A035605 and A300624 (which differ just by a factor of $2$). And there we recover something close to the bivariate generating function $\frac{1}{2}\bigl(\frac{1+x}{1-x}\bigr)^y$.