|
| |
|
|
A186244
|
|
Number of ternary strings of length n containing 00.
|
|
11
|
|
|
|
0, 0, 1, 5, 21, 79, 281, 963, 3217, 10547, 34089, 108955, 345137, 1085331, 3392377, 10549739, 32667201, 100782787, 309946697, 950599131, 2908512145, 8880484019, 27064776729, 82350874699, 250212362465, 759269653155, 2301393567721, 6968615051195
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = 3*a(n-1) + 2*(3^(n-3) - a(n-3)). This recursive formula is based on adding any of {0,1,2} to strings of length n-1 which already have 00 in them, or {100,200} to strings of length n-3 which do not. For n = 3, we add {0,1,2} to 00, and {100,200} to the empty string to get the 5 strings of length 3 which have 00 in them. For n = 4, we add {0,1,2} to those 5, and {100,200} to all three strings of length 1, to get the 21 strings of length 4.
a(n) = -(1/3)*(1+sqrt(3))^n*sqrt(3) - (1/2)*(1+sqrt(3))^n + 3^n - (1/2)*(1-sqrt(3))^n + (1/3)*sqrt(3)*(1-sqrt(3))^n. - Alexander R. Povolotsky, Feb 18 2011
a(n) = 2*a(n-1) + 2*a(n-2) + 3^(n-2). This recursive formula is based on adding the case where the last two digits are not the same to the case where the last two digits are the same. In the first case, there are 2*a(n-1) strings, since any string of length n-1 containing 00 can be made into an appropriate string of length n by appending either of the values {0,1,2} that are not the same as the (n-1)-th digit. The case where the last two digits are the same has two subcases: to any string of length n-2 containing 00, we can append 11 or 22. There are 2*a(n-2) strings in this subcase. Or, to any string of length n-2 (whether or not it contains 00), we can append 00. There are 3^(n-2) strings in this subcase. - Todd CadwalladerOlsker, Oct 24 2020
a(n) = 5*a(n-1) - 4*a(n-2) - 6*a(n-3). - Kevin Ryde, Oct 24 2020
E.g.f.: exp(x)*(exp(2*x) - cosh(sqrt(3)*x) - 2*sinh(sqrt(3)*x)/sqrt(3)). - Stefano Spezia, Mar 02 2024
|
|
|
MATHEMATICA
|
t = {0, 0, 1}; Do[AppendTo[t, 3 t[[-1]] + 2*(3^(n - 3) - t[[-3]])], {n, 3, 40}]; t (* T. D. Noe, Nov 11 2013 *)
CoefficientList[Series[x^2/(3*x - 1)/(2*x^2 + 2*x - 1), {x, 0, 50}], x] (* G. C. Greubel, Feb 19 2017 *)
|
|
|
PROG
|
(PARI) x='x+O('x^50); Vec(x^2/(3*x - 1)/(2*x^2 + 2*x - 1)) \\ G. C. Greubel, Feb 19 2017
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
easy,nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
