Bijections and Catalan number
Bijection principal: To solve some tough counting problems it's helpful if you can show that it maps to another easier counting problem. One to one. Exhaustive. Example 1: For e.g. how many shortest paths to travel from (0,0) to (m,n) in a grid? R denotes right, U denotes up. So 'm' Rs and 'n' Us. (m+n)!/m!n! Example 2: Number of partitions of a natural number: 2 -> 2, 1+1 3 -> 3, 2 + 1, 1 + 2, 1 + 1 + 1 Solution 1: You have 'n' 1s lined up with (n-1) gaps between them: 1 _ 1 _ 1 _ 1 _ 1 You are free to put a partition on each gap or not. So 2 choices per gap. 2^(n-1) Solution 2: n can be expressed as 1 variable: X1 -> (n-1)C(0) 2 vars -> x1 + x2 = n and x1,x2 >= 1 => n-2 identical objects into 2 distinct buckets: (n-2+2-1)C(2-1) = (n-1)C(1) 3 vars -> (n-1)C(2) ... (n-1)C(n-1) Adding them and applying binomial theorem the sum is equal to : 2^(n-1) Now coming back to Bijection Principal: This last problem can be mapped to another problem....