login
a(n) = 2*a(n-1) + a(n-2) - a(n-3), with a(0) = a(1) = 0, a(2) = 1.
(Formerly M1396)
59

%I M1396 #189 Aug 20 2023 10:48:45

%S 0,0,1,2,5,11,25,56,126,283,636,1429,3211,7215,16212,36428,81853,

%T 183922,413269,928607,2086561,4688460,10534874,23671647,53189708,

%U 119516189,268550439,603427359,1355888968,3046654856,6845771321,15382308530,34563733525

%N a(n) = 2*a(n-1) + a(n-2) - a(n-3), with a(0) = a(1) = 0, a(2) = 1.

%C Let u(k), v(k), w(k) be defined by u(1)=1, v(1)=0, w(1)=0 and u(k+1)=u(k)+v(k)+w(k), v(k+1)=u(k)+v(k), w(k+1)=u(k); then {u(n)} = 1,1,3,6,14,31,... (A006356 with an extra initial 1), {v(n)} = 0,1,2,5,11,25,... (this sequence with its initial 0 deleted) and {w(n)} = {u(n)} prefixed by an extra 0 = A077998 with an extra initial 0. - _Benoit Cloitre_, Apr 05 2002. Also u(k)^2+v(k)^2+w(k)^2 = u(2k). - _Gary W. Adamson_, Dec 23 2003

%C Form the graph with matrix A=[1, 1, 1; 1, 0, 0; 1, 0, 1]. Then A006054 counts walks of length n between the vertex of degree 1 and the vertex of degree 3. - _Paul Barry_, Oct 02 2004

%C Form the digraph with matrix [1,1,0; 1,0,1; 1,1,1]. A006054(n) counts walks of length n between the vertices with loops. - _Paul Barry_, Oct 15 2004

%C Nonzero terms = INVERT transform of (1, 1, 2, 2, 3, 3, ...). Example: 56 = (1, 1, 2, 5, 11, 25) dot (3, 3, 2, 2, 1, 1) = (3 + 3 + 4 + 10 + 11 + 25). - _Gary W. Adamson_, Apr 20 2009

%C -a(n+1) appears in the formula for the nonpositive powers of rho:= 2*cos(Pi/7), the ratio of the smaller diagonal in the heptagon to the side length s=2*sin(Pi/7), when expressed in the basis <1,rho,sigma>, with sigma:=rho^2-1, the ratio of the larger heptagon diagonal to the side length, as follows. rho^(-n) = C(n)*1 + C(n-1)*rho - a(n+1)*sigma, n >= 0, with C(n)=A077998(n), C(-1):=0. See the Steinbach reference, and a comment under A052547.

%C If, with the above notations, the power basis of the field Q(rho) is taken one has for nonpositive powers of rho, rho^(-n) = a(n+2)*1 + A077998(n-1)*rho - a(n+1)*rho^2. For nonnegative powers see A006053. See also the Steinbach reference. - _Wolfdieter Lang_, May 06 2011

%C a(n) appears also in the nonnegative powers of sigma,(defined in the above comment, where also the basis is given). See a comment in A106803.

%C The sequence b(n):=(-1)^(n+1)*a(n) forms the negative part (i.e., with nonpositive indices) of the sequence (-1)^n*A006053(n+1). In this way we obtain what we shall call the Ramanujan-type sequence number 2a for the argument 2*Pi/7 (see the comment to Witula's formula in A006053). We have b(n) = -2*b(n-1) + b(n-2) + b(n-3) and b(n) * 49^(1/3) = (c(1)/c(4))^(1/3) * (c(1))^(-n) + (c(2)/c(1))^(1/3) * (c(2))^(-n) + (c(4)/c(2))^(1/3) * (c(4))^(-n) = (c(2)/c(1))^(1/3) * (c(1))^(-n+1) + (c(4)/c(2))^(1/3) * (c(2))^(-n+1) + (c(1)/c(4))^(1/3) * (c(4))^(-n+1), where c(j) := 2*cos(2*Pi*j/7) (for the proof, see the comments to A215112). - _Roman Witula_, Aug 06 2012

%C (1, 1, 2, 5, 11, 25, 56, ...) * (1, 0, 1, 0, 1, ...) = the variant of A006356: (1, 1, 3, 6, 14, 31, ...). - _Gary W. Adamson_, May 15 2013

%C The limit of a(n+1)/a(n) for n -> infinity is, for all generic sequences with this recurrence of signature (2,1,-1), sigma = rho^2-1, approximately 2.246979603, the length ratio (largest diagonal)/side in the regular heptagon (7-gon). For rho = 2*cos(Pi/7) and sigma see a comment above, and the P. Steinbach reference. Proof: a(n+1)/a(n) = 2 + 1/(a(n)/a(n-1)) - 1/((a(n)/a(n-1))*(a(n-1)/a(n-2))), leading in the limit to sigma^3 -2*sigma^2 - sigma + 1, which is solved by sigma = rho^2-1, due to C(7, rho) = 0 , with the minimal polynomial C(7, x) = x^3 - x^2 - 2*x + 1 of rho (see A187360). - _Wolfdieter Lang_, Nov 07 2013

%C Numbers of straight-chain aliphatic amino acids involving single, double or triple bonds (allowing adjacent double bonds) when cis/trans isomerism is neglected. - _Stefan Schuster_, Apr 19 2018

%C Let A(r,n) be the total number of ordered arrangements of an n+r tiling of r red squares and white tiles of total length n, where the individual tile lengths can range from 1 to n. A(r,0) corresponds to a tiling of r red squares only, and so A(r,0) = 1. Also, A(r,n)=0 for n<0. Let A_1(r,n) = Sum_{j=0..n} A(r,j). Then the expansion of 1/(1 - 2*x - x^2 + x^3) is A_1(0,n) + A_1(1,n-2) + A_1(n-4) + ... = a(n) without the initial two 0's. In general, the expansion of 1/(1 - 2*x -x^k + x^(k+1)) is equal to Sum_{j>=0} A_1(j, n-j*k). - _Gregory L. Simay_, May 25 2018

%D Jay Kappraff, Beyond Measure, A Guided Tour Through Nature, Myth and Number, World Scientific, 2002.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Vincenzo Librandi, <a href="/A006054/b006054.txt">Table of n, a(n) for n = 0..150</a>

%H C. P. de Andrade, J. P. de Oliveira Santos, E. V. P. da Silva and K. C. P. Silva, <a href="http://dx.doi.org/10.4236/ojdm.2013.31006">Polynomial Generalizations and Combinatorial Interpretations for Sequences Including the Fibonacci and Pell Numbers</a>, Open Journal of Discrete Mathematics, 2013, 3, 25-32 doi:10.4236/ojdm.2013.31006. - From _N. J. A. Sloane_, Feb 20 2013

%H Maximilian Fichtner, K. Voigt, S. Schuster, <a href="https://doi.org/10.1016/j.bbagen.2016.08.008">The tip and hidden part of the iceberg: Proteinogenic and non-proteinogenic aliphatic amino acids</a>, Biochimica et Biophysica Acta (BBA)-General, 2016, Volume 1861, Issue 1, Part A, January 2017, Pages 3258-3269.

%H Brian Hopkins, Hua Wang, <a href="https://arxiv.org/abs/2003.05291">Restricted Color n-color Compositions</a>, arXiv:2003.05291 [math.CO], 2020.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=434">Encyclopedia of Combinatorial Structures 434</a>

%H S. Morier-Genoud, V. Ovsienko, S. Tabachnikov, <a href="https://doi.org/10.1007/s00209-015-1520-x">Introducing supersymmetric frieze patterns and linear difference operators</a>, Math. Z. 281 (2015) 1061.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H R. Sachdeva and A. K. Agarwal, <a href="https://doi.org/10.1016/j.disc.2016.09.009">Combinatorics of certain restricted n-color composition functions</a>, Discrete Mathematics, 340, (2017), 361-372.

%H P. Steinbach, <a href="http://www.jstor.org/stable/2691048">Golden fields: a case for the heptagon</a>, Math. Mag. 70 (1997), no. 1, 22-31.

%H Alexey Ustinov, <a href="http://arxiv.org/abs/1503.04497">Supercontinuants</a>, arXiv:1503.04497 [math.NT], 2015.

%H Kai Wang, <a href="https://www.researchgate.net/publication/337943524_Fibonacci_Numbers_And_Trigonometric_Functions_Outline">Fibonacci Numbers And Trigonometric Functions Outline</a>, (2019).

%H Roman Witula, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Witula/witula17.html">Ramanujan Type Trigonometric Formulas: The General Form for the Argument 2*Pi/7</a>, Journal of Integer Sequences, Vol. 12 (2009), Article 09.8.5.

%H Roman Witula, D. Slota and A. Warzynski, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Slota/slota57.html">Quasi-Fibonacci Numbers of the Seventh Order</a>, J. Integer Seq., 9 (2006), Article 06.4.3.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-1).

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

%F Sum_{k=0..n+2} a(k) = A077850(n). - _Philippe Deléham_, Sep 07 2006

%F Let M = the 3 X 3 matrix [1,1,0; 1,2,1; 0,1,2], then M^n*[1,0,0] = [A080937(n-1), A094790(n), A006054(n-1)]. E.g., M^3*[1,0,0] = [5,9,5] = [A080937(2), A094790(3), A006054(2)]. - _Gary W. Adamson_, Feb 15 2006

%F a(n) = round(k*A006356(n-1)), for n>1, where k = 0.3568958678... = 1/(1+2*cos(Pi/7)). - _Gary W. Adamson_, Jun 06 2008

%F a(n+1) = A187070(2n+1) = A187068(2n+3). - _L. Edson Jeffery_, Mar 10 2011

%F a(n+3) = Sum_{k=1..n} Sum_{j=0..k} binomial(j,n-3*k+2*j)*(-1)^(j-k)*binomial(k,j)*2^(-n+3*k-j); a(0)=0, a(1)=0, a(2)=1. - _Vladimir Kruchinin_, May 05 2011

%F 7*a(n) = (c(2)-c(4))*(1+c(1))^n + (c(4)-c(1))*(1+c(2))^n + (c(1)-c(2))*(1+c(4))^n, where c(j):=2*cos(2*Pi*j/7) - for the proof see Witula et al. papers. - _Roman Witula_, Aug 07 2012

%F a(n) = -A006053(1-n) for all n in Z. - _Michael Somos_, Jun 25 2018

%e G.f. = x^2 + 2*x^3 + 5*x^4 + 11*x^5 + 25*x^6 + 56*x^7 + 126*x^8 + 283*x^9 + ... - _Michael Somos_, Jun 25 2018

%p A006054:=z**2/(1-2*z-z**2+z**3); # _Simon Plouffe_ in his 1992 dissertation

%t LinearRecurrence[{2, 1, -1}, {0, 0, 1}, 60] (* _Vladimir Joseph Stephan Orlovsky_, Feb 10 2012 *)

%o (Maxima)

%o a(n):=if n<2 then 0 else if n=2 then 1 else b(n-2);

%o b(n):=sum(sum(binomial(j,n-3*k+2*j)*(-1)^(j-k)*binomial(k,j)*2^(-n+3*k-j),j,0,k),k,1,n); \\ _Vladimir Kruchinin_, May 05 2011

%o (PARI) x='x+O('x^66);

%o concat([0, 0], Vec(x^2/(1-2*x-x^2+x^3))) \\ _Joerg Arndt_, May 05 2011

%o (Haskell)

%o a006054 n = a006053_list !! n

%o a006054_list = 0 : 0 : 1 : zipWith (+) (map (2 *) $ drop 2 a006054_list)

%o (zipWith (-) (tail a006054_list) a006054_list)

%o -- _Reinhard Zumkeller_, Oct 14 2011

%Y Cf. A005578, A006053, A006356, A007583, A080937, A094790, A214683, A214699, A214779, A215112, A306334.

%Y Row sums of A144159 and A180264.

%K nonn,easy

%O 0,4

%A _N. J. A. Sloane_