|
%I #32 Jun 11 2019 03:12:13
%S 0,3,6,12,30,78,222,636,1878,5556,16590,49548,148422,444630,1333254,
%T 3997884,11991774,35969766,107903742,323694636,971067318,2913152406,
%U 8739407670,26218074588,78654075342,235961781396,707884899558,2123653365420,6370958763006
%N Number of strings of length n over a 3-letter alphabet that do not begin with a nontrivial palindrome.
%C A nontrivial palindrome is of length at least 2.
%C 3 divides a(n) for all n.
%C 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.
%C This sequence gives the number of walks on K_3 with loops that do not begin with a palindromic sequence.
%H Peter Kagey, <a href="/A252696/b252696.txt">Table of n, a(n) for n = 0..1000</a>
%H Daniel Gabric, Jeffrey Shallit, <a href="https://arxiv.org/abs/1906.03689">Borders, Palindrome Prefixes, and Square Prefixes</a>, arXiv:1906.03689 [cs.DM], 2019.
%F a(n) = 3^n - A248122(n) for n > 0.
%F 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
%e 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.
%t 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 *)
%o (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 }
%Y A248122 gives the number of strings of length n over a 3 letter alphabet that DO begin with a palindrome.
%Y 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).
%K easy,nonn,walk
%O 0,2
%A _Peter Kagey_, Dec 20 2014
|
