The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A248122 Number of strings of length n over a three-letter alphabet that begin with a nontrivial palindrome. 10
 0, 0, 3, 15, 51, 165, 507, 1551, 4683, 14127, 42459, 127599, 383019, 1149693, 3449715, 10351023, 31054947, 93170397, 279516747, 838566831, 2515717083, 7547200797, 22641651939, 67925104239, 203775461139, 611326828047, 1833980928771 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS 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.) For example, 0012 is a string of length four over a three-letter alphabet that begins with a nontrivial palindrome (00). 3 divides a(n) for all n: 0, 0, 1, 5, 17, 55, 169, 517, 1561, 4709, 14153, ... 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'.) lim n -> infinity a(n)/3^n ~ 0.721510080117 is the probability that a random, infinite base-3 string begins with a nontrivial palindrome. LINKS Peter Kagey, Table of n, a(n) for n = 0..1000 FORMULA a(0) = 0; a(1) = 0; a(n) = 3*a(n-1) + 3^ceiling(n/2) - a(ceiling(n/2)), for n >= 2. EXAMPLE For n = 3, the a(3) = 15 solutions are 000, 001, 002, 010, 020, 101, 110, 111, 112, 121, 202, 212, 220, 221, 222. MATHEMATICA a248122[n_] := Block[{f},   f = f = 0;   f[x_] := 3*f[x - 1] + 3^Ceiling[x/2] - f[Ceiling[x/2]]; Table[f[i], {i, 0, n}]]; a248122 (* Michael De Vlieger, Dec 27 2014 *) PROG (Ruby) seq = [0, 0]; (2..N).each{ |i| seq << 3 * seq[i-1] + 3**((i+1)/2) - seq[(i+1)/2] } (Haskell) import Data.Ratio a 0 = 0; a 1 = 0; a n = 3 * a(n - 1) + 3^ceiling(n % 2) - a(ceiling(n % 2)) -- Peter Kagey, Aug 13 2015 CROSSREFS 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). Sequence in context: A112586 A043005 A165746 * A118126 A282464 A284663 Adjacent sequences:  A248119 A248120 A248121 * A248123 A248124 A248125 KEYWORD easy,nonn,walk AUTHOR Peter Kagey, Oct 28 2014 STATUS approved

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

Last modified May 22 17:42 EDT 2022. Contains 353957 sequences. (Running on oeis4.)