I was working on a combinatorics problem that arose from one of my mathematical excursions, and the final formula includes numbers from a sequence that I've never encountered before: https://oeis.org/A080416
The sequence is actually a number triangle, which looks like this:
$$1 \\
1,1 \\
1,4,1 \\
1,12,10,1 \\
1,32,67,20,1 \\
1, 80, 376, 252, 35, 1 \\
…$$
My goal is to find a closed form formula (not a generating function) for the number triangle $a(n,k)$, but I don't even understand how this sequence is formed.
I understand the "paired decomposition of tetrahedral numbers" part of the derivation. Basically, tetrahedral numbers can be decomposed in the following way:
$$\begin{array}{ l l }
\text{Tet}(1) = 1: & 1 \\
\text{Tet}(2) = 4: & 2+2 \\
\text{Tet}(3) = 10: & 3+4+3 \\
\text{Tet}(4) = 20: & 4+6+6+4 \\
\text{Tet}(5) = 35: & 5+8+9+8+5
\end{array}$$
In general, a tetrahedral number can be decomposed as such:
$$\text{Tet}(n)=\sum_{k=1}^n k(n-k+1)$$
Then, the OEIS page states that once we decompose the tetrahedral numbers in this fashion, we can arrive at the goal number triangle by a Stirling-like process (whatever that's supposed to mean). I can't figure out what the process is, and thus how to find the closed form (if it even exists).
Any help would be appreciated.
UPDATE:
I found a heuristic algorithm for computing the rows of the number triangle. For example, take the 5th row of the number triangle (1 32 67 20 1). It can be calculated like this:
STEP 1: list the specific combinations of $4 \choose 1$ as such:
oxxx, xoxx, xxox, xxxo
Now, take the paired decomposition of the 4th tetrahedral number (here: 4 6 6 4) and assign these integers to the four respective slots in the diagram above. Whenever o is at a specific slot, that's the value of the combination. Finally, sum the values of all combinations together. $4+6+6+4=20$.
STEP 2: now, list the combinations of $4\choose 2$:
ooxx, oxox, oxxo, xoox, xoxo, xxoo
Take the paired decompositon of the 3rd tetrahedral number (here: 3 4 3). This time each combination will have a slightly different (more general) numbering scheme of slots. Start with a $3$ (the first number in the paired decomposition) on the left. Whenever you encounter an "o", repeat the number assigned to that slot for the next slot. Whenever you encounter an "x" simply continue parsing through the paired decomposition. The value of a combination will be the multiplication of all slot values where an "o" occurs.
For example: ooxx will have a value of $3\cdot 3=9$ because we start numbering the slots with a $3$. Then we repeat the $3$ for the second slot because we had an "o". So the values of individual slots are $3,3,4,3$. The first two slots have the "o"s so the value of the combination is $3\cdot 3=9$.
Another example: xoox will have a value of $4\cdot 4=16$ because we start numbering with a $3$. Then we go to next number in the decomposition sequence ($4$) because we have an "x". But we have an "o" in the second slot, so the value of the third slot is 4 as well. So the values of the individual slots in order are $3,4,4,3$ and we have "o"s in the middle two positions, so the value of the combination is $4\cdot 4=16$.
We do this for the rest of the combinations, and sum the values of all of the combinations, resulting in $9+12+9+16+12+9$ (respectively), which is $67$.
STEP 3: now, list the combinations of $4\choose 3$:
ooox, ooxo, oxoo, xooo
Repeat the same procedure for numbering slots, but this time with the decomposition of the 2nd tetrahedral number (here: 2 2). The values of each combination end up being $8,8,8,8$ respectively ($2^3$ in each case). Finally, sum all of the combination values to end up with $8+8+8+8=32$.
FINAL STEP: take all of the sums from all of the steps, and arrange them in the reverse order. So here, $32, 67, 20$. Notice how these are the three non-trivial entries of the 5th row of the desired number triangle.
You can generalize this algorithm to generate any $n$th row by simply listing the combinations of $n-1\choose k$ in each $k$th step, numbering the slots using the paired decomposition of $(n-k)$th tetrahedral number, finding the values of each combination by multiplying the values of slots with "o"s, and finally summing the values of each combination for that step. The sums in reverse order will spell out the $n$th row of the triangle.
Note that I ommited steps $0$ and $n-1$ as they will always trivially sum to $1$ (multiplication over the empty set in the $0$th step and multiplication of $n-1$ ones in the last step).
Also note that I have no idea why this algorithm generates the number triangle, I just found it by using very messy heuristic logic. I still need help in arriving at the final closed form formula for the sequence, and trying to derive the Stirling-like process that the author of the OEIS page had in mind.
Best Answer
This triangular sequence is the sequence $S_b(n,k)$ defined in the paper Dually weighted Stirling-type sequences by Corcino et al., which is cited from A080251. The algorithm described in the question is a combinatorial way of taking the coefficient of $x^n$ in the series $$ \sum_{n \ge k} S_b(n,k)x^n = \frac{x^k}{(1 - T_{k-2,0}x) (1 - T_{k-2,1}x) \cdots (1 - T_{k-2,k-2}x)} $$ where $T_{k,j}$ is sequence A080251 in the OEIS. (This is equation (4) in the paper; in their equation, the product in the denominator goes up to $(1 - T_{k-2,k}x)$, but I'm not sure why, since $T_{k-2,k-1}=T_{k-2,k} = 0$.)
I think the recurrence relations in the next section of the paper are a more helpful way to compute this sequence. They are defined in terms of a more general sequence $S_{\alpha,\beta}^{\mathcal V}[n,k]$, whose every value is a polynomial in variables $v_0, v_1, v_2, \dots$ and $w_0, w_2, w_2, \dots$. We can recover our sequence $S_b(n,k)$ by setting $v_i = w_i = i$ for all $i$, and $\alpha = \beta = 0$.
After doing some simplification, here is a three-variable recursive relation for the sequence we want. Let $s(\beta,n,k)$ - the notation is mine, not the paper's - be defined by recurrence relation $$ s(\beta, n, k) = \begin{cases} 1 & n=k=0 \\ 0 & n=0 \text{ xor } k=0 \\ s(\beta+1, n-1,k-1) + \beta \cdot k \cdot s(\beta, n-1, k) & \text{otherwise}. \end{cases} $$
Then the triangle in A080416 is given by $s(0,n,k)$, with some re-indexing:
$$ \begin{matrix} s(0,2,2) & & & & \\ s(0,3,2) & s(0,3,3) & & & \\ s(0,4,2) & s(0,4,3) & s(0,4,4) & & \\ s(0,5,2) & s(0,5,3) & s(0,5,4) & s(0,5,5) & \\ s(0,6,2) & s(0,6,3) & s(0,6,4) & s(0,6,5) & s(0,6,6) \\ \end{matrix} = \begin{matrix} 1 & & & & \\ 1 & 1 & & & \\ 1 & 4 & 1 & & \\ 1 & 12 & 10 & 1 & \\ 1 & 32 & 67 & 20 & 1 \\ \end{matrix} $$
Also, a specialization of equation (16) in the paper gives us a generating function for A080416 that is somewhat simpler than using A080251: $$ \sum_{n \ge k} s(0,n,k) x^n = \frac{x^k}{\prod_{i=1}^{k-1} (1 - i(k-i)x)}. $$ It's possible that I've missed some other useful formulas from the paper.
On p.12, item 5 gives a combinatorial interpretation of $s(0,n,k)$:
This appears to be incorrect; instead, I get $s(0,n,k)$ if we take $(C_1, C_2, \dots, C_k)$ and $(C'_1, C'_2, \dots, C'_k)$ to be partitions of $[n] = \{1,2,\dots,n\}$ into $k$ parts, sorted by their minimal elements. So for example we get $s(0,4,3) = 4$ from the four pairs below: