cp's OEIS Frontend

A249642 Number of strings of length n over a 9-letter alphabet that begin with a nontrivial palindrome.

%I A249642 #36 Jun 15 2025 01:33:00
%S A249642 0,0,9,153,1449,13617,123129,1113273,10024569,90266553,812444409,
%T A249642 7312407993,65812080249,592312391937,5330815197129,47977369796313,
%U A249642 431796361188969,3886167547854657,34975508227845849,314779576724952633,2833016193198913689,25497145762858874817
%N A249642 Number of strings of length n over a 9-letter alphabet that begin with a nontrivial palindrome.
%C A249642 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.)
%C A249642 For example, 0082 is a string of length four over a nine-letter alphabet that begins with a nontrivial palindrome (00).
%C A249642 9 divides a(n) for all n.
%C A249642 a(n) is the number of distinct walks of n steps that begin with a palindromic sequence on the complete graph K_9 with loops. (E.g., 0, 1, 1, 0, 7, 2, 6 is a valid walk with 7 steps and begins with the palindromic sequence '0110'.)
%C A249642 lim n -> infinity a(n)/9^n ~ 0.23302304262956242 is the probability that a random, infinite base-9 string begins with a nontrivial palindrome.
%H A249642 Peter Kagey, <a href="/A249642/b249642.txt">Table of n, a(n) for n = 0..1000</a>
%F A249642 a(0) = 0; a(1) = 0; a(n+1) = 9*a(n) + 9^ceiling((n+1)/2) - a(ceiling((n+1)/2))
%F A249642 G.f. g(x) satisfies g(x) = 9*x^2*(1+9*x)/((1-9*x)*(1-9*x^2)) - (1+x)*g(x^2)/(x-9*x^2). - _Robert Israel_, Dec 30 2014
%e A249642 For n=3 the a(3) = 153 valid strings are:  000, 001, 002, 003, 004, 005, 006, 007, 008, 010, 020, 030, 040, 050, 060, 070, 080, 101, 110, 111, 112, 113, 114, 115, 116, 117, 118, 121, 131, 141, 151, 161, 171, 181, 202, 212, 220, 221, 222, 223, 224, 225, 226, 227, 228, 232, 242, 252, 262, 272, 282, 303, 313, 323, 330, 331, 332, 333, 334, 335, 336, 337, 338, 343, 353, 363, 373, 383, 404, 414, 424, 434, 440, 441, 442, 443, 444, 445, 446, 447, 448, 454, 464, 474, 484, 505, 515, 525, 535, 545, 550, 551, 552, 553, 554, 555, 556, 557, 558, 565, 575, 585, 606, 616, 626, 636, 646, 656, 660, 661, 662, 663, 664, 665, 666, 667, 668, 676, 686, 707, 717, 727, 737, 747, 757, 767, 770, 771, 772, 773, 774, 775, 776, 777, 778, 787, 808, 818, 828, 838, 848, 858, 868, 878, 880, 881, 882, 883, 884, 885, 886, 887, 888
%p A249642 A[0]:= 0: A[1]:= 0:
%p A249642 for n from 1 to 99 do
%p A249642  A[n+1]:= 9*A[n] + 9^ceil((n+1)/2) - A[ceil((n+1)/2)]
%p A249642 od:
%p A249642 seq(A[n],n=0..100); # _Robert Israel_, Dec 30 2014
%t A249642 a249642[n_] := Block[{f}, f[0] = f[1] = 0; f[x_] := 9*f[x - 1] + 9^Ceiling[x/2] - f[Ceiling[x/2]]; Table[f[i], {i, 0, n}]];
%t A249642 a249642[21] (* _Michael De Vlieger_, Dec 26 2014 *)
%o A249642 (Ruby) seq = [0, 0]; (2..N).each{ |i| seq << 9 * seq[i-1] + 9**((i+1)/2) - seq[(i+1)/2] }
%Y A249642 Analogous sequences for k-letter alphabets: A248122 (k=3), A249629 (k=4), A249638 (k=5), A249639 (k=6), A249640 (k=7), A249641 (k=8), A249643(k=10).
%K A249642 easy,nonn,walk
%O A249642 0,3
%A A249642 _Peter Kagey_, Nov 02 2014