A078057 Expansion of (1+x)/(1-2*x-x^2).

1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363, 8119, 19601, 47321, 114243, 275807, 665857, 1607521, 3880899, 9369319, 22619537, 54608393, 131836323, 318281039, 768398401, 1855077841, 4478554083, 10812186007, 26102926097, 63018038201, 152139002499, 367296043199, 886731088897

Offset: 0

Author

N. J. A. Sloane, Nov 17 2002

Keywords

• nonn
• easy
• changed

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

Examples

			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
		

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.
• César Bautista-Ramos and Carlos Guillén-Galván, Fibonacci numbers of generalized Zykov sums, J. Integer Seq., 15 (2012), Article 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 University, Department of Mathematics, 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. Chemistry, 25, 1999, 55-64 (see p. 63).
• Index entries for linear recurrences with constant coefficients, signature (2,1).

Crossrefs

Essentially the same as A001333, which has many more references.

Cf. A000129, A001405, A035607, A131887, A131935, A147720, A175655.

Programs

Haskell

a078057 = sum . a035607_row  -- Reinhard Zumkeller, Jul 20 2013

Mathematica

Expand[Table[((1 + Sqrt[2])^n + (1 - Sqrt[2])^n)/2, {n, 1, 30}]] (* Artur Jasinski, Dec 10 2006 *)
CoefficientList[Series[(1 + x)/(1 - 2 x - x^2), {x, 0, 30}], x] (* Vincenzo Librandi, Jun 16 2014 *)
a[ n_] := ChebyshevT[n+1, I] / I^(n+1); (* Michael Somos, Jul 28 2018 *)

PARI

{a(n) = polchebyshev(n+1, 1, I) / I^(n+1)}; /* Michael Somos, Jul 28 2018 */

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

a(n) = A000129(n)+A000129(n+1). - R. J. Mathar, Mar 19 2025