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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000126 A nonlinear binomial sum.
(Formerly M1103 N0421)
22
1, 2, 4, 8, 15, 27, 47, 80, 134, 222, 365, 597, 973, 1582, 2568, 4164, 6747, 10927, 17691, 28636, 46346, 75002, 121369, 196393, 317785, 514202, 832012, 1346240, 2178279, 3524547, 5702855, 9227432, 14930318, 24157782, 39088133, 63245949 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

a(n)-1 counts ternary numbers with no 0 digit (A007931) and at least one 2 digit, where the total of ternary digits is <= n. E.g. a(4)-1 = 7: 2 12 21 22 112 121 211. - Frank Ellermann, Dec 02 2001

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

a(n) is the permanent of the n X n 0-1 matrix whose (i,j) entry is 1 iff i=1 or j=n or |i-j|<=1. For example, a(5)=15 is per([[1, 1, 1, 1, 1], [1, 1, 1, 0, 1], [0, 1, 1, 1, 1], [0, 0, 1, 1, 1], [0, 0, 0, 1, 1]]). - David Callan, Jun 07 2006

Conjecture. Let S(1)={1} and, for n>1, let S(n) be the smallest set containing x+1 and 2x+1 for each element x in S(n-1). Then a(n) is the sum of the elements in S(n). (See A122554 for a sequence defined in this way.) - John W. Layman, Nov 21 2007

a(n+1) indexes the corner blocks on the Fibonacci spiral built from blocks of unit area (using F(1) and F(2) as the sides of the first block). - Paul Barry, Mar 06 2008

The number of length n binary words with fewer than 2 0-digits between any pair of consecutive 1-digits. [From Jeffrey Liese, Dec 23 2010]

If b(n) = a(n+1) then b(0) = 1 and 2*b(n) >= b(n+1) for all n > 1 which is sufficient for b(n) to be a complete sequence. - Frank M Jackson, Mar 17 2013

REFERENCES

Grimaldi, Ralph P. A generalization of the Fibonacci sequence. Proceedings of the seventeenth Southeastern international conference on combinatorics, graph theory, and computing (Boca Raton, Fla., 1986). Congr. Numer. 54 (1986), 123--128. MR0885268 (89f:11030). - N. J. A. Sloane, Apr 08 2012

D. A. Lind, On a class of nonlinear binomial sums, Fib. Quart., 3 (1965), 292-298.

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 = 1..201

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.

Index to sequences with linear recurrences with constant coefficients, signature (3,-2,-1,1).

FORMULA

G.f.: -(1 - x + x^3 ) / (( x^2 + x - 1 )*( x - 1 )^2).

a(n) = Fib(n+4)-(n+1) = a(n-1)+a(n-2)+n-2 = A001924(n-1)+1 = A065220(n+3)+2. - Henry Bottomley , Oct 22 2001

a(n)=2*a(n-1)-a(n-3)+1 - Frank Adams-Watters, Jan 13 2006

a(n+1)=1+sum{k=0..n, F(k+2)-1}=sum{k=0..n, F(k+2)}-n=F(n+4)-n-2; - Paul Barry, Mar 06 2008

a(0)=1, a(1)=2, a(2)=4, a(3)=8, a(n)=3*a(n-1)-2*a(n-2)-a(n-3)+a(n-4) [From Harvey P. Dale, May 05 2011]

Closed-form without extra leading 1: ((15+7*sqrt(5))*((1+sqrt(5))/2)^n+(15-7*sqrt(5))*((1-sqrt(5))/2)^n-10*n-20)/10; closed-form with extra leading 1: ((20+8*sqrt(5))*((1+sqrt(5))/2)^n+(20-8*sqrt(5))*((1-sqrt(5))/2)^n-20*n-20)/20. [Tim Monahan, Jul 16 2011]

G.f. for closed-form with extra leading 1: (1-2*x+x^2+x^3)/((1-x-x^2)*(x-1)^2). (Tim Monahan, Jul 17 2011)

MAPLE

A000126:=-(1-z+z**3)/(z**2+z-1)/(z-1)**2; [Conjectured by Simon Plouffe in his 1992 dissertation.]

a:= n-> (Matrix([[1, 1, 1, 2]]). Matrix(4, (i, j)-> if (i=j-1) then 1 elif j=1 then [3, -2, -1, 1][i] else 0 fi)^n)[1, 2]; seq (a(n), n=1..36); # Alois P. Heinz, Aug 26 2008

MATHEMATICA

LinearRecurrence[{3, -2, -1, 1}, {1, 2, 4, 8}, 40] (* or *) CoefficientList[ Series[-(1-x+x^3)/((x^2+x-1)(x-1)^2), {x, 0, 40}], x]  (* Harvey P. Dale, Apr 24 2011 *)

PROG

(PARI) Vec((1-x+x^3)/(1-x-x^2)/(1-x)^2+O(x^99)) \\ Charles R Greathouse IV, Oct 06 2011

CROSSREFS

Heap-transform of A000071 - John Layman.

Cf. A066067, A001924, A065220.

Cf. A007931: binary strings with leading 0's, or ternary strings without 0's.

Differences are A000071.

Cf. A122554.

Sequence in context: A222150 A222151 A222152 * A182716 A143281 A098057

Adjacent sequences:  A000123 A000124 A000125 * A000127 A000128 A000129

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified August 21 02:16 EDT 2014. Contains 245836 sequences.