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

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

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

...

NB: 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

(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

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 May 25 14:45 EDT 2018. Contains 304562 sequences. (Running on oeis4.)