login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A318407 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. 1
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, 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, 77, 153, 158, 147, 97, 39, 15, 1, 1, 17, 91, 210, 248, 222, 155, 62, 21, 1 (list; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=0..74.

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

Cf. A007984, A318406.

Sequence in context: A131642 A070674 A070668 * A325807 A072341 A011130

Adjacent sequences:  A318404 A318405 A318406 * A318408 A318409 A318410

KEYWORD

nonn,tabf,easy

AUTHOR

Liam Solus, Aug 26 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 19 16:48 EDT 2019. Contains 324222 sequences. (Running on oeis4.)