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

Author

Peter Kagey, Nov 02 2014

Keywords

• easy
• nonn
• walk

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.

Examples

			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.
		

Links

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

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

Programs

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

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

Ruby

seq = [0, 0]; (2..N).each{ |i| seq << 4 * seq[i-1] + 4**((i+1)/2) - seq[(i+1)/2] }

Formula

a(0) = 0; a(1) = 0; a(n+1) = 4*a(n) + 4^ceiling((n+1)/2) - a(ceiling((n+1)/2)).