login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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. 10
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: A328685 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

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