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
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 number of the elements in S(n). (See A122554 for a sequence defined in this way.) - John W. Layman, Nov 21 2007 [edited by Sela Fried, Feb 18 2026].
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)
Layman's conjecture is true (see Fried link). - Sela Fried, Feb 18 2026
REFERENCES
Ralph P. Grimaldi, 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
Kassie Archer and Noel Bourne, Pattern avoidance in compositions and powers of permutations, arXiv:2505.05218 [math.CO], 2025. See p. 6.
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).
Sela Fried, Proof of two conjectures on Layman sets stated in A000126 and A122554, 2026.
Thomas Langley, Jeffrey Liese, and Jeffrey 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, doi: 10.1080/00150517.1965.12431407.
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) = 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
E.g.f.: exp(x/2)*(15*cosh(sqrt(5)*x/2) + 7*sqrt(5)*sinh(sqrt(5)*x/2))/5 - 2*exp(x) - exp(x)*x. - Stefano Spezia, Feb 23 2026
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
(PARI) vector(40, n, fibonacci(n+3) -(n+1)) \\ G. C. Greubel, Jul 09 2019
(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
(Magma) [Fibonacci(n+3)-(n+1): n in [1..40]]; // G. C. Greubel, Jul 09 2019
(SageMath) [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
KEYWORD
nonn,easy
AUTHOR
STATUS
approved