

A028859


a(n+2) = 2*a(n+1) + 2*a(n); a(0) = 1, a(1) = 3.


39



1, 3, 8, 22, 60, 164, 448, 1224, 3344, 9136, 24960, 68192, 186304, 508992, 1390592, 3799168, 10379520, 28357376, 77473792, 211662336, 578272256, 1579869184, 4316282880, 11792304128, 32217174016, 88018956288, 240472260608, 656982433792, 1794909388800, 4903783645184, 13397386067968
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Number of words of length n without adjacent 0's from the alphabet {0,1,2}. For example, a(2) counts 01,02,10,11,12,20,21,22.  Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Jun 12 2001
Individually, both this sequence and A002605 are convergents to 1+sqrt(3). Mutually, both sequences are convergents to 2+sqrt(3) and 1+sqrt(3)/2.  Klaus E. Kastberg (kastberg(AT)hotkey.net.au), Nov 04 2001 [Can someone clarify what is meant by the obscure second phrase, "Mutually..."?  M. F. Hasler, Aug 06 2018]
Add a loop at two vertices of the graph C_3=K_3. a(n) counts walks of length n+1 between these vertices.  Paul Barry, Oct 15 2004
Prefaced with a 1 as (1 + x + 3x^2 + 8x^3 + 22x^4 + ...) = 1 / (1  x  2x^2  3x^3  5x^4  8x^5  13x^6  21x^7  ...).  Gary W. Adamson, Jul 28 2009
Pisano period lengths: 1, 1, 3, 1, 24, 3, 48, 1, 9, 24, 10, 3, 12, 48, 24, 1, 144, 9, 180, 24, ....  R. J. Mathar, Aug 10 2012
Also the number of independent vertex sets and vertex covers in the ncentipede graph.  Eric W. Weisstein, Sep 21 2017
Conjecture: Also the number of length n + 1 sequences that cover an initial interval of positive integers and whose nonadjacent parts are weakly decreasing. For example, (3,2,3,1,2) has nonadjacent pairs (3,3), (3,1), (3,2), (2,1), (2,2), (3,2), all of which are weakly decreasing, so is counted under a(11). The a(1) = 1 through a(3) = 8 sequences are:
(1) (11) (111)
(12) (121)
(21) (211)
(212)
(221)
(231)
(312)
(321)
The case of compositions is A333148, or A333150 for strict compositions, or A333193 for strictly decreasing parts. A version for ordered set partitions is A332872. Standard composition numbers of these compositions are A334966. Unimodal normal sequences are A227038. See also: A001045, A001523, A032020, A100471, A100881, A115981, A329398, A332836, A332872.
(End)
Number of 2compositions of n+1 restricted to parts 1 and 2 (and allowed zeros); see Hopkins & Ouvry reference.  Brian Hopkins, Aug 16 2020
The number of ternary strings of length n not containing 00. Complement of A186244.  R. J. Mathar, Feb 13 2022


REFERENCES

S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 73).


LINKS



FORMULA

G.f.: (x+1)/(2*x^2+2*x1).
a(n) = [(1+sqrt(3))^(n+2)(1sqrt(3))^(n+2)]/(4*sqrt(3)).  Emeric Deutsch, Feb 01 2005
If p[i]=fibonacci(i+1) and if A is the Hessenberg matrix of order n defined by: A[i,j]=p[ji+1], (i<=j), A[i,j]=1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n1)= det A.  Milan Janjic, May 08 2010
E.g.f.: exp(x)*(cosh(sqrt(3)*x) + 2*sinh(sqrt(3)*x)/sqrt(3)).  Stefano Spezia, Mar 02 2024


MAPLE

a[0]:=1:a[1]:=3:for n from 2 to 24 do a[n]:=2*a[n1]+2*a[n2] od: seq(a[n], n=0..24); # Emeric Deutsch


MATHEMATICA

a[n_]:=(MatrixPower[{{1, 3}, {1, 1}}, n].{{2}, {1}})[[2, 1]]; Table[a[n], {n, 0, 40}] (* Vladimir Joseph Stephan Orlovsky, Feb 20 2010 *)
Table[2^(n  1) Hypergeometric2F1[(1  n)/2, n/2, n, 2], {n, 20}] (* Eric W. Weisstein, Jun 14 2017 *)


PROG

(Haskell)
a028859 n = a028859_list !! n
a028859_list =
1 : 3 : map (* 2) (zipWith (+) a028859_list (tail a028859_list))


CROSSREFS

Cf. A155020 (same sequence with term 1 prepended).


KEYWORD

nonn,easy


AUTHOR



EXTENSIONS



STATUS

approved



