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,2

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.

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.

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

Example

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.

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

Prog

(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 }

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

Sequence in context: A369148 A049941 A219634 * A288147 A026079 A066710

Adjacent sequences: A252693 A252694 A252695 * A252697 A252698 A252699

Keyword

easy,nonn,walk

Author

Peter Kagey, Dec 20 2014

Status

approved