login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A092921 Array F(k,n) read by antidiagonals: k-generalized Fibonacci numbers. 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

LINKS

Alois P. Heinz, Antidiagonals n = 0..140, flattened

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 for n<=0, F(k,n)=0.

G.f.: x/(1-Sum_{i=1..k}, x^i).

EXAMPLE

Array begins:

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

...

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

(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 2^(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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 21 07:18 EST 2018. Contains 299390 sequences. (Running on oeis4.)