Two short proofs of Kemp's identity for rooted plane trees (Q802559): Difference between revisions

For positive integers n,k,p let \(b_{n,k,p}:=the\) number of rooted plane trees with n nodes, height \(\leq k\), and root-degree \(=p\); \(q_{n,k,p}:=the\) number of rooted plane trees with n nodes, height \(=k\), and exactly p nodes of maximal height. The identity: \(q_{n,k,p}=b_{n+1,k,p+1}-b_{n+1,k,p}+b_{n,k,p-1}\) is originally due to \textit{R. Kemp} [Erwartungswerte charakteristischer Größen in geordneten Bäumen, Vortrag auf der Jahrestagung der DMV, Bayreuth, September, 1982], who asked for a ''combinatorial'' proof of it. Two such proofs ar given here, one of them using factorization and rearrangements of Dyck-words, the other one using the continued-fraction approach to enumeration-problems of that kind due to \textit{Ph. Flajolet} [Discrete Math. 32, 125-161 (1980; Zbl 0445.05014)].