login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A055099 Expansion of g.f.: (1 + x)/(1 - 3*x - 2*x^2). 63
1, 4, 14, 50, 178, 634, 2258, 8042, 28642, 102010, 363314, 1293962, 4608514, 16413466, 58457426, 208199210, 741512482, 2640935866, 9405832562, 33499369418, 119309773378, 424928058970, 1513403723666, 5390067288938 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
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
REFERENCES
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, (Problem 2.4.6).
LINKS
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.
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
EXAMPLE
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
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 *)
PROG
(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
(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
CROSSREFS
Column k=2 of A255256.
Sequence in context: A034459 A120747 A229314 * A335921 A153367 A211304
KEYWORD
easy,nonn
AUTHOR
Wolfdieter Lang, Apr 26 2000
EXTENSIONS
Edited by N. J. A. Sloane, Jun 08 2010
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 21 03:52 EST 2024. Contains 370219 sequences. (Running on oeis4.)