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

0, 0, 4, 28, 124, 532, 2164, 8788, 35284, 141628, 567004, 2269948, 9081724, 36334492, 145345564, 581412508, 2325680284, 9302841652, 37211487124, 148846430068, 595386201844, 2381546731732, 9526188851284, 38104763100628, 152419060098004, 609676271166388, 2438705115439924, 9754820584849588

Offset

0,3

Comments

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

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

4 divides a(n) for all n.

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

Limit_{n->oo} a(n)/4^n ~ 0.5415013252744246 is the probability that a random, infinite base-4 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+1) = 4*a(n) + 4^ceiling((n+1)/2) - a(ceiling((n+1)/2)).

Example

for n=3 the a(3) = 28 solutions are: 000, 001, 002, 003, 010, 020, 030, 101, 110, 111, 112, 113, 121, 131, 202, 212, 220, 221, 222, 223, 232, 303, 313, 323, 330, 331, 332, 333.

Mathematica

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

Prog

(Ruby) seq = [0, 0]; (2..N).each{ |i| seq << 4 * seq[i-1] + 4**((i+1)/2) - seq[(i+1)/2] }
(Haskell)
import Data.Ratio
a 0 = 0; a 1 = 0;
a n = 4 * a(n - 1) + 4^ceiling(n % 2) - a(ceiling(n % 2)) -- Peter Kagey, Aug 13 2015
(Magma) [0] cat  [n le 1 select 0 else 4*Self(n-1) + 4^Ceiling((n)/2) - Self(Ceiling((n)/2)): n in [1..40]]; // Vincenzo Librandi, Aug 20 2015

Crossrefs

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

Sequence in context: A328685 A212900 A196514 * A131459 A231581 A223115

Adjacent sequences: A249626 A249627 A249628 * A249630 A249631 A249632

Keyword

easy,nonn,walk

Author

Peter Kagey, Nov 02 2014

Status

approved