7
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ After almost 20 years still no programs and only a sketchy formula. Not a good sign. $\endgroup$
    – Somos
    Oct 12, 2022 at 19:47
  • $\begingroup$ @Somos that's how you know you have entered the Forbidden Obscure Mathematics $\endgroup$
    – KKZiomek
    Oct 12, 2022 at 20:06
  • $\begingroup$ I have proposed an edit to the OEIS with Mathematica code for the recurrence in my answer, so hopefully we'll get a tiny bit less Forbidden Obscure soon. $\endgroup$ Oct 12, 2022 at 20:20
  • $\begingroup$ @MishaLavrov what's crazy is that this sequence popped up from a very easy-to-visualize scenario that is a real life application of counting. I am stunned that there is so little information out there about this $\endgroup$
    – KKZiomek
    Oct 13, 2022 at 0:28

1 Answer 1

2
$\begingroup$

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)$:

The number of pairs of permutations $(\sigma_1, \sigma_2)$ where $\sigma_1$ is a permutation of $[n]$ into disjoint cycles $C_1, C_2, \dots, C_k$, and $\sigma_2$ is a permutation of $[n]$ into disjoint cycles $C'_1, C'_2, \dots, C'_k$, such that for $1 \le j \le k$, the sum of minimal elements of $C_j$ and $C'_{k-j+1}$ is $n+1$.

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:

  • $\{1\},\{2,3\},\{4\}$ and $\{1,2\},\{3\},\{4\}$ with sums $1+4,2+3,4+1$
  • $\{1,3\},\{2\},\{4\}$ and $\{1,2\},\{3\},\{4\}$ with sums $1+4,2+3,4+1$
  • since they are ordered pairs, each of the above can be reversed.
$\endgroup$
6
  • $\begingroup$ +1 for the recurrence formulas, they are helpful. But, do you think a closed form is possible for this specific number triangle? Also, is there some intuition behind the meaning of the numbers in the sequence, that's perhaps connected to the algorithm that I discovered? I could provide you with the scenario that those numbers appeared in, if that would help provide some specific context to what I'm trying to achieve. $\endgroup$
    – KKZiomek
    Oct 12, 2022 at 19:18
  • $\begingroup$ Also, it would be nice to see how this specific sequence (as opposed to the generalization from the paper) is derived from the tetrahedral numbers $\endgroup$
    – KKZiomek
    Oct 12, 2022 at 19:25
  • $\begingroup$ I don't really understand anything that's going on, I'm just adapting what I found in the paper, and you might actually get more out of reading it than I did. I've added a combinatorial interpretation given in the paper to my answer. The end of the paper says that explicit formulas are still unknown. $\endgroup$ Oct 12, 2022 at 19:27
  • $\begingroup$ I see, still thanks for pointing all of that out. I'll be trying to decipher the combinatorial interpretation but it's quite complex lol $\endgroup$
    – KKZiomek
    Oct 12, 2022 at 19:30
  • $\begingroup$ It looks like the combinatorial interpretation erroneously talks about permutations when it should talk about partitions. But with the correction, this is actually just the combinatorial interpretation given in the OEIS sequence! $\endgroup$ Oct 12, 2022 at 20:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .