login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000126 A nonlinear binomial sum.
(Formerly M1103 N0421)
42
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
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.
Forbes, Tamsin; Forbes, Tony Hanoi revisited, Math. Gaz. 100, No. 549, 435-441 (2016).
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.
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
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. A007931: binary strings with leading 0's, or ternary strings without 0's.
Differences are A000071.
Cf. A122554.
Cf. A000045.
Sequence in context: A222150 A222151 A222152 * A344611 A182716 A143281
KEYWORD
nonn,easy
AUTHOR
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 04:58 EDT 2024. Contains 370952 sequences. (Running on oeis4.)