Is there a combinatorial interpretation of this triangle sequence? Is there a "simpler" formula? - MathOverflow

Is there a combinatorial interpretation of this triangle sequence? Is there a "simpler" formula?

2011-10-15T22:59:46Z

Hi.

I was wondering about this. I've got this triangle sequence:

`$$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: http://mathoverflow.net/questions/64450/is-there-a-theory-about-these-kinds-of-recurrence-equations-is-this-a-known-form). 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?

Answer by Gjergji Zaimi for Is there a combinatorial interpretation of this triangle sequence? Is there a "simpler" formula?

2011-10-15T23:54:55Z

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.

Answer by Patricia Hersh for Is there a combinatorial interpretation of this triangle sequence? Is there a "simpler" formula?

2012-08-20T21:44:45Z

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.