Riehl's basketball-walk enumeration conjecture for increasing unary-binary trees
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 , consider basketball walks of length that start at altitude , end at altitude , and never touch or pass below the -axis.
Riehl's conjecture. The number of basketball walks of length starting at the origin and ending at altitude that never touch or pass below the -axis equals the number of increasing unary-binary trees on vertices with associated permutation avoiding .
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
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 .
2016 bijective proof
Bettinelli, Fusy, Mailler, and Randazzo gave an explicit bijection: for every , 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
- arxiv.org
- arxiv.org
- ar5iv.labs.arxiv.org
- arxiv.org
- hal.science
- ocw.mit.edu
- quantamagazine.org
- scientificamerican.com
- quantamagazine.org
- quantamagazine.org
- ar5iv.labs.arxiv.org
- arxiv.org
- ar5iv.labs.arxiv.org
- mathstodon.xyz
- mathstodon.xyz
- mathstodon.xyz
- mathstodon.xyz
- mathstodon.xyz
- quantamagazine.org
- community.openai.com
- quantamagazine.org
- cdn.openai.com
- x.com
- arxiv.org
- x.com
Solutions 0
No solutions have been posted yet.