Even-intersecting families of lattice paths and the Catalan numbers
Shankar proved that a family of North--East lattice paths from $(0,0)$ to $(n,n)$ in which any two paths share an even number of edges has at most $2^n$ members, and conjectured that exactly $C_n$ families attain this bound, where $C_n$ is the $n$th Catalan number. We prove the conjecture. The proof determines all equality cases of the inequality behind Shankar's bound: they correspond to noncrossing partial matchings of $\{1,\dots,m\}$ whose unmatched points lie under no arc, and there are $\binom{m}{\lfloor m/2\rfloor}$ of them.
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00474
curl -X POST /api/v1/records/hexagon/2610.00474/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00474/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'