Liam Solus - cp's OEIS frontend

A318408 Triangle read by rows: T(n,k) is the number of permutations of [n+1] with index in the lexicographic ordering of permutations being congruent to 1 or 5 modulo 6 that have exactly k descents; k > 0.

0, 0, 1, 1, 1, 1, 6, 1, 1, 19, 19, 1, 1, 48, 142, 48, 1, 1, 109, 730, 730, 109, 1, 1, 234, 3087, 6796, 3087, 234, 1, 1, 487, 11637, 48355, 48355, 11637, 487, 1, 1, 996, 40804, 291484, 543030, 291484, 40804, 996, 1

Offset: 0

Liam Solus, Aug 26 2018

Note that we assume the permutations are lexicographically ordered in a zero-indexed list from smallest to largest.
Recall that a descent in a permutation p of [n+1] is an index i in [n] such that p(i) > p(i+1).
The n-th row of the triangle T(n,k) is the coefficient vector of the local h^*-polynomial (i.e., the box polynomial) of the factoradic n-simplex. Each row is known to be symmetric and unimodal. Moreover the local h^*-polynomial of the factoradic n-simplex has only real roots. See the paper by L. Solus below for definitions and proofs of these statements.
The n-th row of T(n,k) is the coefficient sequence of a restriction of the n-th Eulerian polynomial, which is given by the n-th row of A008292.

			The triangle T(n,k) begins:
  n\k|  1     2     3       4       5       6     7     8    9
  ---+---------------------------------------------------------
  0  |  0
  1  |  0
  2  |  1
  3  |  1     1
  4  |  1     6     1
  5  |  1    19    19       1
  6  |  1    48   142      48       1
  7  |  1   109   730     730     109       1
  8  |  1   234  3087    6796    3087     234     1
  9  |  1   487 11637   48355   48355   11637   487     1
  10 |  1   996 40804  291484  543030  291484 40804   996    1

L. Solus. Local h^*-polynomials of some weighted projective spaces, arXiv:1807.08223 [math.CO], 2018. To appear in the Proceedings of the 2018 Summer Workshop on Lattice Polytopes at Osaka University (2018).

Cf. A008292.

R = QQ[z];
factoradicBox = n -> (
L := toList(1..(n!-1));
B := {};
for j in L do
if (j%6!=0 and j%6!=2 and j%6!=3 and j%6!=4) then B = append(B,j);
W := B / (i->z^(i-sum(1..(n-1),j->floor(i/((n-j)!+(n-1-j)!)))));
return sum(W);
);

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.

Original entry on oeis.org

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

Offset: 0

Liam Solus, Aug 26 2018

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.

			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

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.

Cf. A007984, A318406.

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 *)

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

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.)

A318406 For n > 4, a(n) = a(n-1) + a(n-2) if n is even and a(n) = 3*a(n-2) + a(n-4) - a(n-5) if n is odd; a(0) = 0, a(1) = 1, a(2) = 1, a(3) = 2, and a(4) = 3.

Original entry on oeis.org

0, 1, 1, 2, 3, 7, 10, 22, 32, 70, 102, 222, 324, 704, 1028, 2232, 3260, 7076, 10336, 22432, 32768, 71112, 103880, 225432, 329312, 714640, 1043952, 2265472, 3309424, 7181744, 10491168, 22766752, 33257920, 72172576, 105430496, 228793312, 334223808, 725294592, 1059518400, 2299246592, 3358764992

Offset: 0

Liam Solus, Aug 26 2018

a(n) is the number of Markov equivalence classes whose skeleton is the caterpillar graph on n nodes. See Corollary 4.4 in the paper by A. Radhakrishnan et al. below.

Colin Barker, Table of n, a(n) for n = 0..1000
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.
Index entries for linear recurrences with constant coefficients, signature (0,4,0,-2,0,-2).

Cf. A007984, A318407.

LinearRecurrence[{0, 4, 0, -2, 0, -2}, {0, 1, 1, 2, 3, 7}, 50] (* Jean-François Alcover, Sep 17 2018 *)
nxt[{n_,a_,b_,c_,d_,e_}]:={n+1,b,c,d,e,If[OddQ[n],d+e,3d-a+b]}; NestList[nxt,{4,0,1,1,2,3},40][[All,2]] (* Harvey P. Dale, Dec 25 2022 *)

a(n) = if (n > 4, if (n%2, 3*a(n-2) + a(n-4) - a(n-5), a(n-1) + a(n-2)), if (n > 1, n-1, n)); \\ Michel Marcus, Sep 03 2018

concat(0, Vec(x*(1 - x)*(1 + x)*(1 + x - x^2) / (1 - 4*x^2 + 2*x^4 + 2*x^6) + O(x^40))) \\ Colin Barker, Sep 03 2018

From Colin Barker, Sep 03 2018: (Start)
G.f.: x*(1 - x)*(1 + x)*(1 + x - x^2) / (1 - 4*x^2 + 2*x^4 + 2*x^6).
a(n) = 4*a(n-2) - 2*a(n-4) - 2*a(n-6) for n>5.
(End)

A318405 Rectangular array R read by antidiagonals: R(n,k) = F(n+1)^k - kF(n-1)F(n)^(k-1), where F(n) = A000045(n), the n-th Fibonacci number; n >= 0, k >= 1.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 5, 5, 3, 1, 1, 12, 15, 13, 5, 1, 1, 27, 49, 71, 34, 8, 1, 1, 58, 163, 409, 287, 89, 13, 1, 1, 121, 537, 2315, 2596, 1237, 233, 21, 1, 1, 248, 1739, 12709, 23393, 18321, 5205, 610, 34, 1, 1, 503, 5537, 67919, 205894, 268893, 124177, 22105, 1597, 55

Offset: 0

Liam Solus, Aug 26 2018

Row index n begins with 0, column index begins with 1.

R(n,k) is the number of Markov equivalence classes whose skeleton is a spider graph with k legs, each of which contains n nodes of degree at most two. See Corollary 4.2 in the paper by A. Radhakrishnan et al. below.

			The rectangular array R(n,k) begins:
n\k|   1      2      3        4         5          6            7
---+-------------------------------------------------------------
0  |   0      1      1        1         1          1            1
1  |   1      1      1        1         1          1            1
2  |   1      2      5       12        27         58          121
3  |   2      5     15       49       163        537         1739
4  |   3     13     71      409      2315      12709        67919
5  |   5     34    287     2596     23393     205894      1769027
6  |   8     89   1237    18321    268893    3843769     53573477
7  |  13    233   5205   124177   2941661   67944057   1530787237

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.

Columns include A000045, A001519, A318376, A318404.

Cf. A007984.

def R(n, k):
    return fibonacci(n+1)^k-k*fibonacci(n-1)*fibonacci(n)^(k-1)

A318404 a(n) = F(n+1)^4 - 4F(n-1)F(n)^3, where F(n) = A000045(n), the n-th Fibonacci number.

Original entry on oeis.org

1, 1, 12, 49, 409, 2596, 18321, 124177, 854764, 5849089, 40115241, 274888516, 1884285217, 12914634529, 88519396044, 606717892561, 4158514347961, 28502860300132, 195361565985969, 1339027949145649, 9177834477168556, 62905812346085281, 431162854681140297

Offset: 0

Liam Solus, Aug 26 2018

a(n) is the number of Markov equivalence classes whose skeleton is a spider graph with four legs, each of which contains n nodes of degree at most two.

A001519 admits the related formula A001519(n) = F(n+1)^2 - 2*F(n-1)*F(n).

Robert Israel, Table of n, a(n) for n = 0..1195
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.
Index entries for linear recurrences with constant coefficients, signature (5,15,-15,-5,1).

Cf. A000045, A001519, A318376.

[Fibonacci(n+1)^4-4*Fibonacci(n-1)*Fibonacci(n)^3: n in [0..25]]; // Vincenzo Librandi, Aug 26 2018

f:= gfun:-rectoproc({a(n+5)-5*a(n+4)-15*a(n+3)+15*a(n+2)+5*a(n+1)-a(n),a(0)=1,a(1)=1,a(2)=12,a(3)=49,a(4)=409},a(n),remember):
map(f, [$0..30]); # Robert Israel, Aug 26 2018

Table[Fibonacci[n + 1]^4 - 4 Fibonacci[n - 1] Fibonacci[n]^3, {n, 0, 25}] (* Vincenzo Librandi, Aug 26 2018 *)
CoefficientList[Series[(-1 + 4 x + 8 x^2 + 11 x^3 - 4 x^4)/(-1 + 5 x + 15 x^2 - 15 x^3 - 5 x^4 + x^5), {x, 0, 50}], x] (* Stefano Spezia, Sep 03 2018 *)

a(n) = fibonacci(n+1)^4 - 4*fibonacci(n-1)*fibonacci(n)^3; \\ Michel Marcus, Aug 26 2018

def a(n):
    return fibonacci(n+1)^4-4*fibonacci(n-1)*fibonacci(n)^3
[a(n) for n in range(20)]

G.f.: (-1 + 4*x + 8*x^2 + 11*x^3 - 4*x^4)/(-1 + 5*x + 15*x^2 - 15*x^3 - 5*x^4 + x^5). - Robert Israel, Aug 26 2018

a(0) = 1 prepended by Vincenzo Librandi, Aug 26 2018

A318376 a(n) = F(n+1)^3 - 3F(n-1)F(n)^2, where F(n) = A000045(n), the n-th Fibonacci number.

Original entry on oeis.org

1, 1, 5, 15, 71, 287, 1237, 5205, 22105, 93547, 396419, 1679019, 7112825, 30129785, 127632829, 540659703, 2290273903, 9701751655, 41097286445, 174090887853, 737460853361, 3123934276211, 13233197998795, 56056726205715, 237460102927921, 1005897137745457, 4261048654187957

Offset: 0

Liam Solus, Aug 24 2018

a(n) is the number of Markov equivalence classes whose skeleton is a spider graph with three legs, each of which contains n nodes of degree at most two.

A001519 admits the related formula A001519(n) = F(n+1)^2 - 2*F(n-1)*F(n).

Colin Barker, Table of n, a(n) for n = 0..1000
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.
Index entries for linear recurrences with constant coefficients, signature (3,6,-3,-1).

Cf. A000045, A001519.

[Fibonacci(n+1)^3 - 3*Fibonacci(n-1)*Fibonacci(n)^2: n in [1..30]]; // Vincenzo Librandi, Sep 03 2018

CoefficientList[Series[(1 - 2 x - 4 x^2 - 3 x^3) / ((1 + x - x^2) (1-4 x-x^2)), {x, 0, 26}], x] (* Michael De Vlieger, Aug 25 2018 *)
LinearRecurrence[{3, 6, -3, -1}, {1, 1, 5, 15, 71}, 26] (* Stefano Spezia, Sep 02 2018; a(0)=1 amended by Georg Fischer, Apr 03 2019 *)
Table[Fibonacci[n + 1]^3 - 3 Fibonacci[n-1] Fibonacci[n]^2, {n, 0, 25}] (* Vincenzo Librandi, Sep 03 2018 *)
#[[3]]^3-3#[[1]]#[[2]]^2&/@Partition[Fibonacci[Range[-1,30]],3,1] (* Harvey P. Dale, Sep 02 2023 *)

a(n) = fibonacci(n+1)^3 - 3*fibonacci(n-1)*fibonacci(n)^2; \\ Michel Marcus, Aug 25 2018

my(x='x+O('x^31));  Vec((1 - 2*x - 4*x^2 - 3*x^3) / ((1 + x - x^2)*(1 - 4*x - x^2))) \\ Colin Barker, Aug 25 2018 and Sep 06 2018

From Colin Barker, Aug 25 2018: (Start)
G.f.: (1 - 2 x - 4 x^2 - 3 x^3) / ((1 + x - x^2)*(1 - 4*x - x^2)).
a(n) = 3*a(n-1) + 6*a(n-2) - 3*a(n-3) - a(n-4) for n>3.
(End)

a(0) = 1 inserted by Vincenzo Librandi, Sep 03 2018

cp's OEIS Frontend

User: Liam Solus

A318408 Triangle read by rows: T(n,k) is the number of permutations of [n+1] with index in the lexicographic ordering of permutations being congruent to 1 or 5 modulo 6 that have exactly k descents; k > 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Macaulay2

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A318406 For n > 4, a(n) = a(n-1) + a(n-2) if n is even and a(n) = 3*a(n-2) + a(n-4) - a(n-5) if n is odd; a(0) = 0, a(1) = 1, a(2) = 1, a(3) = 2, and a(4) = 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A318405 Rectangular array R read by antidiagonals: R(n,k) = F(n+1)^k - k*F(n-1)*F(n)^(k-1), where F(n) = A000045(n), the n-th Fibonacci number; n >= 0, k >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

A318404 a(n) = F(n+1)^4 - 4*F(n-1)*F(n)^3, where F(n) = A000045(n), the n-th Fibonacci number.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A318376 a(n) = F(n+1)^3 - 3*F(n-1)*F(n)^2, where F(n) = A000045(n), the n-th Fibonacci number.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

Extensions

A318405 Rectangular array R read by antidiagonals: R(n,k) = F(n+1)^k - kF(n-1)F(n)^(k-1), where F(n) = A000045(n), the n-th Fibonacci number; n >= 0, k >= 1.

A318404 a(n) = F(n+1)^4 - 4F(n-1)F(n)^3, where F(n) = A000045(n), the n-th Fibonacci number.

A318376 a(n) = F(n+1)^3 - 3F(n-1)F(n)^2, where F(n) = A000045(n), the n-th Fibonacci number.