f7aa8905-7e15-475c-9311-5657bf997364
prompter
Is there a bijective mapping between the set of natural numbers and the set of all binary tree shapes? I'm pretty sure there is, but I can't find the paper I read about it
7b47fe20-b33e-424a-811e-7547e87a9e30
f7aa8905-7e15-475c-9311-5657bf997364
assistant
Yes, there exists a bijective mapping between the set of natural numbers and the set of all binary tree shapes. This mapping is known as "Cayley's formula" and was first described by Arthur Cayley in the 19th century. According to Cayley's formula, there are n^(n-2) different labeled binary trees with n vertices, and hence there is a bijection between the set of natural numbers and the set of all binary tree shapes.
301bcbef-4479-4c98-8279-6a37d064543f
7b47fe20-b33e-424a-811e-7547e87a9e30
prompter
But I asked you about binary tree shapes and not labeled trees. Do you know, what is the number of all binary tree shapes with n vertices?