OFFSET
0,2
COMMENTS
Let x_n be the sequence 1,3,7,17,41,99,239,... (this sequence or A001333) and let y_n = 1,2,5,12,29,70,169,... (A000129). Then {+- x_n +- y_n*sqrt(2) } are the units in the ring of algebraic integers Z[ sqrt(2) ].
Consider a string of n red, blue and green beads (with start and end points distinct and not interchangeable). If one pairing is disallowed, so that a red bead cannot immediately follow a blue bead or vice versa, how many different strings exist of any given length? Answer is a(n). E.g., a(3)=17 because there are 17 strings of length 3: RRR, RRG, RGR, RGG, RGB, GRR, GRG, GGR, GGG, GGB, GBG, GBB, BGR, BGG, BGB, BBG, BBB - Wayne VanWeerthuizen, May 02 2004
The number of Khalimsky-continuous functions with one fixed endpoint. - Shiva Samieinia (shiva(AT)math.su.se), Oct 08 2007
The sequence (-1)^C(n+1,2)*a(n) with g.f. (1-3x-x^2-x^3)/(1+6x^2+x^4) is the Hankel transform of the signed central binomial coefficients (-1)^C(n+1,2)*A001405(n). - Paul Barry, Jun 24 2008
An elephant sequence, see A175655. For the central square six A[5] vectors, with decimal values between 21 and 336, lead to this sequence. For the corner squares these vectors lead to the companion sequence A000129 (without the leading 0). - Johannes W. Meijer, Aug 15 2010
Sequence is related to rhombus substitution tilings showing 8-fold rotational symmetry (see A001333). - L. Edson Jeffery, Apr 04 2011
Number of length-n strings of 3 letters {0,1,2} with no two adjacent nonzero letters identical. The general case (strings of L letters) is the sequence with g.f. (1+x)/(1-(L-1)*x-x^2). - Joerg Arndt, Oct 11 2012
Row sums of A035607, when seen as a triangle read by rows. - Reinhard Zumkeller, Jul 20 2013
Interpretation via Cartier-Foata traces. Consider the trace monoid on Sigma = {a, b, c} in which only a and b commute. Let h(t) be the CF height (number of cliques) and |t| the length (number of letters). Then a(n) counts traces t with h(t) = n and |t| = n. In CF normal form these are exactly sequences of n singleton cliques {a},{b},{c} with the rule: whenever two consecutive cliques lie in {{a},{b}} they must be equal (so {a}{b} and {b}{a} are forbidden, while {a}{a}, {b}{b}, and any occurrence of {c} are allowed). Equivalently, no direct change a<->b without an intervening {c}. Examples: valid {a}{a}{c}{b}{b}; invalid {a}{b}{a}. This CF trace model is equivalent to Wayne VanWeerthuizen's bead model given above, where {a} = red, {b} = blue, {c} = green. In both cases, a red bead cannot immediately follow a blue bead, and a blue bead cannot immediately follow a red bead, without a green bead in between. - Constantinos Kourouzides, Aug 13 2025
REFERENCES
A. Froehlich and M. J. Taylor, Algebraic Number Theory, Cambridge, 1991 (see p. 3).
Thomas Koshy, Pell and Pell-Lucas Numbers with Applications, Springer, New York, 2014.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Jean-Luc Baril and Nathanaël Hassler, Intervals in a family of Fibonacci lattices, Univ. de Bourgogne (France, 2024). See p. 7.
Paul Barry, Pascal-like Sprugnoli arrays, arXiv:2606.22070 [math.CO], 2026. See p. 11.
César Bautista-Ramos and Carlos Guillén-Galván, Fibonacci numbers of generalized Zykov sums, J. Int. Seq. 15 (2012), Art. 12.7.8
Tanya Khovanova, Recursive Sequences
Constantinos Kourouzides, Study of an elementary trace monoid with two commuting generators, GitHub repository.
Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], 2024. See p. 5.
Emanuele Munarini, Combinatorial properties of the antichains of a garland, Integers 9 (2009), 353-374.
Shiva Samieinia, Digital straight line segments and curves, Licentiate Thesis, Stockholm Univ., Dept. of Math., Report 2007:6.
Shiva Samieinia, The number of continuous curves in digital geometry, Port. Math. 67(1) (2010), 75-89.
Gyula Tasi and Fujio Mizukami, Quantum algebraic-combinatoric study of the conformational properties of n-alkanes, J. Math. Chem. 25 (1999), 55-64 (see p. 63).
Index entries for linear recurrences with constant coefficients, signature (2,1).
FORMULA
a(n) = 2*a(n-1) + a(n-2); a(0)=1; a(1)=3. - Wayne VanWeerthuizen, May 02 2004
a(n) = 2*a(n-1) + a(n-2); lim_{n->oo} a(n+1)/a(n) = 1 + sqrt(2) (i.e., the silver ratio). - Shiva Samieinia (shiva(AT)math.su.se), Oct 08 2007
a(n) = Sum_{k=0..n} A147720(n,k)*3^k*(-1/3)^(n-k). - Philippe Deléham, Nov 15 2008
a(n) = Pell(n) + Pell(n+1) with Pell(n) = A000129(n). - Johannes W. Meijer, Aug 15 2010
G.f.: G(0)/(2*x) -1/x, where G(k) = 1 + 1/(1 - x*(2*k-1)/(x*(2*k+1) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 20 2013
a(n) = T(n+1, i) / i^(n+1), where T(n, x) denotes the Chebyshev polynomial of the first kind. - Michael Somos, Jul 28 2018
E.g.f.: exp(x)*(cosh(sqrt(2)*x) + sqrt(2)*sinh(sqrt(2)*x)). - Stefano Spezia, Jan 31 2023
EXAMPLE
G.f. = 1 + 3*x + 7*x^2 + 17*x^3 + 41*x^4 + 99*x^5 + 239*x^6 + 577*x^7 + ... - Michael Somos, Jul 28 2018
MATHEMATICA
Expand[Table[((1 + Sqrt[2])^n + (1 - Sqrt[2])^n)/2, {n, 1, 30}]] (* Artur Jasinski, Dec 10 2006 *)
(* Alternative: *)
CoefficientList[Series[(1 + x)/(1 - 2 x - x^2), {x, 0, 30}], x] (* Vincenzo Librandi, Jun 16 2014 *)
(* Alternative: *)
a[ n_] := ChebyshevT[n+1, I] / I^(n+1); (* Michael Somos, Jul 28 2018 *)
PROG
(Haskell)
a078057 = sum . a035607_row -- Reinhard Zumkeller, Jul 20 2013
(PARI) {a(n) = polchebyshev(n+1, 1, I) / I^(n+1)}; /* Michael Somos, Jul 28 2018 */
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
N. J. A. Sloane, Nov 17 2002
STATUS
approved