### 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:

1 | A |

1 | cat |

2 | like this |

5 | is hard to get right |

14 | Catalan numbers increase so quickly this must be all |

Posted by Bill Poser at April 15, 2006 02:37 PM