Riehl's basketball-walk enumeration conjecture for increasing unary-binary trees

About 10 years old · traced to

A basketball walk is a walk with the step set used in the paper, and an increasing unary-binary tree is an increasing tree whose vertices have at most one unary or two binary children, with its associated permutation defined as in the source. For a positive integer nn, consider basketball walks of length nn that start at altitude 00, end at altitude 11, and never touch or pass below the xx-axis.

Riehl's conjecture. The number of basketball walks of length nn starting at the origin and ending at altitude 11 that never touch or pass below the xx-axis equals the number of increasing unary-binary trees on nn vertices with associated permutation avoiding 213213.

The conjecture identifies two enumeration sequences arising from lattice paths and pattern-avoiding increasing trees. It was proved in Bettinelli and Fusy (2016), so the corresponding enumeration is no longer open.

References

Primary source

Cyril Banderier, Christian Krattenthaler, Alan Krinik, Dmitry Kruchinin, Vladimir Kruchinin, David Tuan Nguyen and Michael Wallner, “Explicit formulas for enumeration of lattice paths: basketball and the kernel method”, arXiv:1609.06473 (2017).

Progress summary

Refreshed
Claimed solved

An explicit bijection announced in 2016 proves the two counting methods agree, so the conjecture is regarded as solved.

Riehl’s conjecture asserts equality between positive basketball walks ending one level above the axis and increasing unary-binary trees whose associated permutation avoids 213213.

2016 bijective proof

Bettinelli, Fusy, Mailler, and Randazzo gave an explicit bijection: for every n≥0n \ge 0, the two classes are equinumerous. The result is presented as answering the earlier conjecture, with no reported counterexample, gap, or later challenge.

Current status (as of September 2026): The enumeration equality is claimed proved by the 2016 bijection; no unresolved mathematical case is reported, but this automated summary does not independently verify the proof.

Sources

Solutions 0

No solutions have been posted yet.