|
|
A252702
|
|
Number of strings of length n over a 9-letter alphabet that do not begin with a palindrome.
|
|
9
|
|
|
0, 9, 72, 576, 5112, 45432, 408312, 3669696, 33022152, 297153936, 2674339992, 24068651616, 216617456232, 1949553436392, 17545977257832, 157913762298336, 1421223827662872, 12791014151811912, 115119127069153272, 1036072140948039456, 9324649265858015112
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
9 divides a(n) for all n.
lim n -> infinity a(n)/9^n ~ 0.766976957370438 is the probability that a random, infinite string over a 9-letter alphabet does not begin with a palindrome.
This sequence gives the number of walks on K_9 with loops that do not begin with a palindromic sequence.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
For n = 3, the first 10 of the a(3) = 576 solutions are (in lexicographic order) 011, 012, 013, 014, 015, 016, 017, 018, 021, 022.
|
|
PROG
|
(Ruby) seq = [1, 0]; (2..N).each { |i| seq << 9 * seq[i-1] + 9**((i+1)/2) - seq[(i+1)/2] }; seq = seq.each_with_index.collect { |a, i| 9**i - a }
|
|
CROSSREFS
|
A249642 gives the number of strings of length n over a 9-letter alphabet that DO begin with a palindrome.
|
|
KEYWORD
|
easy,nonn,walk
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|