A213290 Number of n-length words w over binary alphabet such that for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

1, 2, 4, 5, 9, 14, 27, 46, 91, 162, 323, 589, 1177, 2179, 4357, 8152, 16303, 30746, 61491, 116689, 233377, 445095, 890189, 1704795, 3409589, 6552379, 13104757, 25258601, 50517201, 97617061, 195234121, 378098956, 756197911, 1467343306, 2934686611, 5704370761

Offset: 0

Author

Alois P. Heinz, Jun 08 2012

Keywords

• nonn

Examples

			a(0) = 1: the empty word.
a(1) = 2: a, b for alphabet {a,b}.
a(2) = 4: aa, ab, ba, bb.
a(3) = 5: aaa, aab, aba, baa, bbb.
a(4) = 9: aaaa, aaab, aaba, aabb, abaa, abab, baaa, baab, bbbb.
a(5) = 14: aaaaa, aaaab, aaaba, aaabb, aabaa, aabab, aabba, abaaa, abaab, ababa, baaaa, baaab, baaba, bbbbb.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000

Crossrefs

Column k=2 of A213276.

Cf. A001405, A057427, A182172.

Programs

Maple

b:= n-> `if`(n<0, 0, binomial(n, ceil(n/2))):
a:= n-> b(n) +b(n-2) +`if`(n>0, 1, 0):
seq(a(n), n=0..40);

Formula

a(n) = A001405(n) + A001405(n-2) + A057427(n).

a(n) = A182172(n,2) + A182172(n-2,2) + A057427(n).