A000126 A nonlinear binomial sum. (Formerly M1103 N0421)

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

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

Alvaro Carbonero, Beth Anne Castellano, Gary Gordon, Charles Kulick, Karie Schmitz, and Brittany Shelton, Permutations of point sets in R_d, arXiv:2106.14140 [math.CO], 2021.

Tamsin Forbes and Tony Forbes, Hanoi revisited, Math. Gaz. 100, No. 549, 435-441 (2016).

T. Langley, J. Liese, and 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.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 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). - Simon Plouffe in his 1992 dissertation

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. - Paul Barry, Mar 06 2008

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

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
# alternative
A000126 := proc(n)
    combinat[fibonacci](n+3)-n-1 ;
end proc:
seq(A000126(n), n=1..40) ; # R. J. Mathar, Aug 05 2022

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
(Python)
def seq(n):
    if n < 0:
        return 1
    a, b = 1, 1
    for i in range(n + 1):
        a, b = b, a + b + i
    return a
[seq(i) for i in range(n)] # Reza K Ghazi, Mar 03 2019
(PARI) vector(40, n, fibonacci(n+3) -(n+1)) \\ G. C. Greubel, Jul 09 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 * A344611 A182716 A143281

Adjacent sequences: A000123 A000124 A000125 * A000127 A000128 A000129

Keyword

nonn,easy

Author

N. J. A. Sloane

Status

approved