# Is there a combinatorial interpretation of this triangle sequence? Is there a “simpler” formula?

Hi.

$$a_{n,k} = \sum_{1 = m_1 < m_2 < \cdots < m_k = n}\ \prod_{j=2}^k S(m_j, m_{j-1})$$.

where the $S(n, k)$ are Stirling numbers of the second kind. The triangle begins:

1,
0, 1,
0, 1, 3,
0, 1, 13, 18,
0, 1, 50, 205, 180,
...

Something very much like this is listed on oeis.org as "Triangle of coefficients from fractional iteration of $e^x - 1$" (and it is doing such fractional iteration that piques my interest in this sequence, and I got the formula while fiddling around with the one mentioned in my earlier question here: Is there a theory about these kinds of recurrence equations? Is this a known formula?). The two look to be identical except for possible indexing differences and the presence/absence of leading zeroes, but I don't have a proof (yet?).

Now, my questions are: does my $a_{n,k}$ have a combinatorial interpretation of some sort, and if so, what is it? Is there a "simpler" formula for it (i.e. one that does not involving summing over up to an exponential or worse amount of terms, even if it is not symbolically shorter)? And finally, is there a combinatorial interpretation of a product of Stirling numbers $S(m_2, m_1) S(m_3, m_2) \cdots S(m_k, m_{k-1})$ where $m_1 < m_2 < \cdots < m_k$, and if so, what is it?

-

There is the obvious combinatorial interpretation that follows from the definition of Stirling numbers: $a_{n,k}$ counts the number of ways you can take $n$ elements and partition them into some identical boxes, take those boxes and partition them into some identical boxes and so on $k$ times, in the end you use only one box. I'm not sure if this can help prove anything about the sequence combinatorially, though.

Edit: Actually there is a neat way to think about this interpretation in terms of trees. Let's call a rooted tree monotone if there are more vertices at depth $h+1$ than at $h$, for all $h$, and for which all leaves are at the same distance from the root. Then by the previous paragraph, $a_{n,k}$ counts the number of monotone rooted trees of depth $k$ with $n$ leaves. What follows below can also be phrased in terms of the corresponding combinatorial species, so if you think in terms of such trees you can prove these statements purely combinatorially.

Perhaps this can clarify the computational part of the question. Let $$F=\text{diag}(0!,1!,2!,\dots)$$ and let $$D(x)=(1,x,x^2,\dots)$$ also denote the Stirling matrix by $S=(p_{ij})_{i,j\geq 0}$, where $p_{ij}=S(i,j)$ if $i\geq j$ and $p_{ij}=0$ otherwise.

I might have my indexing off here but by looking at the (exponential) generating function of Stirling numbers the following is easy to check $$D(x)F^{-1}SF=D(e^x-1)$$ So that $$D(x)F^{-1}S^kF=D((e^x-1)^{(k)}),$$ where $f^{(k)}$ is $f$ composed $n$ times with itself. And the entries of the first column of $S^k$ are precisely the $a_{n,k}$ from which your statement that these are coefficients of the functional iterates of $e^x-1$, follows.

-
Thanks for the response. But when I mentioned about a "simpler formula" I was thinking more along the lines of the double-sum formula for Bernoulli numbers, the single-sum formula for Stirling numbers of the 2nd kind, sum formulas for the Stirling numbers of the 1st kind (the one that sums over the 2nd-kind Stirling numbers, that is), etc. I.e. involving a simple linear-indexed sum over n or n^2, etc. terms. Maybe with a product involved as well, but the total terms summed/producted should be like n, n^2, n^3, etc. (or otherwise polynomial), not a matrix formula like that one. –  mike3 Oct 25 '11 at 23:25

I just saw this question. If I'm not missing something, I think I have a quick answer to your question asking for a combinatorial interpretation for $a_{n,k}$.

Edit: I just realized that my answer is closely related to Gjergji's answer -- I hadn't read his closely enough before. But what I would add to his interpretation is that one may think of his recursive process as giving chains of a particular length in the partition lattice (as detailed below). So you might tap into the literature on the partition lattice.

This number seems to count the chains $\hat{0} = u_k < u_{k-1} < \cdots < u_1 < \hat{1}$ in the partition lattice $\Pi_n$, namely the poset of set partitions of {1,...,n} ordered by reverse refinement (i.e. with $u \le v$ iff $v$ is obtained from $u$ by merging blocks). I've indexed in reverse to align with your notation. Notice that going up a cover relation reduces the number of blocks by exactly one, so $S(n,n-j)$ counts poset elements of rank $j$. Once you choose $u_{k-1}$ of rank $j$, you might as well think of each block in $u_{k-1}$ as a letter, so that counting ways to go up from your chosen $u_{k-1}$ which has rank $j$ to any element $u_{k-2}$ of rank $j'$ satisfying $u_{k-1} < u_{k-2}$, you have $S(n-j,n-j')$ choices for this $u_{k-2}$, etc. Thus, your summands $1 = m_1 < \cdots < m_k = n$ are a choice of which ranks in the partition lattice to use for your chain, and then your products are progressively calculating the ways to choose the next element in a chain having the appropriate rank and above the lower elements of the chain, given the choices so far of lower elements in the chain. In particular, $S(m_j,m_{j-1})$ seems to count the choices for $u_{j-1}$ of rank $m_{j-1}$ once you have chosen the chain elements $u_k,\dots ,u_j$ that are all below it in the chain.

Hopefully I didn't mess up any indexing, but I easily could have. There is a large literature regarding the partition lattice, so maybe it's worth seeing what's been done with chain enumeration there.

-
Regarding the connection you mention to iterating $e^x-1$, you might figure out an explanation from looking at chapter 5 in Enumerative Combinatorics, Vol 2, section 5.1 (on exponentiating generating functions and a connection to set partitions). Now I'd better get off MO and get back to my own work. Good luck! –  Patricia Hersh Aug 20 '12 at 23:07
I just discovered that my answer comes full circle back to the answer my Ph.D. advisor gave you to a different question. Would you like me to delete my answer so you can focus more on trying to get fresh ideas (if you're still thinking about this question)? One comment is that the flag $h$-numbers are dimensions of $S_n$-representations, which is one way to see where your $(n-1)!$ is coming from -- a Lie character tensored with sign character. There's been a lot of study of these representations, which you could find by searching on "rank-selected homology" and "partition lattice". –  Patricia Hersh Aug 21 '12 at 17:02