|
%I #17 Mar 24 2017 00:47:57
%S 0,7,42,252,1722,11802,82362,574812,4021962,28141932,196981722,
%T 1378789692,9651445482,67559543562,472916230122,3310409588892,
%U 23172863100282,162210013560042,1135470066778362,7948290270466812,55638031696285962,389466220495212042
%N Number of strings of length n over a 7-letter alphabet that do not begin with a palindrome.
%C 7 divides a(n) for all n.
%C lim n -> infinity a(n)/7^n ~ 0.697286015491013 is the probability that a random, infinite string over a 7-letter alphabet does not begin with a palindrome.
%C This sequence gives the number of walks on K_7 with loops that do not begin with a palindromic sequence.
%H Peter Kagey, <a href="/A252700/b252700.txt">Table of n, a(n) for n = 0..1000</a>
%F a(n) = 7^n - A249640(n) for n > 0.
%e For n = 3, the first 10 of the a(3) = 252 solutions are (in lexicographic order) 011, 012, 013, 014, 015, 016, 021, 022, 023, 024.
%t a252700[n_] := Block[{f}, f[0] = f[1] = 0;
%t f[x_] := 7*f[x - 1] + 7^Ceiling[(x)/2] - f[Ceiling[(x)/2]];
%t Prepend[Rest@Table[7^i - f[i], {i, 0, n}], 0]]; a252700[21] (* _Michael De Vlieger_, Dec 26 2014 *)
%o (Ruby) seq = [1, 0]; (2..N).each { |i| seq << 7 * seq[i-1] + 7**((i+1)/2) - seq[(i+1)/2] }; seq = seq.each_with_index.collect { |a, i| 7**i - a }
%Y A249640 gives the number of strings of length n over a 7-letter alphabet that DO begin with a palindrome.
%Y Analogous sequences for k-letter alphabets: A252696 (k=3), A252697 (k=4), A252698 (k=5), A252699 (k=6), A252701 (k=8), A252702 (k=9), A252703 (k=10).
%K easy,nonn,walk
%O 0,2
%A _Peter Kagey_, Dec 20 2014
|
