I have read the Wikipedia article for Catalan number and a number of other websites, but still couldn't understand it. Please explain it in simple terms, or using some examples. Thanks in advance!
Asked
Active
Viewed 1,704 times
1
-
2Which part of Wikipedia's section "Applications in combinatorics" is not clear to you? As you can see, Catalan numbers have multiple interpretations (each of these is a fine example). – dtldarek Dec 02 '12 at 14:40
-
@dtldarek actually I thought if I couldn't understand the basic concept of catalan numbers, then what is the use in reading the applications.. then after Mark suggested, I read it and finally understood it.. Thanks :) – Vishnu Vivek Dec 03 '12 at 11:52
1 Answers
4
I'd read the Wikipedia article in a different section order than it is currently written:
Applications in combinatorics
The $n$th Catalan number counts the number of different ways $n$ pairs of brackets can be correctly matched.
E.g. for $n = 3$ there are these distinct correctly matched pairs of brackets: $$((()))\space\space()(())\space\space()()()\space\space(())()\space\space(()())$$ (Etc.)
Properties
$C_0 = 1 \text{ and } C_{n+1} = \sum_{i=0}^nC_iC_{n−i} \text{ for } n\ge0$
Etc.
Mark Hurd
- 688
-
Hi Mark! you've mentioned "The nth Catalan number counts the number of different ways n pairs of brackets can be correctly matched". This line seems to make sense. Can you provide an example. – Vishnu Vivek Dec 02 '12 at 14:53
-
2That's straight from the Wikipedia article -- will copy their example... – Mark Hurd Dec 02 '12 at 14:55
-
Well, I'm currently reading that..starting to get the hang of it.. – Vishnu Vivek Dec 02 '12 at 14:59