cp's OEIS Frontend

A252701 Number of strings of length n over an 8-letter alphabet that do not begin with a palindrome.

%I A252701 #18 Mar 24 2017 00:47:57
%S A252701 0,8,56,392,3080,24248,193592,1545656,12362168,98873096,790960520,
%T A252701 6327490568,50619730952,404956301960,3239648870024,25917178598024,
%U A252701 207337416422024,1658699232503096,13269593761151672,106156749298252856,849253993595062328,6794031942433008056
%N A252701 Number of strings of length n over an 8-letter alphabet that do not begin with a palindrome.
%C A252701 8 divides a(n) for all n.
%C A252701 lim n -> infinity a(n)/8^n ~ 0.73661041899617 is the probability that a random, infinite string over an 8-letter alphabet does not begin with a palindrome.
%C A252701 This sequence gives the number of walks on K_8 with loops that do not begin with a palindromic sequence.
%H A252701 Peter Kagey, <a href="/A252701/b252701.txt">Table of n, a(n) for n = 0..1000</a>
%F A252701 a(n) = 8^n - A249641(n) for n > 0.
%e A252701 For n = 3, the first 10 of the a(3) = 392 solutions are (in lexicographic order) 011, 012, 013, 014, 015, 016, 017, 021, 022, 023.
%t A252701 a252701[n_] := Block[{f}, f[0] = f[1] = 0;
%t A252701   f[x_] := 8*f[x - 1] + 8^Ceiling[(x)/2] - f[Ceiling[(x)/2]];
%t A252701 Prepend[Rest@Table[8^i - f[i], {i, 0, n}], 0]]; a252701[21] (* _Michael De Vlieger_, Dec 26 2014 *)
%o A252701 (Ruby) seq = [1, 0]; (2..N).each { |i| seq << 8 * seq[i-1] + 8**((i+1)/2) - seq[(i+1)/2] }; seq = seq.each_with_index.collect { |a, i| 8**i - a }
%Y A252701 A249641 gives the number of strings of length n over an 8-letter alphabet that DO begin with a palindrome.
%Y A252701 Analogous sequences for k-letter alphabets: A252696 (k=3), A252697 (k=4), A252698 (k=5), A252699 (k=6), A252700 (k=7), A252702 (k=9), A252703 (k=10).
%K A252701 easy,nonn,walk
%O A252701 0,2
%A A252701 _Peter Kagey_, Dec 20 2014