OFFSET
0,7
COMMENTS
The n-th row of the triangle T(n,k) is the coefficient sequence of a generating polynomial admitting a recursive formula given in Theorem 4.3 of the paper by A. Radhakrishnan et al. below.
The sum of the entries in the n-th row is A318406(n).
The entries in the n-th row appear to alway form a unimodal sequence.
LINKS
A. Radhakrishnan, L. Solus, and C. Uhler. Counting Markov equivalence classes for DAG models on trees, arXiv:1706.06091 [math.CO], 2017; Discrete Applied Mathematics 244 (2018): 170-185.
FORMULA
A recursion whose n-th iteration is a polynomial with coefficient vector the n-th row of T(n,k):
W_0 = 0
W_1 = 1
W_2 = 1
W_3 = 1 + x
W_4 = 1 + 2*x
for n>4:
if n is even:
W_n = W_{n-1} + x*W_{n-2}
if n is odd:
W_n = (x + 2)*W_{n-2} + (x^3 - x^2 + x-2)*W_{n-3} + (x^2 + 1)*W_{n-4}
(see Theorem 4.3 of Radhakrishnan et al. for proof.)
EXAMPLE
The triangle T(n,k) begins:
n\k| 0 1 2 3 4 5 6 7 8 9
-----+------------------------------------------------
0 | 0
1 | 1
2 | 1
3 | 1 1
4 | 1 2
5 | 1 4 1 1
6 | 1 5 3 1
7 | 1 7 8 3 3
8 | 1 8 13 6 4
9 | 1 10 23 16 13 6 1
10 | 1 11 31 29 19 10 1
11 | 1 13 46 59 46 39 13 5
12 | 1 14 57 90 75 58 23 6
13 | 1 16 77 153 158 147 97 39 15 1
14 | 1 17 91 210 248 222 155 62 21 1
MATHEMATICA
W[0] = 0; W[1] = 1; W[2] = 1; W[3] = 1 + x; W[4] = 1 + 2x;
W[n_] := W[n] = If[EvenQ[n], W[n-1] + x W[n-2], (x+2) W[n-2] + (x^3 - x^2 + x - 2) W[n-3] + (x^2 + 1) W[n-4]];
Join[{0}, Table[CoefficientList[W[n], x], {n, 0, 14}]] // Flatten (* Jean-François Alcover, Sep 17 2018 *)
PROG
(PARI) pol(n) = if (n==0, 0, if (n==1, 1, if (n==2, 1, if (n==3, 1 + x, if (n==4, 1 + 2*x, if (n%2, (x + 2)*pol(n-2) + (x^3 - x^2 + x-2)*pol(n-3) + (x^2 + 1)*pol(n-4), pol(n-1) + x*pol(n-2)))))));
row(n) = Vecrev(pol(n)); \\ Michel Marcus, Sep 04 2018
CROSSREFS
KEYWORD
nonn,tabf,easy
AUTHOR
Liam Solus, Aug 26 2018
STATUS
approved