[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