|
%I #72 Aug 24 2015 14:05:37
%S 0,0,3,15,51,165,507,1551,4683,14127,42459,127599,383019,1149693,
%T 3449715,10351023,31054947,93170397,279516747,838566831,2515717083,
%U 7547200797,22641651939,67925104239,203775461139,611326828047,1833980928771
%N Number of strings of length n over a three-letter alphabet that begin with a nontrivial palindrome.
%C A nontrivial palindrome is a palindrome of length two or greater. (I.e., "1" is a trivial palindrome, but "11" and "121" are nontrivial palindromes.)
%C For example, 0012 is a string of length four over a three-letter alphabet that begins with a nontrivial palindrome (00).
%C 3 divides a(n) for all n: 0, 0, 1, 5, 17, 55, 169, 517, 1561, 4709, 14153, ...
%C Number of walks of n steps that begin with a palindromic sequence on the complete graph K_3 with loops. (E.g., 0, 1, 1, 0, 2, 1, 2 is a valid walk with 7 steps and begins with the palindromic sequence '0110'.)
%C lim n -> infinity a(n)/3^n ~ 0.721510080117 is the probability that a random, infinite base-3 string begins with a nontrivial palindrome.
%H Peter Kagey, <a href="/A248122/b248122.txt">Table of n, a(n) for n = 0..1000</a>
%F a(0) = 0; a(1) = 0; a(n) = 3*a(n-1) + 3^ceiling(n/2) - a(ceiling(n/2)), for n >= 2.
%e For n = 3, the a(3) = 15 solutions are 000, 001, 002, 010, 020, 101, 110, 111, 112, 121, 202, 212, 220, 221, 222.
%t a248122[n_] := Block[{f},
%t f[0] = f[1] = 0;
%t f[x_] := 3*f[x - 1] + 3^Ceiling[x/2] - f[Ceiling[x/2]];
%t Table[f[i], {i, 0, n}]]; a248122[26] (* _Michael De Vlieger_, Dec 27 2014 *)
%o (Ruby) seq = [0, 0]; (2..N).each{ |i| seq << 3 * seq[i-1] + 3**((i+1)/2) - seq[(i+1)/2] }
%o (Haskell)
%o import Data.Ratio
%o a 0 = 0; a 1 = 0;
%o a n = 3 * a(n - 1) + 3^ceiling(n % 2) - a(ceiling(n % 2)) -- _Peter Kagey_, Aug 13 2015
%Y Analogous sequences for k-letter alphabets: A249629 (k=4), A249638 (k=5), A249639 (k=6), A249640 (k=7), A249641 (k=8), A249642 (k=9), A249643 (k=10).
%K easy,nonn,walk
%O 0,3
%A _Peter Kagey_, Oct 28 2014
|
