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

%I

%S 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,

%T 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,

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

%N Array F(k,n) read by antidiagonals: k-generalized Fibonacci numbers in row k >= 1, starting (0, 1, 1, ...) for column n >= 0.

%C 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.

%C 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).

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

%H Alois P. Heinz, <a href="/A092921/b092921.txt">Antidiagonals n = 0..140, flattened</a>

%H E. S. Egge, <a href="http://arXiv.org/abs/math.CO/0109219">Restricted permutations related to Fibonacci numbers and k-generalized Fibonacci numbers</a>, arXiv:math/0109219 [math.CO], 2001.

%H E. S. Egge, <a href="http://arXiv.org/abs/math.CO/0307050">Restricted 3412-Avoiding Involutions</a>, arXiv:math/0307050 [math.CO], 2003.

%H E. S. Egge and T. Mansour, <a href="http://arXiv.org/abs/math.CO/0203226">Restricted permutations, Fibonacci numbers and k-generalized Fibonacci numbers</a>, arXiv:math/0203226 [math.CO], 2002.

%H E. S. Egge and T. Mansour, <a href="http://arXiv.org/abs/math.CO/0209255">231-avoiding involutions and Fibonacci numbers</a>, arXiv:math/0209255 [math.CO], 2002.

%H Nathaniel D. Emerson, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Emerson/emerson6.html">A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.

%H Abraham Flaxman, Aram W. Harrow, Gregory B. Sorkin, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r8">Strings with Maximally Many Distinct Subsequences and Substrings</a>, Electronic J. Combinatorics 11 (1) (2004), Paper R8.

%H I. Flores, <a href="http://www.fq.math.ca/Scanned/5-3/flores.pdf">k-Generalized Fibonacci numbers</a>, Fib. Quart., 5 (1967), 258-266.

%H H. Gabai, <a href="http://www.fq.math.ca/Scanned/8-1/gabai.pdf">Generalized Fibonacci k-sequences</a>, Fib. Quart., 8 (1970), 31-38.

%H R. Kemp, <a href="http://dx.doi.org/10.1002/rsa.3240050111">Balanced ordered trees</a>, Random Structures and Alg., 5 (1994), pp. 99-121.

%H E. P. Miles jr., <a href="http://www.jstor.org/stable/2308649">Generalized Fibonacci numbers and associated matrices</a>, The Amer. Math. Monthly, 67 (1960) 745-752.

%H M. D. Miller, <a href="http://www.jstor.org/stable/2316316">On generalized Fibonacci numbers</a>, The Amer. Math. Monthly, 78 (1971) 1108-1109.

%F 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.

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

%F F(k,n) = 2^(n-2) for 1 < n <= k+1. - _M. F. Hasler_, Apr 20 2018

%e Array begins:

%e 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...

%e 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...

%e 1, 3, 4, 4, 4, 4, 4, 4, 4, 4, ...

%e 1, 5, 7, 8, 8, 8, 8, 8, 8, 8, ...

%e 1, 8, 13, 15, 16, 16, 16, 16, 16, 16, ...

%e 1, 13, 24, 29, 31, 32, 32, 32, 32, 32, ...

%e 1, 21, 44, 56, 61, 63, 64, 64, 64, 64, ...

%e 1, 34, 81, 108, 120, 125, 127, 128, 128, 128, ...

%e 1, 55, 149, 208, 236, 248, 253, 255, 256, 256, ...

%e ...

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

%e From _Peter Luschny_, Aug 12 2015: (Start)

%e As a triangle counting compositions of n with largest part k:

%e n\k]| [0][1] [2] [3] [4][5][6][7][8][9]

%e [0] | [0]

%e [1] | [0, 1]

%e [2] | [0, 1, 1]

%e [3] | [0, 1, 1, 1]

%e [4] | [0, 1, 2, 1, 1]

%e [5] | [0, 1, 3, 2, 1, 1]

%e [6] | [0, 1, 5, 4, 2, 1, 1]

%e [7] | [0, 1, 8, 7, 4, 2, 1, 1]

%e [8] | [0, 1, 13, 13, 8, 4, 2, 1, 1]

%e [9] | [0, 1, 21, 24, 15, 8, 4, 2, 1, 1]

%e 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].

%e (End)

%p F:= proc(k, n) option remember; `if`(n<2, n,

%p add(F(k, n-j), j=1..min(k,n)))

%p end:

%p seq(seq(F(k, d+1-k), k=1..d+1), d=0..12); # _Alois P. Heinz_, Nov 02 2016

%t F[k_, n_] := F[k, n] = If[n<2, n, Sum[F[k, n-j], {j, 1, Min[k, n]}]];

%t Table[F[k, d+1-k], {d, 0, 12}, {k, 1, d+1}] // Flatten (* _Jean-Fran├žois Alcover_, Jan 11 2017, translated from Maple *)

%o (PARI) F(k,n)=if(n<2,if(n<1,0,1),sum(i=1,k,F(k,n-i)))

%o (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

%o (Sage)

%o # As a triangle of compositions of n with largest part k.

%o C = lambda n,k: Compositions(n, max_part=k, inner=[k]).cardinality()

%o for n in (0..9): [C(n,k) for k in (0..n)] # _Peter Luschny_, Aug 12 2015

%Y Rows converge to A166444: each column n converges to A166444(n) (= 2^(n-2) = A000079(n-2) for n >= 2).

%Y Rows 1-8 are (shifted) A057427, A000045, A000073, A000078, A001591, A001592, A066178, A079262.

%Y Essentially a reflected version of A048887. See A048004 and A126198 for closely related arrays.

%Y Cf. A066099.

%K nonn,tabl

%O 0,12

%A _Ralf Stephan_, Apr 17 2004

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 August 18 16:26 EDT 2018. Contains 313833 sequences. (Running on oeis4.)