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

Author

Michael Somos, Sep 20 2014

Keywords

• nonn
• easy

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.

Examples

			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].
		

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).

Crossrefs

Cf. A103143, A123102.

Programs

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

Mathematica

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

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 */

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)