A248122 Number of strings of length n over a three-letter alphabet that begin with a nontrivial palindrome.

0, 0, 3, 15, 51, 165, 507, 1551, 4683, 14127, 42459, 127599, 383019, 1149693, 3449715, 10351023, 31054947, 93170397, 279516747, 838566831, 2515717083, 7547200797, 22641651939, 67925104239, 203775461139, 611326828047, 1833980928771

Offset

0,3

Comments

A nontrivial palindrome is a palindrome of length two or greater. (I.e., "1" is a trivial palindrome, but "11" and "121" are nontrivial palindromes.)

For example, 0012 is a string of length four over a three-letter alphabet that begins with a nontrivial palindrome (00).

3 divides a(n) for all n: 0, 0, 1, 5, 17, 55, 169, 517, 1561, 4709, 14153, ...

Number of walks of n steps that begin with a palindromic sequence on the complete graph K_3 with loops. (E.g., 0, 1, 1, 0, 2, 1, 2 is a valid walk with 7 steps and begins with the palindromic sequence '0110'.)

lim n -> infinity a(n)/3^n ~ 0.721510080117 is the probability that a random, infinite base-3 string begins with a nontrivial palindrome.

Links

Peter Kagey, Table of n, a(n) for n = 0..1000

Formula

a(0) = 0; a(1) = 0; a(n) = 3*a(n-1) + 3^ceiling(n/2) - a(ceiling(n/2)), for n >= 2.

Example

For n = 3, the a(3) = 15 solutions are 000, 001, 002, 010, 020, 101, 110, 111, 112, 121, 202, 212, 220, 221, 222.

Mathematica

a248122[n_] := Block[{f},
  f[0] = f[1] = 0;
  f[x_] := 3*f[x - 1] + 3^Ceiling[x/2] - f[Ceiling[x/2]];
Table[f[i], {i, 0, n}]]; a248122[26] (* Michael De Vlieger, Dec 27 2014 *)

Prog

(Ruby) seq = [0, 0]; (2..N).each{ |i| seq << 3 * seq[i-1] + 3**((i+1)/2) - seq[(i+1)/2] }
(Haskell)
import Data.Ratio
a 0 = 0; a 1 = 0;
a n = 3 * a(n - 1) + 3^ceiling(n % 2) - a(ceiling(n % 2)) -- Peter Kagey, Aug 13 2015

Crossrefs

Analogous sequences for k-letter alphabets: A249629 (k=4), A249638 (k=5), A249639 (k=6), A249640 (k=7), A249641 (k=8), A249642 (k=9), A249643 (k=10).

Sequence in context: A112586 A043005 A165746 * A118126 A282464 A284663

Adjacent sequences: A248119 A248120 A248121 * A248123 A248124 A248125

Keyword

easy,nonn,walk

Author

Peter Kagey, Oct 28 2014

Status

approved