This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A249629 Number of strings of length n over a 4-letter alphabet that begin with a nontrivial palindrome. 9
 0, 0, 4, 28, 124, 532, 2164, 8788, 35284, 141628, 567004, 2269948, 9081724, 36334492, 145345564, 581412508, 2325680284, 9302841652, 37211487124, 148846430068, 595386201844, 2381546731732, 9526188851284, 38104763100628, 152419060098004, 609676271166388, 2438705115439924, 9754820584849588 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS A nontrivial palindrome is a palindrome of length 2 or greater. (I.e., "1" is a trivial palindrome, but "11" and "121" are nontrivial palindromes.) For example, 0032 is a is a string of length 4 over a 4-letter alphabet that begins with a nontrivial palindrome (00). 4 divides a(n) for all n. Number of walks of n steps that begin with a palindromic sequence on the complete graph K_4 with loops. (E.g., 0, 1, 1, 0, 3, 1, 2 is a valid walk with 7 steps and begins with the palindromic sequence '0110'.) lim n -> infinity a(n)/4^n ~ 0.5415013252744246 is the probability that a random, infinite base-4 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+1) = 4*a(n) + 4^ceiling((n+1)/2) - a(ceiling((n+1)/2)). EXAMPLE for n=3 the a(3) = 28 solutions are: 000, 001, 002, 003, 010, 020, 030, 101, 110, 111, 112, 113, 121, 131, 202, 212, 220, 221, 222, 223, 232, 303, 313, 323, 330, 331, 332, 333. MATHEMATICA a249629[n_] := Block[{f},   f[0] = f[1] = 0;   f[x_] := 4*f[x - 1] + 4^Ceiling[x/2] - f[Ceiling[x/2]]; Table[f[i], {i, 0, n}]]; a249629[27] (* Michael De Vlieger, Dec 27 2014 *) PROG (Ruby) seq = [0, 0]; (2..N).each{ |i| seq << 4 * seq[i-1] + 4**((i+1)/2) - seq[(i+1)/2] } (Haskell) import Data.Ratio a 0 = 0; a 1 = 0; a n = 4 * a(n - 1) + 4^ceiling(n % 2) - a(ceiling(n % 2)) -- Peter Kagey, Aug 13 2015 (MAGMA) [0] cat  [n le 1 select 0 else 4*Self(n-1) + 4^Ceiling((n)/2) - Self(Ceiling((n)/2)): n in [1..40]]; // Vincenzo Librandi, Aug 20 2015 CROSSREFS Analogous sequences for k-letter alphabets: A248122 (k=3), A249638 (k=5), A249639 (k=6), A249640 (k=7), A249641 (k=8), A249642 (k=9), A249643 (k=10). Sequence in context: A318011 A212900 A196514 * A131459 A231581 A223115 Adjacent sequences:  A249626 A249627 A249628 * A249630 A249631 A249632 KEYWORD easy,nonn,walk AUTHOR Peter Kagey, Nov 02 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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 20 09:27 EDT 2019. Contains 324234 sequences. (Running on oeis4.)