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.
Which one?

For n  = 10 there are 2^10 subsets possible.
For e.g.
{1,9} is one such.
We map it to count of continuous missing or non-missing numbers from 1 to 10.
So this maps to {1,7,1,1} 1 present, 7 missing, 1 present, 1 missing.
Similarly
{1,5,8,10} => {1,3,1,2,1,1,1}

As you see this neatly maps to previous problem.
But that has 2^(n-1) solutions whereas this has 2^n. Why?
Because there are 2 subsets which point to the same mapping.
Take any subset, its complement will give the same mapping as well.
So {1,5,8,10} and {2,3,4,6,7,9} will both give {1,3,1,2,1,1,1}.

So divide the number of subsets by 2 to get the correct answer.

Example 3:
If there are 1000 players playing knockout matches, how many matches will there be in total?
If there are even number of players in any round, a pair will be made to play matches.
If there are odd number of players in any round, 1 player will be left alone to progress to next round and rest will play matches.

Solution:
There will be 999 matches in total.
Why?
There will be one player, the final winner, who will not lose any match.
Everyone else will lose exactly one match.
There will be 999 losers in total.
So there will be 999 matches in total.

Catalan Number applications
Ex1: If there are 5 +1s and 5 -1s to be laid out to form a string such that any prefix of that string has (num +1s) >= (num -1s), how many such ways to do that?
For e.g. {1, -1, 1, 1, -1, -1, -1, 1, -1, 1} is valid till first 6 characters but becomes invalid starting 7th character.

Ex2: Similarly for a string made up of opening and closing parentheses: (,) if we want to ensure that number of (s is >= )s.

Ex3: Similarly, while traveling on a grid if I want to go from (0,0) to (5,5) in a way that number of Right steps is >= number of Up steps.

All 3 are same problems and answer is the Catalan Number.

Let's focus on Ex3 now. How to find the number of "right" paths?
Number of right paths = Total paths - wrong paths.
Total paths = 10C5 = 10!/5!5!
Wrong paths:
Each wrong path will cross the line y = x and touch the line y = x + 1 at least once.
As soon as the wrong path (to 5,5) touches the line y = x + 1, reflect all points from there onwards against y = x + 1.
This will give you a path to (4,6) from (0,0).

For each path from (0,0) to (4,6) there is a wrong path from (0,0) to (5,5).
It is a bijection.
So wrong paths = 10C4

For (0,0) to (n,n), wrong paths = 2nC(n-1)
Correct paths = (2n)C(n) - (2n)C(n-1)

It simplifies to (2n)C(n)/(n+1) which is the nth Catalan number.