cp's OEIS Frontend

A252697 Number of strings of length n over a 4-letter alphabet that do not begin with a palindrome.

%I A252697 #15 Mar 24 2017 00:47:57
%S A252697 0,4,12,36,132,492,1932,7596,30252,120516,481572,1924356,7695492,
%T A252697 30774372,123089892,492329316,1969287012,7877027532,31507989612,
%U A252697 126031476876,504125425932,2016499779372,8065997193132,32263981077036,129055916612652,516223635676236
%N A252697 Number of strings of length n over a 4-letter alphabet that do not begin with a palindrome.
%C A252697 4 divides a(n) for all n.
%C A252697 lim n -> infinity a(n)/4^n ~ 0.458498674725575 is the probability that a random, infinite string over a 4-letter alphabet does not begin with a palindrome.
%C A252697 This sequence gives the number of walks on K_4 with loops that do not begin with a palindromic sequence.
%H A252697 Peter Kagey, <a href="/A252697/b252697.txt">Table of n, a(n) for n = 0..1000</a>
%F A252697 a(n) = 4^n - A249629(n) for n > 0.
%e A252697 For n = 3, the first 10 of the a(3) = 36 solutions are (in lexicographic order) 011, 012, 013, 021, 022, 023, 031, 032, 033, 100.
%o A252697 (Ruby) seq = [1, 0]; (2..N).each { |i| seq << 4 * seq[i-1] + 4**((i+1)/2) - seq[(i+1)/2] }; seq = seq.each_with_index.collect { |a, i| 4**i - a }
%Y A252697 A249629 gives the number of strings of length n over a 4-letter alphabet that DO begin with a palindrome.
%Y A252697 Analogous sequences for k-letter alphabets: A252696 (k=3), A252698 (k=5), A252699 (k=6), A252700 (k=7), A252701 (k=8), A252702 (k=9), A252703 (k=10).
%K A252697 easy,nonn,walk
%O A252697 0,2
%A A252697 _Peter Kagey_, Dec 20 2014