A336996 Triangle of coefficients T(n,k) (n >= 0, 0 <= k <= 2*n), read by rows: n-th row is obtained by expanding (2 + x + x^2)^n.

1, 2, 1, 1, 4, 4, 5, 2, 1, 8, 12, 18, 13, 9, 3, 1, 16, 32, 56, 56, 49, 28, 14, 4, 1, 32, 80, 160, 200, 210, 161, 105, 50, 20, 5, 1, 64, 192, 432, 640, 780, 732, 581, 366, 195, 80, 27, 6, 1, 128, 448, 1120, 1904, 2632, 2884, 2674, 2045, 1337, 721, 329, 119, 35, 7, 1

Offset: 0

Author

Brian Hopkins, Aug 10 2020

Keywords

• nonn
• tabf

Comments

3-compositions are integer compositions where up to 2 0's are allowed between successive positive parts. T(n,k) is the number of 3-compositions of n+1 having k 0's.

First column counts standard compositions.

Examples

			3-compositions of 2 are 2 and 1+1 with no 0's, 1+0+1 with one 0, and 1+0+0+1 with two 0's.
Triangle T(n, k) begins:
n\k 0   1   2   3   4   5   6   7   8   9 10 11 12
0:  1
1:  2   1   1
2:  4   4   5   2   1
3:  8  12  18  13   9   3   1
4: 16  32  56  56  49  28  14   4   1
5: 32  80 160 200 210 161 105  50  20   5  1
6: 64 192 432 640 780 732 581 366 195  80 27  6  1
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..22800 (rows 0 <= n <= 150, flattened)
• Brian Hopkins and Stéphane Ouvry, Combinatorics of Multicompositions, arXiv:2008.04937 [math.CO], 2020.

Crossrefs

Cf. A027907 for (1+x+x^2)^n, A038207 for 2-compositions.

Programs

Mathematica

Table[CoefficientList[(2 + x + x^2)^n, x], {n, 0, 8}]

PARI

row(n) = Vecrev((x^2 + x + 2)^n); \\ Michel Marcus, Aug 14 2020

Formula

T(n,k) = Sum_{m=0..n} binomial(n, m)*trinomial(m, k) using trinomial coefficients as in A027907.

Recurrence: T(0,0) = 1; T(n,k) = T(n-1,k-2) + T(n-1,k-1) + 2*T(n-1,k), with T(n,k) = 0 if k < 0 or k > 2*n.

Row sums are powers of 4 (A000302).