How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
There is a bijection for every
Statement
For every natural number there is a bijection
from the binary trees of size (Binary trees, defined recursively, and their size) to the Dyck paths of semilength (Dyck paths of semilength ).
Facts & Assumptions
Given: a natural number .
Every tree in is determined by an index , a left subtree in and a right subtree in (Binary trees, defined recursively, and their size).
Every Dyck path of semilength factors uniquely as with and for a unique index (Every Dyck path of semilength factors uniquely as with and ).
A function is a bijection exactly when it has a two-sided inverse ( is a bijection if and only if there is a function with and ; such a is unique, equals the inverse relation , and is itself a bijection).
Proof
[base] The set has the single tree and has the single empty path, so sending to the empty path is a bijection.
[ih] Assume that for every index a bijection has already been constructed.
For a tree write its recursive data as as in [F1], with and , and define to be the Dyck path whose step word is , then the step word of , then , then the step word of . This lands in by the defining condition on Dyck paths.
For a Dyck path , the first-return factorisation of [L1] writes uniquely as with and for a unique , so the induction hypothesis supplies unique trees and and therefore a unique tree with recursive data . Define .
The definitions of and undo one another: starting from a tree, the factorisation recovered from its image is the same recursive split, and starting from a Dyck path, the tree recovered from its first return rebuilds the same path. Hence and , so is a bijection by [L2].
Remarks
- The proof is a transport of the same recursion on two different families. Binary trees split at the root into left and right subtrees; Dyck paths split at their first return into an inner and an outer path. The bijection is that identification written as a two-sided inverse.
Depends on
- Binary trees, defined recursively, and their size
- Each $\mathcal{T}_n$ is finite
- Dyck paths of semilength $n$
- Every Dyck path of semilength $n+1$ factors uniquely as $U\,P\,D\,Q$ with $P\in\mathcal{D}_i$ and $Q\in\mathcal{D}_{n-i}$
- $f : A \to B$ is a bijection if and only if there is a function $g : B \to A$ with $g \circ f = \Delta_A$ and $f \circ g = \Delta_B$; such a $g$ is unique, equals the inverse relation $f^{-1}$, and is itself a bijection
Used by
Dependency tree · two levels
23 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- D. Guichard, An Introduction to Combinatorics and Graph Theory, §3.5 (standard reference, not scraped)
- N. Dershowitz and S. Zaks, The Cycle Lemma and Some Applications (standard reference, not scraped)