login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A252696 Number of strings of length n over a 3-letter alphabet that do not begin with a nontrivial palindrome. 9
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 (list; graph; refs; listen; history; text; internal format)
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: A245774 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 22 17:42 EDT 2022. Contains 353957 sequences. (Running on oeis4.)