A007984 -id:A007984 - cp's OEIS frontend

A143977 Rectangular array R by antidiagonals: label each unit square in the first quadrant lattice by its northeast vertex (x,y) and mark squares having |x-y| == 0 (mod 3); then R(m,n) is the number of marked squares in the rectangle [0,m] X [0,n].

1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 3, 3, 3, 2, 2, 4, 4, 4, 4, 2, 3, 4, 5, 6, 5, 4, 3, 3, 5, 6, 7, 7, 6, 5, 3, 3, 6, 7, 8, 9, 8, 7, 6, 3, 4, 6, 8, 10, 10, 10, 10, 8, 6, 4, 4, 7, 9, 11, 12, 12, 12, 11, 9, 7, 4, 4, 8, 10, 12, 14, 14, 14, 14, 12, 10, 8, 4, 5, 8, 11, 14, 15, 16, 17, 16, 15, 14, 11, 8, 5

Offset: 1

Clark Kimberling, Sep 06 2008

Rows numbered 3,6,9,12,15,... are, except for initial terms, multiples of (1,2,3,4,5,6,7,...) = A000027.

			Northwest corner:
  1  1  1  2  2  2  3
  1  2  2  3  4  4  5
  1  2  3  4  5  6  7
  2  3  4  6  7  8 10
  2  4  5  7  9 10 12

Stefano Spezia, First 140 antidiagonals of the array, flattened

Diagonals: A008810, A007984, A000212, A128422.
Rows and columns: A002264, A004523, A000027, A004772, A047212, et al.
Cf. A143974, A143976, A143979.

T[m_,n_]:=Ceiling[m n/3];Flatten[Table[T[m-n+1,n],{m,13},{n,m}]] (* Stefano Spezia, Oct 27 2022 *)

R(m,n) = ceiling(m*n/3). [Corrected by Stefano Spezia, Oct 27 2022]

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)

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

A368569 Irregular triangle read by rows: T(n,k) is the number of essential graphs with n nodes and k (directed or undirected) edges (n >= 1, 0 <= k <= n*(n-1)/2).

Original entry on oeis.org

1, 1, 1, 1, 3, 6, 1, 1, 6, 27, 60, 66, 24, 1, 1, 10, 75, 350, 1120, 2130, 2595, 1730, 690, 80, 1, 1, 15, 165, 1235, 6930, 27882, 79825, 162315, 236490, 245150, 180936, 91560, 29890, 5190, 240, 1

Offset: 1

Moritz Schauer, Feb 06 2024

			Triangle T(n,k) (with n >= 1 and 0 <= k <= n*(n-1)/2) begins as follows:
  1;
  1,  1;
  1,  3,  6,   1;
  1,  6, 27,  60,   66,   24,    1;
  1, 10, 75, 350, 1120, 2130, 2595, 1730, 690, 80, 1;
  ...

Row sums give A007984.
Row lengths give A000124.
Column k=1 is A000217.
Column k=2 is A239568.

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)

cp's OEIS Frontend

A143977 Rectangular array R by antidiagonals: label each unit square in the first quadrant lattice by its northeast vertex (x,y) and mark squares having |x-y| == 0 (mod 3); then R(m,n) is the number of marked squares in the rectangle [0,m] X [0,n].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

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

A368569 Irregular triangle read by rows: T(n,k) is the number of essential graphs with n nodes and k (directed or undirected) edges (n >= 1, 0 <= k <= n*(n-1)/2).

Views

Author

Keywords

Examples

Crossrefs

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

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.