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.
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
Offset: 0
Examples
From _Peter Luschny_, Apr 03 2021: (Start)
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)
.
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)
Links
- Alois P. Heinz, Antidiagonals n = 0..140, flattened
- Srecko Brlek, Andrea Frosini, Simone Rinaldi, and 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
- Eric S. Egge, Restricted permutations related to Fibonacci numbers and k-generalized Fibonacci numbers, arXiv:math/0109219 [math.CO], 2001.
- Eric S. Egge, Restricted 3412-Avoiding Involutions, arXiv:math/0307050 [math.CO], 2003.
- Eric S. Egge and Toufik Mansour, Restricted permutations, Fibonacci numbers and k-generalized Fibonacci numbers, arXiv:math/0203226 [math.CO], 2002.
- Eric S. Egge and Toufik 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, and Gregory B. Sorkin, Strings with Maximally Many Distinct Subsequences and Substrings, Electronic J. Combinatorics 11 (1) (2004), Paper R8.
- Ivan 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.
- Michel Mollard, p-th order generalized Fibonacci cubes and maximal cubes in Fibonacci p-cubes, arXiv:2507.16387 [math.CO], 2025. See p. 3.
- Harold R. Parks and Dean C. Wills, Sum of k-bonacci Numbers, arXiv:2208.01224 [math.CO], 2022. See p. 5.
- Hsin-Po Wang and Chi-Wei Chin, On Counting Subsequences and Higher-Order Fibonacci Numbers, arXiv:2405.17499 [cs.IT], 2024. See p. 2.
Crossrefs
Programs
-
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 *) -
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
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
Comments