|
| |
|
|
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\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
_Simon Plouffe_, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}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] (* From 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,changed
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
STATUS
|
approved
|
| |
|
|
