|
| |
|
|
A001924
|
|
Apply partial sum operator twice to Fibonacci numbers.
(Formerly M2645 N1053)
|
|
64
|
|
|
|
0, 1, 3, 7, 14, 26, 46, 79, 133, 221, 364, 596, 972, 1581, 2567, 4163, 6746, 10926, 17690, 28635, 46345, 75001, 121368, 196392, 317784, 514201, 832011, 1346239, 2178278, 3524546, 5702854, 9227431, 14930317, 24157781, 39088132, 63245948, 102334116, 165580101
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Leading coefficients in certain rook polynomials (for n>=2; see p. 18 of the Riordan paper). - Emeric Deutsch, Mar 08 2004
a(n) is the number of nonempty subsets of {1,2,...,n} such that the difference of successive elements is at most 2. See example below. Generally, the o.g.f. for the number of nonempty subsets of {1,2,...,n} such that the difference of successive elements is <= k is: x/((1-x)*(1-2*x+x^(k+1))). Cf. A000217 the case for k=1, A001477 the case for k=0 (counts singleton subsets). - Geoffrey Critzer, Feb 17 2012
-Fibonacci(n-2) = p(-1) where p(x) is the unique degree-n polynomial such that p(k) = a(k) for k = 0, 1, ..., n. - Michael Somos, Dec 31 2012
a(n) is the number of bit strings of length n+1 with the pattern 00 and without the pattern 011, see example. - John M. Campbell, Feb 10 2013
|
|
|
REFERENCES
|
J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23.
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
|
Wolfdieter Lang, Problem B-858, Fibonacci Quarterly, 36 (1998), 373-374, Solution, ibid. 37 (1999) 183-184.
|
|
|
FORMULA
|
G.f.: x/((1-x-x^2)*(1-x)^2).
Convolution of natural numbers n >= 1 with Fibonacci numbers F(k).
a(n) = Fibonacci(n+4) - (3+n). (End)
a(n) = a(n-1) + a(n-2) + n = a(n-1) + A000071(n+2).
a(n) = Sum_{k=0..n} Sum_{i=0..k} Fibonacci(i). - Benoit Cloitre, Jan 26 2003
a(n) = (sqrt(5)/2 + 1/2)^n*(7*sqrt(5)/10 + 3/2) + (3/2 - 7*sqrt(5)/10)*(sqrt(5)/2 - 1/2)^n*(-1)^n - n - 3. - Paul Barry, Mar 26 2003
a(n) = Sum_{k=0..n} Sum_{i=0..n} i * C(n-k,k-i). - Wesley Ivan Hurt, Sep 21 2017
E.g.f.: exp(x/2)*(15*cosh(sqrt(5)*x/2) + 7*sqrt(5)*sinh(sqrt(5)*x/2))/5 - exp(x)*(3 + x). - Stefano Spezia, Jun 25 2022
|
|
|
EXAMPLE
|
a(5) = 26 because there are 31 nonempty subsets of {1,2,3,4,5} but 5 of these have successive elements that differ by 3 or more: {1,4}, {1,5}, {2,5}, {1,2,5}, {1,4,5}. - Geoffrey Critzer, Feb 17 2012
There are a(5) = 26 bit strings with the pattern 00 and without the pattern 011 of length 5+1:
000000, 000001, 000010, 000100, 000101, 001000,
001001, 001010, 010000, 010001, 010010, 010100,
100000, 100001, 100010, 100100, 100101, 101000, 101001,
110000, 110001, 110010, 110100, 111000, 111001, 111100.
(End)
|
|
|
MAPLE
|
##
a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <1|-1|-2|3>>^n.
<<0, 1, 3, 7>>)[1, 1]:
|
|
|
MATHEMATICA
|
LinearRecurrence[{3, -2, -1, 1}, {0, 1, 3, 7}, 40] (* Harvey P. Dale, Jan 24 2015 *)
Nest[Accumulate, Fibonacci[Range[0, 40]], 2] (* Harvey P. Dale, Jun 15 2016 *)
|
|
|
PROG
|
(Haskell)
a001924 n = a001924_list !! n
a001924_list = drop 3 $ zipWith (-) (tail a000045_list) [0..]
(Sage) [fibonacci(n+4) -n-3 for n in (0..40)] # G. C. Greubel, Jul 08 2019
(GAP) List([0..40], n-> Fibonacci(n+4) -n-3) # G. C. Greubel, Jul 08 2019
|
|
|
CROSSREFS
|
Right-hand column 4 of triangle A011794.
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
