[seqfan] Re: A000984
Li-yao Xia
li-yao.xia at ens.fr
Wed May 7 17:18:33 CEST 2014
Catalan numbers count the intersection of
"Distinct strings of length 2n using n letters A and n letters B."
and
"Words on {a,b} of length 2n such that no prefix of the word contains
more b's than a's."
The latter allows unmatched brackets, a = '(', b = ')', "((((((((" is valid.
-------- Original Message --------
Subject: [seqfan] Re: A000984
From: William Keith <william.keith at gmail.com>
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
Date: 05/07/2014 05:14 PM
That comment is wrong. The number of such words is the Catalan numbers,
A000108 -- for instance, a Dyck path is formed by using a for up steps and
b for down steps. The condition that the b's never outnumber a's is then
the condition that the path never goes below the horizontal.
William
_______________________________________________
Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list