|
| |
|
|
A249639
|
|
Number of strings of length n over a 6 letter alphabet that begin with a nontrivial palindrome.
|
|
10
|
|
|
|
0, 0, 6, 66, 426, 2706, 16386, 99186, 595986, 3580986, 21490986, 128976186, 773887386, 4643505066, 27861211146, 167168350506, 1003011186666, 6018073616706, 36108448196946, 216650728156866, 1299904407916386, 7799426681319186, 46796560321735986
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
A nontrivial palindrome is a palindrome of length 2 or greater. (I.e., "1" is a trivial palindrome, but "11" and "121" are nontrivial palindromes.)
For example, 0052 is a string of length 4 over a six letter alphabet that begins with a nontrivial palindrome (00).
6 divides a(n) for all n.
Number of walks of n steps that begin with a palindromic sequence on the complete graph K_6 with loops. (E.g., 0, 1, 1, 0, 4, 1, 2 is a valid walk with 7 steps and begins with the palindromic sequence '0110'.)
Limit_{n->oo} a(n)/6^n ~ 0.35553832903695737 is the probability that a random, infinite base-6 string begins with a nontrivial palindrome.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(0) = 0; a(1) = 0; a(n+1) = 6*a(n) + 6^ceiling((n+1)/2) - a(ceiling((n+1)/2))
|
|
|
EXAMPLE
|
For n=3 the a(3) = 66 solutions are: 000, 001, 002, 003, 004, 005, 010, 020, 030, 040, 050, 101, 110, 111, 112, 113, 114, 115, 121, 131, 141, 151, 202, 212, 220, 221, 222, 223, 224, 225, 232, 242, 252, 303, 313, 323, 330, 331, 332, 333, 334, 335, 343, 353, 404, 414, 424, 434, 440, 441, 442, 443, 444, 445, 454, 505, 515, 525, 535, 545, 550, 551, 552, 553, 554, 555
|
|
|
MATHEMATICA
|
a249639[n_] := Block[{f},
f[0] = f[1] = 0;
f[x_] := 6*f[x - 1] + 6^Ceiling[x/2] - f[Ceiling[x/2]];
|
|
|
PROG
|
(Ruby) seq = [0, 0]; (2..N).each{ |i| seq << 6 * seq[i-1] + 6**((i+1)/2) - seq[(i+1)/2] }
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
easy,nonn,walk
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
