0

I know by the formula

(2*n)!/n! * (n+1)!

the number of possible Binary Tree Combinations can be found out.

eg. for n=3, 5 combinations are possible.

I also know NCR but the standard formula of NCR is n!/r!(n-r)!.

So I want to know why formula for Combinations of Possible Binary tree is (2*n)!/n! * (n+1)!. What is the derivation behind this formula, from where it came.

sahil pahuja
  • 53
  • 5
  • 1
    What is a "Binary Tree Combination"? What is an "NCR"? – Stef Aug 06 '20 at 13:22
  • PS: is this question related to your? https://stackoverflow.com/questions/1352776/the-possible-number-of-binary-search-trees-that-can-be-created-with-n-keys-is-gi – Stef Aug 06 '20 at 13:23
  • no, its a different question. And binary tree combinations is number of combinations/structures possible for n nodes – sahil pahuja Aug 06 '20 at 13:27
  • 1
    The wikipedia page you linked does not mention "Binary Tree Combination". But your question is to calculate the number of possible Binary Tree Combinations. So, I ask again: what is a "Binary Tree Combination"? – Stef Aug 06 '20 at 13:29
  • you can check here: https://stackoverflow.com/questions/3042412/with-n-no-of-nodes-how-many-different-binary-and-binary-search-trees-possib – sahil pahuja Aug 06 '20 at 13:33
  • This is really a mathematics question, not a programming one. There are various different proofs of this result. (The search term you want is "Catalan number". The wikipedia page has several proofs: https://en.wikipedia.org/wiki/Catalan_number) – Mark Dickinson Aug 06 '20 at 14:59
  • I think this is the right stack exchange because mathamaticians may not know about data structures/binary trees – sahil pahuja Aug 06 '20 at 15:01
  • @sahilpahuja: I think you should test that hypothesis by posting on https://math.stackexchange.com. (And I think you'll find that there are plenty of mathematicians who know about Catalan numbers and binary trees.) – Mark Dickinson Aug 06 '20 at 15:02
  • 1
    I’m voting to close this question because it's about mathematics, not programming – Mark Dickinson Aug 06 '20 at 15:02

0 Answers0