A249641 Number of strings of length n over an 8-letter alphabet that begin with a nontrivial palindrome.

0, 0, 8, 120, 1016, 8520, 68552, 551496, 4415048, 35344632, 282781304, 2262444024, 18099745784, 144799511928, 1158397641080, 9267193490808, 74137560288632, 593100581182152, 4744804748330312, 37958438777603016, 303667511011784648, 2429340094421767752

Offset: 0

Author

Peter Kagey, Nov 02 2014

Keywords

• easy
• nonn
• walk

Comments

A nontrivial palindrome is a palindrome of length 2 or greater. (E.g., "1" is a trivial palindrome, but "11" and "121" are nontrivial palindromes.)

For example, 0072 is a string of length 4 over an eight letter alphabet that begins with a nontrivial palindrome (00).

8 divides a(n) for all n.

a(n) is the number of distinct walks of n steps that begin with a palindromic sequence on the complete graph K_8 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'.)

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

Examples

			For n=3 the a(3) = 120 valid strings are: 000, 001, 002, 003, 004, 005, 006, 007, 010, 020, 030, 040, 050, 060, 070, 101, 110, 111, 112, 113, 114, 115, 116, 117, 121, 131, 141, 151, 161, 171, 202, 212, 220, 221, 222, 223, 224, 225, 226, 227, 232, 242, 252, 262, 272, 303, 313, 323, 330, 331, 332, 333, 334, 335, 336, 337, 343, 353, 363, 373, 404, 414, 424, 434, 440, 441, 442, 443, 444, 445, 446, 447, 454, 464, 474, 505, 515, 525, 535, 545, 550, 551, 552, 553, 554, 555, 556, 557, 565, 575, 606, 616, 626, 636, 646, 656, 660, 661, 662, 663, 664, 665, 666, 667, 676, 707, 717, 727, 737, 747, 757, 767, 770, 771, 772, 773, 774, 775, 776, 777
		

Links

• Peter Kagey, Table of n, a(n) for n = 0..1000

Crossrefs

Analogous sequences for k-letter alphabets: A248122 (k=3), A249629 (k=4), A249638 (k=5), A249639 (k=6), A249640 (k=7), A249642 (k=9), A249643(k=10).

Programs

Mathematica

a249641[n_] := Block[{f},
  f[0] = f[1] = 0;
  f[x_] := 8*f[x - 1] + 8^Ceiling[x/2] - f[Ceiling[x/2]];
Table[f[i], {i, 0, n}]]; a249641[20] (* Michael De Vlieger, Dec 27 2014 *)

Ruby

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

Formula

a(0) = 0; a(1) = 0; a(n+1) = 8*a(n) + 8^ceiling((n+1)/2) - a(ceiling((n+1)/2)).