A Bijection Between Ordered Trees To Binary Trees That Takes The Pruning Order To The Strahler Number

By Doron Zeilberger.

Appeared in Discrete Math 82 (1990), 89-92.

Xavier G. Viennot is not only one of the greatest enumerators in the world, he is also a talented amateur wine-maker. In the historical 1985 conference in Montreal, he offered ten bottles for the bijection described in this article. The prize was awared in an ad-hoc, but impressive, `ceremony' in Viennot's country house, near Bordeaux, at a party that was held as one of the festivities in the equally historical May 2-4, 1991 FPSAC III conference. I also got a `bonus': a bottle of the excellent Alsacian beer `Schutzenberger'.

(Plain ) .tex version (4 pages)

.dvi version (for previewing)

.ps version

.pdf version

Note: The present Plain TeX version was obtained by applying my TroffToTeX translator to the original Troff source file

Added March 1, 2005: Guru Don Knuth wrote a neat implementation of my algorithm, with CWEB annotation.

Doron Zeilberger's List of Papers

Doron Zeilberger's Home Page