cp's OEIS Frontend

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

%I A249640 #24 Dec 28 2014 22:46:12
%S A249640 0,0,7,91,679,5005,35287,248731,1742839,12211675,85493527,598537051,
%T A249640 4189841719,29329466845,205306842727,1437151921051,10060067469319,
%U A249640 70420500427165,492943531132087,3450604914906331,24154234601326039,169079643588071965
%N A249640 Number of strings of length n over a 7-letter alphabet that begin with a nontrivial palindrome.
%C A249640 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 A249640 For example, 0062 is a string of length 4 over a seven letter alphabet that begins with a nontrivial palindrome (00).
%C A249640 7 divides a(n) for all n.
%C A249640 Number of walks of n steps that begin with a palindromic sequence on the complete graph K_7 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 A249640 lim n -> infinity a(n)/7^n ~ 0.30271398450898696 is the probability that a random, infinite base-7 string begins with a nontrivial palindrome.
%H A249640 Peter Kagey, <a href="/A249640/b249640.txt">Table of n, a(n) for n = 0..1000</a>
%F A249640 a(0) = 0; a(1) = 0; a(n+1) = 7*a(n) + 7^ceiling((n+1)/2) - a(ceiling((n+1)/2)).
%e A249640 For n=3 the a(3) = 91 solutions are: 000, 001, 002, 003, 004, 005, 006, 010, 020, 030, 040, 050, 060, 101, 110, 111, 112, 113, 114, 115, 116, 121, 131, 141, 151, 161, 202, 212, 220, 221, 222, 223, 224, 225, 226, 232, 242, 252, 262, 303, 313, 323, 330, 331, 332, 333, 334, 335, 336, 343, 353, 363, 404, 414, 424, 434, 440, 441, 442, 443, 444, 445, 446, 454, 464, 505, 515, 525, 535, 545, 550, 551, 552, 553, 554, 555, 556, 565, 606, 616, 626, 636, 646, 656, 660, 661, 662, 663, 664, 665, 666
%t A249640 a249640[n_] := Block[{f},
%t A249640   f[0] = f[1] = 0;
%t A249640   f[x_] := 7*f[x - 1] + 7^Ceiling[x/2] - f[Ceiling[x/2]];
%t A249640 Table[f[i], {i, 0, n}]]; a249640[21] (* _Michael De Vlieger_, Dec 27 2014 *)
%o A249640 (Ruby) seq = [0, 0]; (2..N).each{ |i| seq << 7 * seq[i-1] + 7**((i+1)/2) - seq[(i+1)/2] }
%Y A249640 Analogous sequences for k-letter alphabets: A248122 (k=3), A249629 (k=4), A249638 (k=5), A249639 (k=6), A249641 (k=8), A249642 (k=9), A249643(k=10).
%K A249640 easy,nonn,walk
%O A249640 0,3
%A A249640 _Peter Kagey_, Nov 02 2014