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,2

Links

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

Formula

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

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

Example

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.

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);

Crossrefs

Column k=2 of A213276.

Cf. A001405, A057427, A182172.

Sequence in context: A363225 A234273 A120939 * A277852 A277854 A120770

Adjacent sequences: A213287 A213288 A213289 * A213291 A213292 A213293

Keyword

nonn

Author

Alois P. Heinz, Jun 08 2012

Status

approved