[seqfan] Re: A000984

[Li-yao Xia]

Hi,

 > (...) "Number of words on {a,b} of length 2n such that no prefix of 
the word contains more b's than a's." I'm not sure that I understand 
[that comment]. Can someone explain?

For n=2, the list of such words (of length 2n) is:

"aaaa", "aaab", "aaba", "aabb", "abaa", "abab";

and we can check that for any word, e.g., "aaba", and any of its 
prefixes (including itself), e.g., "aab", there are at least as many a's 
as b's.

That comment correctly[*] describes sequence A000984 (central binomial 
coefficients, C(2n,n)). It differs from A000108 (Catalan numbers, 
C(2n,n)/(n+1)), i.e., the number of Dyck words of length 2n, in that 
there can be more a's than b's. In fact such words are precisely 
prefixes of Dyck words.

[*] There is a proof in the following excerpt (Prop. 8.1.2, p6, using 
Lem. 8.1.1, p5), which shows a bijection between Dyck prefixes and words 
with equally many a's and b's:

http://www.lix.polytechnique.fr/~schaeffe/Biblio/PoulalhonSchaeffer-050204.pdf

(And Dyck words are their intersection.)