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

0, 4, 12, 36, 132, 492, 1932, 7596, 30252, 120516, 481572, 1924356, 7695492, 30774372, 123089892, 492329316, 1969287012, 7877027532, 31507989612, 126031476876, 504125425932, 2016499779372, 8065997193132, 32263981077036, 129055916612652, 516223635676236

Offset: 0

Author

Peter Kagey, Dec 20 2014

Keywords

• easy
• nonn
• walk

Comments

4 divides a(n) for all n.

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

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

Examples

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

Links

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

Crossrefs

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

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

Programs

Ruby

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

Formula

a(n) = 4^n - A249629(n) for n > 0.