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
Peter Kagey, Table of n, a(n) for n = 0..1000
FORMULA
a(n) = 9^n - A249642(n) for n > 0.
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
KEYWORD
easy,nonn,walk
AUTHOR
Peter Kagey, Dec 20 2014
STATUS
approved