Product of sizes of subtrees of a perfect binary tree

77 Views Asked by At

A perfect binary tree is a binary tree for which every parent node has exactly two children and each leaf occurs at the same depth (alternatively, same height) in the tree.

A perfect binary tree of depth $k$ has $n = 2^{k+1}-1$ nodes. Is there a closed form solution expressing the product of the sizes of its perfect subtrees (each such perfect subtree is obtained as a maximal perfect subtree rooted at a node of the tree)? For instance, a perfect binary tree of size 15 has the product of subtree-sizes: $(2^4-1)(2^3-1)^2 (2^2 - 1)^4$. In general: $(2^{k+1}-1)^{2^0}(2^{k}-1)^{2^1}(2^{k-1}-1)^{2^2}(2^{k-2}-1)^{2^3} \ldots$ Is there a closed form solution for this expression? Or an asymptotic classification O(f(n))?

The online resource by Banderier discusses the sum of the sizes of the subtrees. I am looking for information on the product of these sizes, but for the case of n (maximal) perfect subtrees, each rooted at one of the n nodes of the given perfect tree.