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

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000126 A nonlinear binomial sum.
(Formerly M1103 N0421)
39
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. - 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

From Gus Wiseman, Feb 10 2019: (Start)

Also the number of non-singleton subsets of {1, ..., n + 1} with no successive elements. For example, the a(5) = 15 subsets are:

  {},

  {1,3}, {1,4}, {1,5}, {1,6}, {2,4}, {2,5}, {2,6}, {3,5}, {3,6}, {4,6},

  {1,3,5}, {1,3,6}, {1,4,6}, {2,4,6}.

Also the number of binary sequences with all zeros or at least 2 ones and no adjacent ones. For example, the a(1) = 1 through a(4) = 8 sequences are:

  (00)  (000)  (0000)  (00000)

        (101)  (0101)  (00101)

               (1001)  (01001)

               (1010)  (01010)

                       (10001)

                       (10010)

                       (10100)

                       (10101)

(End)

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

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

T. Langley, J. Liese, J. Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order , J. Int. Seq. 14 (2011) # 11.4.2

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

Richard J. Mathar, The Kepler binary tree of reduced fractions, 2017.

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 entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

FORMULA

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

From Henry Bottomley, Oct 22 2001: (Start)

a(n) = Fibonacci(n+3) - (n+1) = a(n-1) + a(n-2) + n - 2

a(n) = A001924(n-1) + 1 = A065220(n+3) + 2. (End)

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

a(n+1) = 1 + Sum_{k=0..n} (Fibonacci(k+2) - 1) = Sum_{k=0..n} Fibonacci(k+2) - n = Fibonacci(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). - 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 *)

Table[Length[Select[Subsets[Range[n]], Min@@Abs[Subtract@@@Partition[#, 2, 1, 1]]>1&]], {n, 15}] (* Gus Wiseman, Feb 10 2019 *)

PROG

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

(PARI) vector(40, n, fibonacci(n+3) -(n+1)) \\ G. C. Greubel, Jul 09 2019

(Python)

def a(n):

    if n < 0:

        return 1

    n = int(n)

    s, a, b = [], 1, 1

    for i in range(n+1):

        s.append(b)

        a, b = b, a+b+i

    return s[n]

[a(n) for n in range(40)] # Reza K Ghazi, Mar 03 2019

(MAGMA) [Fibonacci(n+3)-(n+1): n in [1..40]]; // G. C. Greubel, Jul 09 2019

(Sage) [fibonacci(n+3)-(n+1) for n in (1..40)] # G. C. Greubel, Jul 09 2019

(GAP) List([1..40], n-> Fibonacci(n+3)-(n+1)); # G. C. Greubel, Jul 09 2019

CROSSREFS

Heap-transform of A000071. - John W. Layman

Cf. A066067, A001924, A065220.

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

Differences are A000071.

Cf. A122554.

Cf. A005251, A066982, A169985.

Cf. A000045.

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 | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 11 07:37 EST 2019. Contains 329914 sequences. (Running on oeis4.)