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 

```


Is there a combinatorial interpretation of this array in terms of $S_{2n+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

```

