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.

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

Author

Liam Solus, Aug 26 2018

Keywords

• nonn
• tabl
• easy

Comments

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.

Examples

			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
		

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.

Crossrefs

Columns include A000045, A001519, A318376, A318404.

Cf. A007984.

Programs

Sage

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