The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A249639 Number of strings of length n over a 6 letter alphabet that begin with a nontrivial palindrome. 10

%I

%S 0,0,6,66,426,2706,16386,99186,595986,3580986,21490986,128976186,

%T 773887386,4643505066,27861211146,167168350506,1003011186666,

%U 6018073616706,36108448196946,216650728156866,1299904407916386,7799426681319186,46796560321735986

%N Number of strings of length n over a 6 letter alphabet that begin with a nontrivial palindrome.

%C 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.)

%C For example, 0052 is a is a string of length 4 over a six letter alphabet that begins with a nontrivial palindrome (00).

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

%C 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'.)

%C lim n -> infinity a(n)/6^n ~ 0.35553832903695737 is the probability that a random, infinite base-6 string begins with a nontrivial palindrome.

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

%F a(0) = 0; a(1) = 0; a(n+1) = 6*a(n) + 6^ceiling((n+1)/2) - a(ceiling((n+1)/2))

%e 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

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

%t f = f = 0;

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

%t Table[f[i], {i, 0, n}]]; a249639 (* _Michael De Vlieger_, Dec 27 2014 *)

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

%Y Analogous sequences for k letter alphabets: A248122 (k=3), A249629 (k=4), A249638 (k=5), A249640 (k=7), A249641 (k=8), A249642 (k=9), A249643(k=10).

%K easy,nonn,walk

%O 0,3

%A _Peter Kagey_, Nov 02 2014

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 20 15:30 EDT 2021. Contains 345165 sequences. (Running on oeis4.)