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.
Best Answer
I don't see a problem with the approach you just explained. $$\begin{align} (1+2)^{2n}+(1-2)^{2n} &=\sum_{k=0}^{2n}\binom{2n}{k}2^k+\sum_{k=0}^{2n}\binom{2n}{k}(-2)^k\\ &=\sum_{k=0}^{2n}\binom{2n}{k}(2^k+(-2)^k)\\ &=2\sum_{j=0}^n\binom{2n}{2j}2^{2j}\quad\left(j=\frac12k\right)\\ &=2\sum_{j=0}^n\binom{2n}{2j}4^j\\ \end{align}$$ $$\therefore\sum_{k=0}^n\binom{2n}{2k}4^k=\frac12\left(3^{2n}+(-1)^{2n}\right)$$