|
| |
|
|
A092921
|
|
Array F(k,n) read by antidiagonals: k-generalized Fibonacci numbers in row k >= 1, starting (0, 1, 1, ...) for column n >= 0.
|
|
16
|
|
|
|
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
|
Alois P. Heinz, Antidiagonals n = 0..140, flattened
Srecko Brlek, Andrea Frosini, Simone Rinaldi, Laurent Vuillon, Tilings by translation: enumeration by a rational language approach, The Electronic Journal of Combinatorics, vol. 13, (2006). Table 1 is essentially this array. - N. J. A. Sloane, Jul 20 2014
E. S. Egge, Restricted permutations related to Fibonacci numbers and k-generalized Fibonacci numbers, arXiv:math/0109219 [math.CO], 2001.
E. S. Egge, Restricted 3412-Avoiding Involutions, arXiv:math/0307050 [math.CO], 2003.
E. S. Egge and T. Mansour, Restricted permutations, Fibonacci numbers and k-generalized Fibonacci numbers, arXiv:math/0203226 [math.CO], 2002.
E. S. Egge and T. Mansour, 231-avoiding involutions and Fibonacci numbers, arXiv:math/0209255 [math.CO], 2002.
Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.
Abraham Flaxman, Aram W. Harrow, Gregory B. Sorkin, Strings with Maximally Many Distinct Subsequences and Substrings, Electronic J. Combinatorics 11 (1) (2004), Paper R8.
I. Flores, k-Generalized Fibonacci numbers, Fib. Quart., 5 (1967), 258-266.
H. Gabai, Generalized Fibonacci k-sequences, Fib. Quart., 8 (1970), 31-38.
R. Kemp, Balanced ordered trees, Random Structures and Alg., 5 (1994), pp. 99-121.
E. P. Miles jr., Generalized Fibonacci numbers and associated matrices, The Amer. Math. Monthly, 67 (1960) 745-752.
M. D. Miller, On generalized Fibonacci numbers, The Amer. Math. Monthly, 78 (1971) 1108-1109.
|
|
|
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
|
|
|
EXAMPLE
|
Array begins:
k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 k=9 k=10
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
1, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...
1, 3, 4, 4, 4, 4, 4, 4, 4, 4, ...
1, 5, 7, 8, 8, 8, 8, 8, 8, 8, ...
1, 8, 13, 15, 16, 16, 16, 16, 16, 16, ...
1, 13, 24, 29, 31, 32, 32, 32, 32, 32, ...
1, 21, 44, 56, 61, 63, 64, 64, 64, 64, ...
1, 34, 81, 108, 120, 125, 127, 128, 128, 128, ...
1, 55, 149, 208, 236, 248, 253, 255, 256, 256, ...
...
Note: This is the transpose of the array corresponding to the data according to OEIS conventions, i.e., read by falling antidiagonals, cf. "table" link. - M. F. Hasler, Apr 20 2018
From Peter Luschny, Aug 12 2015: (Start)
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
|
|
|
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
|
Rows converge to A166444: each column n converges to A166444(n) (= 2^(n-2) = A000079(n-2) for n >= 2).
Rows 1-8 are (shifted) A057427, A000045, A000073, A000078, A001591, A001592, A066178, A079262.
Essentially a reflected version of A048887. See A048004 and A126198 for closely related arrays.
Cf. A066099.
Sequence in context: A129353 A174295 A158511 * A191607 A029387 A070878
Adjacent sequences: A092918 A092919 A092920 * A092922 A092923 A092924
|
|
|
KEYWORD
|
nonn,tabl
|
|
|
AUTHOR
|
Ralf Stephan, Apr 17 2004
|
|
|
STATUS
|
approved
|
| |
|
|
