Timeline for A combinatorial interpretation for $n$-ary trees for negative $n$
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 22, 2023 at 14:28 | comment | added | Pedro | @VladimirDotsenko I suppose one wants some (twisted) associative algebra Koszul duality phenomenon here, even though $T_n$ and its recursion is clearly operadic in nature. | |
| Mar 13, 2023 at 8:29 | comment | added | Alexander Burstein | @TomCopeland Yes, but this is the un-aerated version. Given the functional equation, it is easy to see that $T_{-n}(x)=\frac{1}{T_{n+1}(-x)}=1+xT_{n+1}^n(-x)$, so as as Ira points out in his answer, it is easier to interpret $U_n(x)=1-T_{-n}(-x)=xT_{n+1}^n(x)$. So, what you are asking for (sequences for $T_n(x)$ when $n=3$ and $n=-3$) are, respectively, A001764 and the alternating-sign version of A006632 with $1$ prepended ($1,1,-3,15,-91,612,-4389,32890,\dots$). | |
| Mar 9, 2023 at 17:43 | comment | added | Alexander Burstein | @TomCopeland Could you leave a link to it here? Thanks. | |
| Mar 4, 2023 at 21:13 | vote | accept | Alexander Burstein | ||
| Mar 4, 2023 at 20:49 | comment | added | Alexander Burstein | @TomCopeland Thanks for checking it out. Actually, the place where this comes up in that paper is the discussion on p. 43 after Ex. 51 and 52. | |
| Mar 4, 2023 at 6:24 | answer | added | Ira Gessel | timeline score: 12 | |
| Mar 4, 2023 at 0:18 | comment | added | Ira Gessel | From oeis.org/A333829 we can infer that the coefficient of $x^m$ in $T_n(x)$, which is $\frac{1}{mn+1}\binom{mn+1}{m}$, is the Ehrhart polynomial for the $n$-dimensional polytope which is the convex hull of length $n+1$ nondecreasing parking functions. I haven't checked this and don't know of a reference, nor do I know why this Ehrhart polynomial also counts trees. But if this all checks out, the reciprocity theorem for Ehrhart polynomials might help with a combinatorial explanation. | |
| Mar 1, 2023 at 20:43 | comment | added | Alexander Burstein | @TomCopeland Thank you for this valuable advice. | |
| Mar 1, 2023 at 16:55 | answer | added | Tom Copeland | timeline score: 7 | |
| Feb 27, 2023 at 21:16 | comment | added | Timothy Chow | @BrendanMcKay Even in one of the most basic examples of combinatorial reciprocity, namely taking $n=-1$ in the chromatic polynomial to get acyclic orientations, we get negative numbers and have to take absolute values. | |
| Feb 27, 2023 at 19:40 | comment | added | Sam Hopkins | Nevermind, writing $T_n(x) = \sum_{m \geq 0} t_{n,m} x^m$, my comments were more about extending to negative values of $m$, but as you say you are interested in negative values of $n$. | |
| Feb 27, 2023 at 16:11 | comment | added | Alexander Burstein | @SamHopkins On the left, there is just the function itself. On the right, it appears raised to the degree equal to its index. | |
| Feb 27, 2023 at 15:32 | comment | added | Peter Taylor | @BrendanMcKay, there are a couple of combinatorial interpretations if we take absolute values. Consider (directed and ordered) trees of unbounded valency but such that every non-leaf vertex has exactly $k$ leaf children. There's a special case in the tree with one vertex. Otherwise all such trees have a multiple of $(k+1)$ vertices. The g.f. ignoring the special case satisfies $L_k(x) = 1 + x^{k+1} \sum_{j \ge 0} \binom{j+k}{k} (L_k(x) - 1)^j$. We seem to have $L_k(x) = 1 + x^{k+1} T_{k+2}^{k+1}(x^{k+1}) = 2-T_{-k-1}(-x^{k+1})$. | |
| Feb 27, 2023 at 13:27 | comment | added | Brendan McKay | Doesn't seem to have non-negative coefficients, so unfortunately it doesn't count things in a simple way. | |
| Feb 27, 2023 at 13:00 | comment | added | Sam Hopkins | It looks like you're aiming for a combinatorial reciprocity result. Stanley studies reciprocity for differentially finite power series in: math.mit.edu/~rstan/pubs/pubfiles/45.pdf. Of course, algebraic power series are a subset of differentially finite, but I'm not sure if the method of "extending to negatives" is the same as what you've done here. | |
| Feb 27, 2023 at 11:24 | comment | added | Vladimir Dotsenko | What an interesting observation! I came across some sort of similar situations where this sort of behaviour ($n$ replaced by $1-n$, and at the same time, $x$ replaced by $-x$ in the generating function; THAT is a key hint) was a manifestation of Koszul duality for some algebraic objects. I'll definitely try to think about your observation with this in mind... | |
| Feb 27, 2023 at 11:16 | history | asked | Alexander Burstein | CC BY-SA 4.0 |