Intereting Posts

Using Nakayama's Lemma to prove isomorphism theorem for finitely generated free modules
Find all polynomials $P$ such that $P(x^2+1)=P(x)^2+1$
Elementary proof of topological invariance of dimension using Brouwer's fixed point and invariance of domain theorems?
Finding an irrational not covered in standard proof that $\mu(\mathbb{Q} \cap ) = 0$
Improving my understanding of Cantor's Diagonal Argument
Prove $\frac{a}{ab+2c}+\frac{b}{bc+2a}+\frac{c}{ca+2b} \ge \frac 98$
Compute $\sum_{k=1}^{\infty}e^{-\pi k^2}\left(\pi k^2-\frac{1}{4}\right)$
Polar form of the sum of complex numbers $\operatorname{cis} 75 + \operatorname{cis} 83 + \ldots+ \operatorname{cis} 147$
$<$ in a preorder
An example of topological space in which each singleton is not in $G_\delta$
Is “imposing” one function onto another ever used in mathematics?
Product of quotient maps and quotient space that is not Hausdorff
Prove that $2^n +1$ in never a perfect cube
Prove by induction that $n^3 + 11n$ is divisible by $6$ for every positive integer $n$.
Is there an equivalence relation of which the quotient topology is homeomorphic to codomain of a quotient map?

I am struggling with a question that asks the number of trees that exist with x nodes and max level z. During my research I found that the number of binary trees with x nodes can be obtained by Catalan numbers. However, there is this element of max levels z. I don’t know how that affects the problem. Can anyone provide me any guidance as to how to solve this problem? I obviously do not want a solution. I am trying to understand what is being asked so that I can solve it.

- Finding connected components of the graph
- What is the number of full binary trees of height less than $h$
- Partition a binary tree by removing a single edge
- Evaluating 'combinatorial' sum
- Enumerate out-trees that include a set of nodes in a directed graph
- Spanning Trees of the Complete Graph Avoiding a Given Tree
- Computing Ancestors of # for Stern-Brocot Tree
- Condition on degrees for existence of a tree
- Counting $k$-ary labelled trees
- Number of rooted subtrees of given size in infinite d-regular tree

This is not a solution, or even a useful hint, but perhaps these comments will be useful to someone.

Let $t(n,h)$ be the number of binary trees of height $h$ having $n$ nodes; if I understand correctly, you’re to find some sort of usable expression for $t(n,h)$. That appears to me to be a very hard problem.

A few results are easy: $t(h+1,h)=2^h$, $t(n,h)\ne 0$ iff $h<n<2^{h+1}$, $t(2^{h+1}-1,h)=1$, and of course $\sum_h t(n,h)=C_n$, the $n$-th Catalan number. Summing in the other direction, $\sum_n t(n,h)$ is the $h$-th term of OEIS A001699, for which the OEIS entry mentions no closed form. Here’s a table of $t(n,h)$ for $1\le n\le 8$ and $0\le h\le 7$:

$$\begin{array}{l|cccccccc|c}

n\backslash h&0&1&2&3&4&5&6&7&\text{Total}\\ \hline

0&1&&&&&&&&1\\

1&1&&&&&&&&1\\

2&0&2&&&&&&&2\\

3&0&1&4&&&&&&5\\

4&0&0&6&8&&&&&14\\

5&0&0&6&20&16&&&&42\\

6&0&0&4&40&56&32&&&132\\

7&0&0&1&68&152&144&64&&429\\

8&0&0&0&94&376&480&352&128&1430

\end{array}$$

An analysis like the one that leads to the Catalan recurrence for binary trees on $n$ nodes yields a very messy recurrence for $t(n,h)$:

$$t(n+1,h+1)=2\sum_{k=h+1}^nt(k,h)\sum_{i=0}^{h-1}t(n-k,i)+\sum_{k=h+1}^{n-h-1}t(k,h)t(n-k,h)\;.\tag{1}$$

Without the factor of $2$, the double summation counts the number of ways of building a binary tree on $n+1$ vertices whose left subtree has height $h$ and whose right subtree has height less than $h$; doubling this adds the trees whose right subtrees have height $h$ and whose left subtrees have height less than $h$. The last term on the right counts the binary trees on $n+1$ vertices whose left and right subtrees both have height $h$.

$(1)$ does reduce to something reasonable in special cases. For example, it’s easily verified that

$$t(h+2,h)=2\Big(t(h,h-1)+t(h+1,h-1)\Big)$$

for $h\ge 2$.

This is messy enough, however, that I can’t help wondering whether this is the right problem. By the way, it doesn’t appear to help to replace *of height h* with *of height at most h*: that just replaces the entries in the table above with cumulative row sums, which don’t appear to be any nicer.

**Added:** $(1)$ requires that $t(0,0)=1$ and that the empty tree have height $0$. I’ve added a row to the table to reflect this.

Gerry Myerson has found OEIS A073429 and OEIS A073345, which are versions of the table above. Unfortunately, it appears that not much more is known.

- Given a helix, consider the curve of it's tangent. Express the curvature and torsion of such a curve.
- On Martingale betting system
- 9 pirates have to divide 1000 coins…
- If every ideal is principal show the same is true for the image of a homomorphism.
- Jordan region problem
- How many ways to place $n$ balls in $k$ bins with the minimum number of balls in any bin equal to $m$?
- Av = Bv for all v implies A = B?
- Continuous function on closed unit ball
- A shrinking map that is not a contraction no fixed point.
- Semigroups: Entire Elements (II)
- A problem with tensor products
- Symmetric and wedge product in algebra and differential geometry
- Geometric interpretation of a complex set
- Finding Jordan basis of a matrix ($3\times3$ example)
- Subgroup of $\mathbb{Q}$ with finite index