Binomiální strom řádu $k$ (značíme $B_k$) je uspořádaný (t.j. záleží na pořadí synů) zakořeněný strom, pro který platí:
$B_0$ je tvořen pouze kořenem.
Pro $k \geq 1$ získáme $B_k$ ze stromů $B_0, B_1, . . . , B_{k−1}$ tak, že přidáme nový kořen a kořeny těchto stromů uděláme (takto popořadě) syny nového kořene.
Binomiální strom řádu $k$ (značíme $B'_k$) je uspořádaný (t.j. záleží na pořadí synů) zakořeněný strom, pro který platí:
$B'_0$ je tvořen pouze kořenem.
Pro $k \geq 1$ se $B'$ k skládá ze stromu $B'_{k−1}$, pod jehož kořenem je jako nejpravější syn napojený další strom $B'_{k−1}$.
Stromy $B_k$ a $B'_k$ jsou izomorfní.
Matematickou indukcí podle $k$.
Pro $k = 0$ tvrzení zjevně platí.
Pod kořenem stromu Bk jsou dle jeho definice zavěšeny stromy $B_0, \dots , B_{k−1}$.
Odtržením nejpravějšího podstromu $B_{k−1}$ od $B_k$ však dostáváme podle indukčního předpokladu strom $B_{k−1}$.
To dává přesně definici stromu $B′_k$.
Naopak, uvážíme-li strom $B'_k$, z indukce vyplývá, že $B'_{k−1}$ je izomorfní s $B_{k−1}$, pod jehož kořen jsou dle definice napojeny stromy $B_0, \dots , B_{k−2}$.
Pod kořen $B'_k$ jsou tudíž napojeny stromy $B_0, \dots , B_{k−1}$.
To dává přesně definici stromu $B_k$.
$\square$
Počet hladin stromu $B_k$ je roven $k + 1$, stupeň kořene je $k$, a počet vrcholů $B_k$ je roven $2^k$.
Indukcí podle $k$:
ZK: Strom $B_0$ má jistě $1$ hladinu a $2^0 = 1$ vrchol.
IK:
Z indukčního předpokladu vyplývá, že počet hladin $B_{k−1}$ je $k$ a počet vrcholů je $2^{k−1}$.
Užitím předchozího lemmatu dostáváme, že strom $B_k$ je složený ze dvou stromů $B_{k−1}$, z nichž jeden je o hladinu níže než druhý, což dává počet hladin $k + 1$ stromu $B_k$.
Složením dvou stromů $B_{k−1}$ dostáváme $2 \cdot 2^{k−1} = 2^k$ vrcholů.
Stupeň kořene $B_{k−1}$ je dle IP $k − 1$ a přidáním jednoho nového syna je stupeň $B_k$ tedy roven $k$.
$\square$
Binomiální strom s $n$ vrcholy (pokud existuje) má $1 + \log n$ hladin a počet synů kořene $\log n$.
Počet vrcholů stromu $B_k$ na $i$. hladině ($i \in {0, \dots , k}$) je $n_k(i) = \binom{k}{i}$
Indukcí podle řádu $k$.
ZK: Lemma platí triviálně pro $B_0$ a $B_1$ (a $B_2$). Nechť tedy $k \geq 2$.
IK:
Z definice $B'_k$ plyne, že vrcholy $B'_k$ na $i$. hladině, $0 < i < k$, jsou tvořeny:
vrcholy levého $B'_{k−1}$ na $i$. hladině
vrcholy pravého $B'_{k−1}$ na ($i − 1$). hladině.
Z indukčního předpokladu tedy dostaneme Pascalovým pravidlem
$\square$
Stromy $B_k$ a $B'_k$ jsou izomorfní.