A055099 Expansion of g.f.: (1 + x)/(1 - 3*x - 2*x^2).

1, 4, 14, 50, 178, 634, 2258, 8042, 28642, 102010, 363314, 1293962, 4608514, 16413466, 58457426, 208199210, 741512482, 2640935866, 9405832562, 33499369418, 119309773378, 424928058970, 1513403723666, 5390067288938, 19197009314146, 68371162520314, 243507506189234

Offset: 0

Author

Wolfdieter Lang, Apr 26 2000

Keywords

• easy
• nonn

Comments

Row sums of triangle A054458.

a(n) = term (1,1) in M^n, M = the 3 X 3 matrix [1,1,1; 1,1,1; 2,2,1]. - Gary W. Adamson, Mar 12 2009

Equals the INVERT transform of A001333: (1, 3, 7, 17, 41, 99, ...). - Gary W. Adamson, Aug 14 2010

a(n) is the number of one sided n-step walks taking steps from {(0,1), (-1,0), (1,0), (1,1)}. - Shanzhen Gao, May 13 2011

Number of quaternary words of length n on {0,1,2,3} containing no subwords 03 or 30. - Philippe Deléham, Apr 27 2012

Pisano period lengths: 1, 1, 4, 1, 24, 4, 48, 1, 12, 24, 30, 4, 12, 48, 24, 2, 272, 12, 18, 24, ... - R. J. Mathar, Aug 10 2012

a(n) = A007481(2*n+1) - A007481(2*n) = A007481(2*(n+1)) - A007481(2*n+1). - Reinhard Zumkeller, Oct 25 2015

Number of length-n words on a,b,c,d avoiding aa and ab. For n >= 1, the number of such words ending with a or the number of those ending with b is A007482(n-1), and the number of those ending with c or the number of those ending with d is a(n-1). - Jianing Song, Jun 01 2022

Examples

			a(3) = 50 because among the 4^3 = 64 quaternary words of length 3 only 14 namely 003, 030, 031, 032, 033, 103, 130, 203, 230, 300, 301, 302, 303, 330 contain the subwords 03 or 30. - _Philippe Deléham_, Apr 27 2012
		

References

• I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, (Problem 2.4.6).

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• M. Abrate, S. Barbero, U. Cerruti, and N. Murru, Construction and composition of rooted trees via descent functions, Algebra, Volume 2013 (2013), Article ID 543913, 11 pages.
• 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 17
• A. S. Fraenkel, Heap games, numeration systems and sequences, arXiv:math/9809074 [math.CO], 1998; Annals of Combinatorics, 2 (1998), 197-210.
• Shanzhen Gao and Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science.
• S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, 2010.
• Sergey Kitaev and Jeffrey Remmel, (a,b)-rectangle patterns in permutations and words, arXiv:1304.4286 [math.CO], 2013.
• Paul K. Stockmeyer, The Pascal Rhombus and the Stealth Configuration, arXiv:1504.04404 [math.CO], 2015.
• Index entries for linear recurrences with constant coefficients, signature (3,2).

Crossrefs

Column k=2 of A255256.

Cf. A001333, A002203, A007481, A007482, A054458, A104934, A202396.

Programs

Haskell

a055099 n = a007481 (2 * n + 1) - a007481 (2 * n)
-- Reinhard Zumkeller, Oct 25 2015

Magma

I:=[1,4]; [n le 2 select I[n] else 3*Self(n-1) + 2*Self(n-2): n in [1..41]]; // G. C. Greubel, Jun 27 2021

Maple

a := proc(n) option remember; `if`(n < 2, [1, 4][n+1], (3*a(n-1) + 2*a(n-2))) end:
seq(a(n), n=0..23); # Peter Luschny, Jan 06 2019

Mathematica

max = 24; cv = ContinuedFraction[ Sqrt[2], max] // Convergents // Numerator; Series[ 1/(1 - cv.x^Range[max]), {x, 0, max}] // CoefficientList[#, x]& // Rest (* Jean-François Alcover, Jun 21 2013, after Gary W. Adamson *)
LinearRecurrence[{3, 2}, {1, 4}, 24] (* Jean-François Alcover, Sep 23 2017 *)

Sage

[(i*sqrt(2))^(n-1)*( i*sqrt(2)*chebyshev_U(n, -3*i/(2*sqrt(2))) + chebyshev_U(n-1, -3*i/(2*sqrt(2))) ) for n in (0..40)] # G. C. Greubel, Jun 27 2021

Formula

a(n) = a*c^n - b*d^n, a := (5 + sqrt(17))/(2*sqrt(17)), b := (5 - sqrt(17))/(2*sqrt(17)), c := (3 + sqrt(17))/2, d := (3 - sqrt(17))/2.

a(n) = Sum_{m=0..n} A054458(n, m).

a(n) = F32(n) + F32(n-1) with F32(n) = A007482(n), n >= 1, a(0) = 1.

a(n) = A007482(n) + A007482(n-1) = 2*A007482(n) - A104934(n). - R. J. Mathar, Jul 23 2010

a(n) = 3*a(n-1) + 2*a(n-2) with a(0) = 1, a(1) = 4. - Vincenzo Librandi, Dec 08 2010

a(n) = (Sum_{k = 0..n} A202396(n,k)*3^k)/2^n. - Philippe Deléham, Feb 05 2012

a(n) = (i*sqrt(2))^(n-1)*( i*sqrt(2)*ChebyshevU(n, -3*i/(2*sqrt(2))) + ChebyshevU(n-1, -3*i/(2*sqrt(2))) ). - G. C. Greubel, Jun 27 2021

a(n) = 2*a(n-1) + 2*A007482(n-1), n >= 1. - Jianing Song, Jun 01 2022

E.g.f.: exp(3*x/2)*(17*cosh(sqrt(17)*x/2) + 5*sqrt(17)*sinh(sqrt(17)*x/2))/17. - Stefano Spezia, May 24 2024

Extensions

Edited by N. J. A. Sloane, Jun 08 2010