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
KEYWORD
nonn,easy
AUTHOR
Michael Somos, Sep 20 2014
STATUS
approved