login
Hit polynomials; convolution of natural numbers with Fibonacci numbers F(2), F(3), F(4), ....
(Formerly M3384 N1365)
36

%I M3384 N1365 #92 Sep 04 2022 12:54:45

%S 0,1,4,10,21,40,72,125,212,354,585,960,1568,2553,4148,6730,10909,

%T 17672,28616,46325,74980,121346,196369,317760,514176,831985,1346212,

%U 2178250,3524517,5702824,9227400,14930285,24157748,39088098,63245913,102334080,165580064

%N Hit polynomials; convolution of natural numbers with Fibonacci numbers F(2), F(3), F(4), ....

%C a(n) is the sum of the n-th row of the triangle in A119457 for n > 0. - _Reinhard Zumkeller_, May 20 2006

%C Convolution of odds (A005408) with Fibonacci numbers (A000045). - _Graeme McRae_, Jun 06 2006

%C Equals row sums of triangle A152203. - _Gary W. Adamson_, Nov 29 2008

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

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

%D J. Riordan, The enumeration of permutations with three-ply staircase restrictions, unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963. (See A001883)

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Vincenzo Librandi, <a href="/A001891/b001891.txt">Table of n, a(n) for n = 0..1000</a>

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H N. J. A. Sloane, <a href="/A001883/a001883_21.pdf">Annotated copy of Riordan's Three-Ply Staircase paper</a> (unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963)

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2,-1,1).

%F G.f.: x*(1+x)/((1-x-x^2)*(1-x)^2). - _Simon Plouffe_ in his 1992 dissertation

%F a(n) = Fibonacci(n+5) - (5+2*n). - _Wolfdieter Lang_

%F a(n) = a(n-1) + a(n-2) + (2n+1); a(-x)=0. - _Barry E. Williams_, Mar 27 2000

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

%F a(n) - a(n-1) = A101220(2,1,n). - _Ross La Haye_, May 31 2006

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

%t LinearRecurrence[{3,-2,-1,1}, {0,1,4,10}, 40] (* _Vladimir Joseph Stephan Orlovsky_, Feb 16 2012 *)

%t Table[Fibonacci[n+5] -(2*n+5), {n,0,40}] (* _G. C. Greubel_, Jul 06 2019 *)

%t maxDiff = 2;

%t Map[Length[Select[Map[{#, Max[Differences[#]]} &,

%t Drop[Subsets[Range[#]], # + 1]], #[[2]] <= maxDiff &]] &,

%t Range[16]] (* _Peter J. C. Moses_, Aug 14 2022 *)

%o (Magma) [Fibonacci(n+5)-(5+2*n): n in [0..40]]; // _Vincenzo Librandi_, Jun 07 2013

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

%o (Sage) [fibonacci(n+5) -2*n-5 for n in (0..40)] # _G. C. Greubel_, Jul 06 2019

%o (GAP) List([0..40], n-> Fibonacci(n+5) -2*n-5) # _G. C. Greubel_, Jul 06 2019

%Y Partial sums of A001911.

%Y A diagonal of triangle in A080061.

%Y Right-hand column 5 of triangle A011794.

%Y Cf. A001883-A001890. A152203.

%Y Cf. A000295, A356619, A356620, A356621.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_, _Simon Plouffe_