A252696 Number of strings of length n over a 3-letter alphabet that do not begin with a nontrivial palindrome.

0, 3, 6, 12, 30, 78, 222, 636, 1878, 5556, 16590, 49548, 148422, 444630, 1333254, 3997884, 11991774, 35969766, 107903742, 323694636, 971067318, 2913152406, 8739407670, 26218074588, 78654075342, 235961781396, 707884899558, 2123653365420, 6370958763006

Offset: 0

Author

Peter Kagey, Dec 20 2014

Keywords

• easy
• nonn
• walk

Comments

A nontrivial palindrome is of length at least 2.

3 divides a(n) for all n.

lim n -> infinity a(n)/3^n ~ 0.278489919882115 is the probability that a random, infinite string over a 3-letter alphabet does not begin with a palindrome.

This sequence gives the number of walks on K_3 with loops that do not begin with a palindromic sequence.

Examples

			For n = 3, the first 10 of the a(3) = 12 solutions are (in lexicographic order) 011, 012, 021, 022, 100, 102, 120, 122, 200, 201.
		

Links

• Peter Kagey, Table of n, a(n) for n = 0..1000
• Daniel Gabric, Jeffrey Shallit, Borders, Palindrome Prefixes, and Square Prefixes, arXiv:1906.03689 [cs.DM], 2019.

Crossrefs

A248122 gives the number of strings of length n over a 3 letter alphabet that DO begin with a palindrome.

Analogous sequences for k-letter alphabets: A252697 (k=4), A252698 (k=5), A252699 (k=6), A252700 (k=7), A252701 (k=8), A252702 (k=9), A252703 (k=10).

Programs

Mathematica

b[0] = 0; b[1] = 0; b[n_] := b[n] = 3*b[n-1] + 3^Ceiling[n/2] - b[Ceiling[n/2]]; a[n_] := 3^n - b[n]; a[0] = 0; Table[a[n], {n, 0, 28}] (* Jean-François Alcover, Jan 19 2015 *)

Ruby

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

Formula

a(n) = 3^n - A248122(n) for n > 0.

a(2n) = k*a(2n-1) - a(n) for n >= 1; a(2n+1) = k*a(2n) - a(n+1) for n >= 1. - Jeffrey Shallit, Jun 09 2019