I am looking for a solution of a problem below:
Show that, with n relations, there are (2(n − 1))!/(n − 1)! different join orders.
For this, I found a help from this slides (slide no - 19). That says
left deep n!
right deep n!
zig zag n!2^(n-2)
bushy n!C(n-1), Here C(n-1) is Catalan Number
= (2n-2)!/(n-1)!
But I could not proof the above mathematically. Please help.
If we take only bushy, that is n!C(n-1). That is equal to:
n! * ((2(n-1))!/(n! * (n-1)!)) = (2n-2)!/(n-1)!
So without considering others, it only considered bushy?