login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001924 Apply partial sum operator twice to Fibonacci numbers.
(Formerly M2645 N1053)
56
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

A107909(a(n)) = A000225(n) = 2^n - 1. - Reinhard Zumkeller, May 28 2005

(1, 3, 7, 14,...) = row sums of triangle A141289. - Gary W. Adamson, Jun 22 2008

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-2x+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

a(n) = A228074(n+1,3) for n > 1. - Reinhard Zumkeller, Aug 15 2013

REFERENCES

Bader AlBdaiwi, On the Number of Cycles in a Graph, arXiv preprint arXiv:1603.01807, 2016

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

T. D. Noe, Table of n, a(n) for n=0..500

J.-L. Baril, J.-M. Pallo, Motzkin subposet and Motzkin geodesics in Tamari lattices, 2013.

Ligia Loretta Cristea, Ivica Martinjak, Igor Urbiha, Hyperfibonacci Sequences and Polytopic Numbers, arXiv:1606.06228 [math.CO], 2016.

E. Kilic, P. Stanica, Generating matrices for weighted sums of second order linear recurrences, JIS 12 (2009) 09.2.7.

W. Lang, Problem B-858, Fibonacci Quarterly, 36 (1998), 373-374, Solutioibid. 37 (1999) 183-184.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23. [Annotated scanned copy]

Stacey Wagner, Enumerating Alternating Permutations with One Alternating Descent, DePaul Discoveries: Vol. 2: Iss. 1, Article 2.

Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

FORMULA

G.f.: x/((1-x-x^2)*(1-x)^2). Convolution of natural numbers n >= 1 with Fibonacci numbers F(k). a(n)=F(n+4)-(3+n). - Wolfdieter Lang

a(n) = a(n-1)+a(n-2)+n = Fib(n+4)-n-3 = a(n-1)+A000071(n+2) = A001891(n)-a(n-1) = n+A001891(n-1) = A065220(n+4)+1 = A000126(n+1)-1. - Henry Bottomley, Jan 03 2003

a(n) = sum(k=0, n, sum(i=0, k, F(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, F(k)*(n-k)). - Benoit Cloitre, Jun 07 2004

a(n) - a(n-1) = A101220(1,1,n). - Ross La Haye, May 31 2006

F(n) + a(n-3) = A133640(n). - Gary W. Adamson, Sep 19 2007

a(n) = Sum_{k=1..n} C(n-k+2,k+1), with n>=0. - Paolo P. Lava, Apr 16 2008

a(n) = A077880(-3-n) = 2*a(n-1) - a(n-3) + 1. - Michael Somos, Dec 31 2012

INVERT transform is A122595. PSUM transform is A014162. PSUMSIGN transform is A129696. BINOMIAL transform of A039834 with 0,1 prepended is this sequence. - Michael Somos, Dec 31 2012

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

From John M. Campbell, Feb 10 2013: (Start)

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

A001924:=-1/(z**2+z-1)/(z-1)**2; # Conjectured by Simon Plouffe in his 1992 dissertation. [This conjecture needs to have the numerator changed from -1 to -z. - Robert G. Wilson v ]

##

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

seq(a(n), n=0..40);  # Alois P. Heinz, Oct 05 2012

MATHEMATICA

Join[{b=0}, a=0; Table[c=b+a+n; a=b; b=c, {n, 1, 60}]] (* Vladimir Joseph Stephan Orlovsky, Dec 10 2008 *)

f[n_] := Fibonacci[n + 4] - 3 - n; Array[f, 32, 0] (* Or *)

Accumulate@ Accumulate@ Fibonacci@ Range[0, 31] (* Or *)

a[n_] := a[n] = a[n - 1] + a[n - 2] + n; a[0] = 0; a[1] = 1; Array[a, 32, 0]  (* Or *)

gf = x/(1 - 3 x + 2 x^2 + x^3 - x^4); CoefficientList[ Series[ gf, {x, 0, 31}], x] (* Robert G. Wilson v *)

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

(PARI) a(n)=fibonacci(n+4)-n-3 \\ Charles R Greathouse IV, Feb 24 2011

(Haskell)

a001924 n = a001924_list !! n

a001924_list = drop 3 $ zipWith (-) (tail a000045_list) [0..]

-- Reinhard Zumkeller, Nov 17 2013

(MAGMA) [Fibonacci(n+4)-(n+3): n in [0..50]]; // Vincenzo Librandi, Jun 23 2016

CROSSREFS

Cf. A000045, A001891, A133640, A141289.

Right-hand column 4 of triangle A011794.

Cf. A014162, A039834, A077880, A122595, A129696.

Cf. A065220.

Sequence in context: A036830 A014153 * A079921 A014168 A132109 A099854

Adjacent sequences:  A001921 A001922 A001923 * A001925 A001926 A001927

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

Description improved Jan 01 1997

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 April 28 12:16 EDT 2017. Contains 285575 sequences.