6
$\begingroup$

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 
$\endgroup$
11
  • 2
    $\begingroup$ Where did this originally come up? $\endgroup$
    – Bma
    Dec 27, 2021 at 21:41
  • 1
    $\begingroup$ @Bma the numbers are somewhat related to the integrals $\int\limits_0^\infty\dfrac{\tanh^n(x)}{x^m}dx$, see here mathoverflow.net/questions/271526/…. $\endgroup$
    – Wolfgang
    Dec 28, 2021 at 8:31
  • 3
    $\begingroup$ The bivariate generating function seems to be given by $\sum_{n,m\geq 0} \frac{a_{n,m}}{(2n+1)!} x^{2n+1}y^{2m+1} = \frac{1}{2} \sinh(2 y \operatorname{arctanh} x)$. Or was this the origin of your numbers? $\endgroup$ Dec 28, 2021 at 11:47
  • 1
    $\begingroup$ @TimothyBudd, and the even part is $\frac{1}{2}\cosh(2y\,\mathrm{arctanh} x)$, so in total we obtain $\frac{1}{2}\exp(2y\,\mathrm{arctanh} x)$. $\endgroup$ Dec 28, 2021 at 13:59
  • 1
    $\begingroup$ It should be possible to interpret this generating function combinatorially, by rewriting it as $\frac{1}{2}\exp\left(y\log\frac{1+x}{1-x}\right)$. The term $\log\frac{1+x}{1-x}$ is the generating function for cycles of odd length, either blue or red, so in total we get 'permutations' with all cycles of odd length, and each cycle coloured blue or red, up to swapping colours. Each cycle has weight $y$. $\endgroup$ Dec 28, 2021 at 14:29

2 Answers 2

9
$\begingroup$

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
$\endgroup$
3
  • $\begingroup$ Does the interpretation "the number of runs of ones of odd length in a binary word" have an interpretation in terms of subsets of $S_{2n + 1}$? $\endgroup$
    – LSpice
    Dec 28, 2021 at 0:04
  • $\begingroup$ Thank you so much! The oeis is often helpful; but it is good to know there is much more around. And such a nice generating function, just $\frac{1}{2}\left(\frac{1+x}{1-x}\right)^y$. $\endgroup$
    – Wolfgang
    Dec 28, 2021 at 15:01
  • 1
    $\begingroup$ I just found that these polynomials are in fact well known: multiply them by 2, and we get the Mittag-Leffler Polynomials. Now an OEIS search comes up with more info about them, e.g. hidden in the comment section of oeis.org/A142983. $\endgroup$
    – Wolfgang
    Jan 4, 2022 at 15:09
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ And fortunately I didn't insert a comma in the oeis search, otherwise it wouldn't have worked because of the $0$'s! $\endgroup$
    – Wolfgang
    Dec 30, 2021 at 15:46

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.