|
|
A001891
|
|
Hit polynomials; convolution of natural numbers with Fibonacci numbers F(2), F(3), F(4), ....
(Formerly M3384 N1365)
|
|
36
|
|
|
0, 1, 4, 10, 21, 40, 72, 125, 212, 354, 585, 960, 1568, 2553, 4148, 6730, 10909, 17672, 28616, 46325, 74980, 121346, 196369, 317760, 514176, 831985, 1346212, 2178250, 3524517, 5702824, 9227400, 14930285, 24157748, 39088098, 63245913, 102334080, 165580064
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Define a triangle by T(n,0) = n*(n+1)+1, T(n,n) = 1, and T(r,c) = T(r-1,c) + T(r-2,c-1). This triangle starts: 1; 3,1; 7,2,1; 13,5,2,1; 21,12,4,2,1; the sum of terms in row n is a(n+1). - J. M. Bergot, Apr 23 2013
a(n) = number of k-tuples (u(1), u(2), ..., u(k)) with 1 <= u(1) < u(2) < ... < u(k) <= n such that u(i) - u(i-1) <= 2 for i = 2,...,k. Changing the bound from 2 to 3, then 4, then 5, yields A356619, A356620, A356621. The patterns suggest that the limiting sequence as the bound increases is A000295. - Clark Kimberling, Aug 24 2022
|
|
REFERENCES
|
J. Riordan, The enumeration of permutations with three-ply staircase restrictions, unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963. (See A001883)
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
G.f.: x*(1+x)/((1-x-x^2)*(1-x)^2). - Simon Plouffe in his 1992 dissertation
a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-4). - Sam Lachterman (slachterman(AT)fuse.net), Sep 22 2003
a(n) = (-3 + (2^(-1-n)*((1-sqrt(5))^n*(-11+5*sqrt(5)) + (1+sqrt(5))^n*(11+5*sqrt(5)))) / sqrt(5) - 2*(1+n)). - Colin Barker, Mar 11 2017
|
|
MATHEMATICA
|
Table[Fibonacci[n+5] -(2*n+5), {n, 0, 40}] (* G. C. Greubel, Jul 06 2019 *)
maxDiff = 2;
Map[Length[Select[Map[{#, Max[Differences[#]]} &,
Drop[Subsets[Range[#]], # + 1]], #[[2]] <= maxDiff &]] &,
|
|
PROG
|
(PARI) a(n)=([0, 1, 0, 0; 0, 0, 1, 0; 0, 0, 0, 1; 1, -1, -2, 3]^n*[0; 1; 4; 10])[1, 1] \\ Charles R Greathouse IV, Apr 08 2016
(Sage) [fibonacci(n+5) -2*n-5 for n in (0..40)] # G. C. Greubel, Jul 06 2019
(GAP) List([0..40], n-> Fibonacci(n+5) -2*n-5) # G. C. Greubel, Jul 06 2019
|
|
CROSSREFS
|
Right-hand column 5 of triangle A011794.
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|