login
Number of strings of length n over a 10-letter alphabet that do not begin with a palindrome.
9

%I #17 Mar 24 2017 00:47:57

%S 0,10,90,810,8010,79290,792090,7912890,79120890,791129610,7911216810,

%T 79111376010,791112968010,7911121767210,79111209759210,

%U 791112018471210,7911120105591210,79111200264782490,791112001856695290,7911120010655736090,79111200098646144090

%N Number of strings of length n over a 10-letter alphabet that do not begin with a palindrome.

%C 10 divides a(n) for all n.

%C lim n -> infinity a(n)/10^n ~ 0.79111200088977 is the probability that a random, infinite string over a 10-letter alphabet does not begin with a palindrome.

%C This sequence gives the number of walks on K_10 with loops that do not begin with a palindromic sequence.

%H Peter Kagey, <a href="/A252703/b252703.txt">Table of n, a(n) for n = 0..1000</a>

%F a(n) = 10^n - A249643(n) for n > 0.

%e For n = 3, the first 20 of the a(3) = 810 solutions are (in lexicographic order) 011, 012, 013, 014, 015, 016, 017, 018, 019, 021, 022, 023, 024, 025, 026, 027, 028, 029, 031, 032.

%t a252703[n_] := Block[{f},

%t f[0] = f[1] = 0;

%t f[x_] := 10*f[x - 1] + 10^Ceiling[(x)/2] - f[Ceiling[(x)/2]];

%t Prepend[Rest@Table[10^i - f[i], {i, 0, n}],0]]; a252703[20] (* _Michael De Vlieger_, Dec 26 2014 *)

%o (Ruby) seq = [1, 0]; (2..N).each { |i| seq << 10 * seq[i-1] + 10**((i+1)/2) - seq[(i+1)/2] }; seq = seq.each_with_index.collect { |a, i| 10**i - a }

%Y A249643 gives the number of strings of length n over a 10-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), A252700 (k=7), A252701 (k=8), A252702 (k=9).

%K easy,nonn,walk

%O 0,2

%A _Peter Kagey_, Dec 20 2014