|
%I #120 Mar 02 2024 13:13:02
%S 1,3,8,22,60,164,448,1224,3344,9136,24960,68192,186304,508992,1390592,
%T 3799168,10379520,28357376,77473792,211662336,578272256,1579869184,
%U 4316282880,11792304128,32217174016,88018956288,240472260608,656982433792,1794909388800,4903783645184,13397386067968
%N a(n+2) = 2*a(n+1) + 2*a(n); a(0) = 1, a(1) = 3.
%C 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
%C 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]
%C 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
%C 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
%C Equals row 2 of the array in A180165, and the INVERTi transform of A125145. - _Gary W. Adamson_, Aug 14 2010
%C 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
%C Also the number of independent vertex sets and vertex covers in the n-centipede graph. - _Eric W. Weisstein_, Sep 21 2017
%C From _Gus Wiseman_, May 19 2020: (Start)
%C 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:
%C (1) (11) (111)
%C (12) (121)
%C (21) (211)
%C (212)
%C (221)
%C (231)
%C (312)
%C (321)
%C 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.
%C (End)
%C 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
%C The number of ternary strings of length n not containing 00. Complement of A186244. - _R. J. Mathar_, Feb 13 2022
%D S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 73).
%H Reinhard Zumkeller, <a href="/A028859/b028859.txt">Table of n, a(n) for n = 0..1000</a>
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 14.9 "Strings with no two consecutive zeros", pp.318-320.
%H C. Bautista-Ramos and C. Guillen-Galvan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Bautista/bautista4.html">Fibonacci numbers of generalized Zykov sums</a>, J. Integer Seq., 15 (2012), #12.7.8.
%H Moussa Benoumhani, <a href="http://www.emis.de/journals/JIS/VOL15/Benoumhani/benoumhani8.html">On the Modes of the Independence Polynomial of the Centipede</a>, Journal of Integer Sequences, Vol. 15 (2012), #12.5.1.
%H D. Birmajer, J. B. Gil, and M. D. Weiner, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Gil/gil6.html">On the Enumeration of Restricted Words over a Finite Alphabet</a>, J. Int. Seq. 19 (2016) # 16.1.3 Example 7.
%H Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, <a href="https://www.emis.de/journals/JIS/VOL18/Szczyrba/sz3.html">Analytic Representations of the n-anacci Constants and Generalizations Thereof</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
%H P. Z. Chinn, R. Grimaldi, and S. Heubach, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Heubach/heubach40.html">Tiling with Ls and Squares</a>, J. Int. Sequences 10 (2007) #07.2.8.
%H David Garth and Adam Gouge, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Garth/garth14.html">Affinely Self-Generating Sets and Morphisms</a>, Journal of Integer Sequences, Article 07.1.5, 10 (2007) 1-13.
%H Juan B. Gil and Jessica A. Tomasko, <a href="https://arxiv.org/abs/2108.06462">Fibonacci colored compositions and applications</a>, arXiv:2108.06462 [math.CO], 2021.
%H Aoife Hennessy, <a href="http://repository.wit.ie/1693/1/AoifeThesis.pdf">A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths</a>, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
%H Brian Hopkins and Stéphane Ouvry, <a href="https://arxiv.org/abs/2008.04937">Combinatorics of Multicompositions</a>, arXiv:2008.04937 [math.CO], 2020.
%H Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Janjic/janjic63.html">On Linear Recurrence Equations Arising from Compositions of Positive Integers</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>
%H J. Shallit, <a href="https://arxiv.org/abs/2310.14252">Proof of Irvine's conjecture via mechanized guessing</a>, arXiv preprint arXiv:2310.14252 [math.CO], October 22 2023.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CentipedeGraph.html">Centipede Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/VertexCover.html">Vertex Cover</a>
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,2).
%F a(n) = a(n-1) + A052945(n) = A002605(n) + A002605(n-1).
%F G.f.: -(x+1)/(2*x^2+2*x-1).
%F a(n) = [(1+sqrt(3))^(n+2)-(1-sqrt(3))^(n+2)]/(4*sqrt(3)). - _Emeric Deutsch_, Feb 01 2005
%F 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
%F a(n) = 3^n - A186244(n). - _Toby Gottfried_, Mar 07 2013
%F E.g.f.: exp(x)*(cosh(sqrt(3)*x) + 2*sinh(sqrt(3)*x)/sqrt(3)). - _Stefano Spezia_, Mar 02 2024
%p 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_
%t 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 *)
%t Table[2^(n - 1) Hypergeometric2F1[(1 - n)/2, -n/2, -n, -2], {n, 20}] (* _Eric W. Weisstein_, Jun 14 2017 *)
%t LinearRecurrence[{2, 2}, {1, 3}, 20] (* _Eric W. Weisstein_, Jun 14 2017 *)
%o (Haskell)
%o a028859 n = a028859_list !! n
%o a028859_list =
%o 1 : 3 : map (* 2) (zipWith (+) a028859_list (tail a028859_list))
%o -- _Reinhard Zumkeller_, Oct 15 2011
%o (PARI) a(n)=([1,3;1,1]^n*[2;1])[2,1] \\ _Charles R Greathouse IV_, Mar 27 2012
%o (PARI) A028859(n)=([1,1]*[2,2;1,0]^n)[1] \\ _M. F. Hasler_, Aug 06 2018
%Y Cf. A180165, A125145, A026150, A030195, A080040, A083337, A106435, A108898.
%Y Cf. A155020 (same sequence with term 1 prepended).
%Y Cf. A002605.
%K nonn,easy
%O 0,2
%A _N. J. A. Sloane_
%E Definition completed by _M. F. Hasler_, Aug 06 2018
|
