A252698 Number of strings of length n over a 5-letter alphabet that do not begin with a palindrome.

0, 5, 20, 80, 380, 1820, 9020, 44720, 223220, 1114280, 5569580, 27838880, 139185380, 695882180, 3479366180, 17396607680, 86982815180, 434912961620, 2174563693820, 10872812899520, 54364058928020, 271820266801220, 1359101306167220, 6795506391650720

Offset

0,2

Comments

5 divides a(n) for all n.

lim n -> infinity a(n)/5^n ~ 0.570048386972902 is the probability that a random, infinite string over a 5-letter alphabet does not begin with a palindrome.

This sequence gives the number of walks on K_5 with loops that do not begin with a palindromic sequence.

Links

Peter Kagey, Table of n, a(n) for n = 0..1000

Formula

a(n) = 5^n - A249638(n) for n > 0.

Example

For n = 3, the first 10 of the a(3) = 80 solutions are (in lexicographic order) 011, 012, 013, 014, 021, 022, 023, 024, 031, 032.

Prog

(Ruby) seq = [1, 0]; (2..N).each { |i| seq << 5 * seq[i-1] + 5**((i+1)/2) - seq[(i+1)/2] }; seq = seq.each_with_index.collect { |a, i| 5**i - a }

Crossrefs

A249638 gives the number of strings of length n over a 5-letter alphabet that DO begin with a palindrome.

Analogous sequences for k-letter alphabets: A252696 (k=3), A252697 (k=4), A252699 (k=6), A252700 (k=7), A252701 (k=8), A252702 (k=9), A252703 (k=10).

Sequence in context: A003947 A369837 A363508 * A271196 A033131 A321703

Adjacent sequences: A252695 A252696 A252697 * A252699 A252700 A252701

Keyword

easy,nonn,walk

Author

Peter Kagey, Dec 20 2014

Status

approved