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

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

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

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

Equals row 2 of the array in A180165, and the INVERTi transform of A125145. - Gary W. Adamson, Aug 14 2010

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 n-centipede graph. - Eric W. Weisstein, Sep 21 2017

From Gus Wiseman, May 19 2020: (Start)

Conjecture: Also the number of length n + 1 sequences that cover an initial interval of positive integers and whose non-adjacent parts are weakly decreasing. For example, (3,2,3,1,2) has non-adjacent 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 2-compositions 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

• Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
• Jean-Paul Allouche, Jeffrey Shallit, and Manon Stipulanti, Combinatorics on words and generating Dirichlet series of automatic sequences, arXiv:2401.13524 [math.CO], 2025. See p. 14.
• Joerg Arndt, Matters Computational (The Fxtbook), section 14.9 "Strings with no two consecutive zeros", pp.318-320.
• C. Bautista-Ramos and C. Guillen-Galvan, Fibonacci numbers of generalized Zykov sums, J. Integer Seq., 15 (2012), #12.7.8.
• Moussa Benoumhani, On the Modes of the Independence Polynomial of the Centipede, Journal of Integer Sequences, Vol. 15 (2012), #12.5.1.
• D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3 Example 7.
• Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
• P. Z. Chinn, R. Grimaldi, and S. Heubach, Tiling with Ls and Squares, J. Int. Sequences 10 (2007) #07.2.8.
• David Garth and Adam Gouge, Affinely Self-Generating Sets and Morphisms, Journal of Integer Sequences, Article 07.1.5, 10 (2007) 1-13.
• Juan B. Gil and Jessica A. Tomasko, Fibonacci colored compositions and applications, arXiv:2108.06462 [math.CO], 2021.
• Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
• Brian Hopkins and Stéphane Ouvry, Combinatorics of Multicompositions, arXiv:2008.04937 [math.CO], 2020.
• Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
• Tanya Khovanova, Recursive Sequences
• J. Shallit, Proof of Irvine's conjecture via mechanized guessing, arXiv preprint arXiv:2310.14252 [math.CO], October 22 2023.
• Eric Weisstein's World of Mathematics, Centipede Graph
• Eric Weisstein's World of Mathematics, Independent Vertex Set
• Eric Weisstein's World of Mathematics, Vertex Cover
• Index entries for linear recurrences with constant coefficients, signature (2,2).

Crossrefs

Cf. A180165, A125145, A026150, A030195, A080040, A083337, A106435, A108898.

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

Cf. A002605.

Programs

Haskell

a028859 n = a028859_list !! n
a028859_list =
   1 : 3 : map (* 2) (zipWith (+) a028859_list (tail a028859_list))
-- Reinhard Zumkeller, Oct 15 2011

Maple

a[0]:=1:a[1]:=3:for n from 2 to 24 do a[n]:=2*a[n-1]+2*a[n-2] 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 *)
LinearRecurrence[{2, 2}, {1, 3}, 20] (* Eric W. Weisstein, Jun 14 2017 *)

PARI

a(n)=([1,3;1,1]^n*[2;1])[2,1] \\ Charles R Greathouse IV, Mar 27 2012

PARI

A028859(n)=([1,1]*[2,2;1,0]^n)[1] \\ M. F. Hasler, Aug 06 2018

Formula

a(n) = a(n-1) + A052945(n) = A002605(n) + A002605(n-1).

G.f.: -(x+1)/(2*x^2+2*x-1).

a(n) = [(1+sqrt(3))^(n+2)-(1-sqrt(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[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n-1)= det A. - Milan Janjic, May 08 2010

a(n) = 3^n - A186244(n). - Toby Gottfried, Mar 07 2013

E.g.f.: exp(x)*(cosh(sqrt(3)*x) + 2*sinh(sqrt(3)*x)/sqrt(3)). - Stefano Spezia, Mar 02 2024

Extensions

Definition completed by M. F. Hasler, Aug 06 2018