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!)
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[0] = f[1] = 0;

  f[x_] := 3*f[x - 1] + 3^Ceiling[x/2] - f[Ceiling[x/2]];

Table[f[i], {i, 0, n}]]; a248122[26] (* 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.

License Agreements, Terms of Use, Privacy Policy. .

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