A318407 - OEIS

%I #17 Sep 17 2018 03:41:49

%S 0,1,1,1,1,1,2,1,4,1,1,1,5,3,1,1,7,8,3,3,1,8,13,6,4,1,10,23,16,13,6,1,

%T 1,11,31,29,19,10,1,1,13,46,59,46,39,13,5,1,14,57,90,75,58,23,6,1,16,

%U 77,153,158,147,97,39,15,1,1,17,91,210,248,222,155,62,21,1

%N Triangle read by rows: T(n,k) is the number of Markov equivalence classes whose skeleton is the caterpillar graph on n nodes that contain precisely k immoralities.

%C 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.

%C The sum of the entries in the n-th row is A318406(n).

%C The entries in the n-th row appear to alway form a unimodal sequence.

%H A. Radhakrishnan, L. Solus, and C. Uhler. <a href="https://arxiv.org/abs/1706.06091">Counting Markov equivalence classes for DAG models on trees</a>, arXiv:1706.06091 [math.CO], 2017; Discrete Applied Mathematics 244 (2018): 170-185.

%F A recursion whose n-th iteration is a polynomial with coefficient vector the n-th row of T(n,k):

%F W_0 = 0

%F W_1 = 1

%F W_2 = 1

%F W_3 = 1 + x

%F W_4 = 1 + 2*x

%F for n>4:

%F   if n is even:

%F     W_n = W_{n-1} + x*W_{n-2}

%F   if n is odd:

%F     W_n = (x + 2)*W_{n-2} + (x^3 - x^2 + x-2)*W_{n-3} + (x^2 + 1)*W_{n-4}

%F (see Theorem 4.3 of Radhakrishnan et al. for proof.)

%e The triangle T(n,k) begins:

%e   n\k|  0    1    2    3    4    5    6    7    8    9

%e -----+------------------------------------------------

%e    0 |  0

%e    1 |  1

%e    2 |  1

%e    3 |  1    1

%e    4 |  1    2

%e    5 |  1    4    1    1

%e    6 |  1    5    3    1

%e    7 |  1    7    8    3    3

%e    8 |  1    8   13    6    4

%e    9 |  1   10   23   16   13    6    1

%e   10 |  1   11   31   29   19   10    1

%e   11 |  1   13   46   59   46   39   13    5

%e   12 |  1   14   57   90   75   58   23    6

%e   13 |  1   16   77  153  158  147   97   39   15    1

%e   14 |  1   17   91  210  248  222  155   62   21    1

%t W[0] = 0; W[1] = 1; W[2] = 1; W[3] = 1 + x; W[4] = 1 + 2x;

%t 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]];

%t Join[{0}, Table[CoefficientList[W[n], x], {n, 0, 14}]] // Flatten (* _Jean-François Alcover_, Sep 17 2018 *)

%o (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)))))));

%o row(n) = Vecrev(pol(n)); \\ _Michel Marcus_, Sep 04 2018

%Y Cf. A007984, A318406.

%K nonn,tabf,easy

%O 0,7

%A _Liam Solus_, Aug 26 2018