April 15, 2006

fibs and cats

If poets have discovered the fibonacci sequence, perhaps they'll move on to other sequences. I suggest the Catalan numbers, known to mathematicians for increasing so quickly, and to computational linguists from a famous paper on syntactic ambiguity by Ken Church and Ramesh Patil in which it is shown that as the number of prepositional phrases in a sentence increases, the number of possible parse trees and their corresponding representations grows as the Catalan numbers.The sequence begins: 1, 1, 2, 5, 14, 42, 132, 429. Here is what is presumably the first cat:

1A
1cat
2like this
5is hard to get right
14Catalan numbers increase so quickly this must be all
Posted by Bill Poser at April 15, 2006 02:37 PM