A247594 a(n) = a(n-1) + a(n-2) + 3*a(n-3) with a(0) = 1, a(1) = 2, a(2) = 5.

1, 2, 5, 10, 21, 46, 97, 206, 441, 938, 1997, 4258, 9069, 19318, 41161, 87686, 186801, 397970, 847829, 1806202, 3847941, 8197630, 17464177, 37205630, 79262697, 168860858, 359740445, 766389394, 1632712413, 3478323142, 7410203737, 15786664118, 33631837281

Offset

0,2

Comments

a(n) is the number of words of length n in {A,B,C} such that no two consecutive letters are B and every letter C is adjacent to exactly one letter B.

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

David Beckwith, Problem 11776, The American Mathematical Monthly, 121 (2014), 455. See solution, 123 (May, 2016), 508-510.

Roberto Tauraso, Solution of Problem 11776.

Index entries for linear recurrences with constant coefficients, signature (1,1,3).

Formula

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

0 = a(n) - a(n-1) - a(n-2) - 3*a(n-3) for all n in Z.

From Greg Dresden, Aug 05 2022: (Start)

a(n) = b(n+3) - b(n) for b(n) = A103143(n).

a(n) = c(n+2) - 2*c(n-1) for c(n) = A123102(n). (End)

Example

G.f. = 1 + 2*x + 5*x^2 + 10*x^3 + 21*x^4 + 46*x^5 + 97*x^6 + 206*x^7 + ...
a(3) = 10 with words [AAA, AAB, ABA, ABC, ACB, BAA, BAB, BCA, CBA, CBC].

Mathematica

LinearRecurrence[{1, 1, 3}, {1, 2, 5}, 40] (* Vincenzo Librandi, Aug 13 2015 *)

Prog

(PARI) {a(n) = if( n<0, polcoeff( (2*x + x^2 + x^3) / (3 + x + x^2 - x^3) + x * O(x^-n), -n), polcoeff( (1 + x + 2*x^2) / (1 - x - x^2 - 3*x^3) + x * O(x^n), n))};
(PARI) first(m)={my(v=vector(m)); v[1]=1; v[2]=2; v[3]=5; for(i=4, m, v[i]=v[i-1]+v[i-2]+3*v[i-3]); v; } /* Anders Hellström, Aug 12 2015 */
(Haskell)
a247594 n = a247594_list !! n
a247594_list = 1 : 2 : 5 : zipWith (+)
   (tail $ zipWith (+) a247594_list $ tail a247594_list)
   (map (* 3) a247594_list)
-- Reinhard Zumkeller, Sep 21 2014
(Magma) I:=[1, 2, 5]; [n le 3 select I[n] else Self(n-1)+Self(n-2)+3*Self(n-3): n in [1..40]]; // Vincenzo Librandi, Aug 13 2015

Crossrefs

Cf. A103143, A123102.

Sequence in context: A264544 A052540 A018106 * A209469 A208275 A327764

Adjacent sequences: A247591 A247592 A247593 * A247595 A247596 A247597

Keyword

nonn,easy

Author

Michael Somos, Sep 20 2014

Status

approved