|
|
A092921
|
|
Array F(k, n) read by descending antidiagonals: k-generalized Fibonacci numbers in row k >= 1, starting (0, 1, 1, ...), for column n >= 0.
|
|
21
|
|
|
0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 3, 2, 1, 1, 0, 1, 5, 4, 2, 1, 1, 0, 1, 8, 7, 4, 2, 1, 1, 0, 1, 13, 13, 8, 4, 2, 1, 1, 0, 1, 21, 24, 15, 8, 4, 2, 1, 1, 0, 1, 34, 44, 29, 16, 8, 4, 2, 1, 1, 0, 1, 55, 81, 56, 31, 16, 8, 4, 2, 1, 1, 0, 1, 89, 149, 108, 61, 32, 16, 8, 4, 2, 1, 1, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,12
|
|
COMMENTS
|
For all k >= 1, the k-generalized Fibonacci number F(k,n) satisfies the recurrence obtained by adding more terms to the recurrence of the Fibonacci numbers.
The number of tilings of an 1 X n rectangle with tiles of size 1 X 1, 1 X 2, ..., 1 X k is F(k,n).
T(k,n) is the number of 0-balanced ordered trees with n edges and height k (height is the number of edges from root to a leaf). - Emeric Deutsch, Jan 19 2007
Brlek et al. (2006) call this table "number of psp-polyominoes with flat bottom". - N. J. A. Sloane, Oct 30 2018
|
|
LINKS
|
|
|
FORMULA
|
F(k,n) = F(k,n-1) + F(k,n-2) + ... + F(k,n-k); F(k,1) = 1 and F(k,n) = 0 for n <= 0.
G.f.: x/(1-Sum_{i=1..k} x^i).
F(k,n) = 2^(n-2) for 1 < n <= k+1. - M. F. Hasler, Apr 20 2018
F(k,n) = Sum_{j=0..floor(n/(k+1))} (-1)^j*((n - j*k) + j + delta(n,0))/(2*(n - j*k) + delta(n,0))*binomial(n - j*k, j)*2^(n-j*(k+1)), where delta denotes the Kronecker delta (see Corollary 3.2 in Parks and Wills). - Stefano Spezia, Aug 06 2022
|
|
EXAMPLE
|
Array begins:
n = 0 1 2 3 4 5 6 7 8 9 10
-------------------------------------------------------------
[k=1, mononacci ] 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
[k=2, Fibonacci ] 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
[k=3, tribonacci] 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, ...
[k=4, tetranacci] 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, ...
[k=5, pentanacci] 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, ...
[k=6] 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, ...
[k=7] 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, ...
[k=8] 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, ...
[k=9] 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, ...
Note that the first parameter in F(k, n) refers to rows, and the second parameter refers to columns. This is always the case. Only the usual naming convention for the indices is not adhered to because it is common to call the row sequences k-bonacci numbers. (End)
.
As a triangle counting compositions of n with largest part k:
n\k]| [0][1] [2] [3] [4][5][6][7][8][9]
[0] | [0]
[1] | [0, 1]
[2] | [0, 1, 1]
[3] | [0, 1, 1, 1]
[4] | [0, 1, 2, 1, 1]
[5] | [0, 1, 3, 2, 1, 1]
[6] | [0, 1, 5, 4, 2, 1, 1]
[7] | [0, 1, 8, 7, 4, 2, 1, 1]
[8] | [0, 1, 13, 13, 8, 4, 2, 1, 1]
[9] | [0, 1, 21, 24, 15, 8, 4, 2, 1, 1]
For example for n=7 and k=3 we have the 7 compositions [3, 3, 1], [3, 2, 2], [3, 2, 1, 1], [3, 1, 3], [3, 1, 2, 1], [3, 1, 1, 2], [3, 1, 1, 1, 1].
(End)
|
|
MAPLE
|
F:= proc(k, n) option remember; `if`(n<2, n,
add(F(k, n-j), j=1..min(k, n)))
end:
seq(seq(F(k, d+1-k), k=1..d+1), d=0..12); # Alois P. Heinz, Nov 02 2016
# Based on the above function:
Arow := (k, len) -> seq(F(k, j), j = 0..len):
seq(lprint(Arow(k, 14)), k = 1..10); # Peter Luschny, Apr 03 2021
|
|
MATHEMATICA
|
F[k_, n_] := F[k, n] = If[n<2, n, Sum[F[k, n-j], {j, 1, Min[k, n]}]];
Table[F[k, d+1-k], {d, 0, 12}, {k, 1, d+1}] // Flatten (* Jean-François Alcover, Jan 11 2017, translated from Maple *)
|
|
PROG
|
(PARI) F(k, n)=if(n<2, if(n<1, 0, 1), sum(i=1, k, F(k, n-i)))
(PARI) T(m, n)=!!n*(matrix(m, m, i, j, j==i+1||i==m)^(n+m-2))[1, m] \\ M. F. Hasler, Apr 20 2018
(PARI) F(k, n) = if(n==0, 0, polcoeff(lift(Mod('x, Pol(vector(k+1, i, if(i==1, 1, -1))))^(n+k-2)), k-1)); \\ Kevin Ryde, Jun 05 2020
(Sage)
# As a triangle of compositions of n with largest part k.
C = lambda n, k: Compositions(n, max_part=k, inner=[k]).cardinality()
for n in (0..9): [C(n, k) for k in (0..n)] # Peter Luschny, Aug 12 2015
|
|
CROSSREFS
|
Columns converge to A166444: each column n converges to A166444(n) = 2^(n-2).
Essentially a reflected version of A048887.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|