|
|
A252703
|
|
Number of strings of length n over a 10-letter alphabet that do not begin with a palindrome.
|
|
9
|
|
|
0, 10, 90, 810, 8010, 79290, 792090, 7912890, 79120890, 791129610, 7911216810, 79111376010, 791112968010, 7911121767210, 79111209759210, 791112018471210, 7911120105591210, 79111200264782490, 791112001856695290, 7911120010655736090, 79111200098646144090
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
10 divides a(n) for all n.
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.
This sequence gives the number of walks on K_10 with loops that do not begin with a palindromic sequence.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 10^n - A249643(n) for n > 0.
|
|
EXAMPLE
|
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.
|
|
MATHEMATICA
|
a252703[n_] := Block[{f},
f[0] = f[1] = 0;
f[x_] := 10*f[x - 1] + 10^Ceiling[(x)/2] - f[Ceiling[(x)/2]];
Prepend[Rest@Table[10^i - f[i], {i, 0, n}], 0]]; a252703[20] (* Michael De Vlieger, Dec 26 2014 *)
|
|
PROG
|
(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 }
|
|
CROSSREFS
|
A249643 gives the number of strings of length n over a 10-letter alphabet that DO begin with a palindrome.
|
|
KEYWORD
|
easy,nonn,walk
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|