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 to the triangulations of the labelled -gon.
Facts & Assumptions
Given: a natural number .
A triangulation of the -gon has a unique split index on the closing side, and splitting there produces triangulations of the -gon and the -gon (For and a triangulation of the -gon there is a unique with such that and are both chords of or sides, and splits along ).
Every tree in is determined by an index , a left subtree in and a right subtree in (Binary trees, defined recursively, and their size).
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 the set has the single empty triangulation, so there is a unique bijection .
[ih] Assume that for every index a bijection has already been constructed.
For a tree write its recursive data as as in [F1]. Let be the triangulation of the -gon obtained by taking the triangle on the closing side with third vertex , filling the left -gon by , and filling the right -gon by the order-preserving relabelling of onto the vertices .
For a triangulation , [L1] supplies a unique split index and therefore a unique index , together with triangulations of the left -gon and the right -gon. Relabel those two sub-polygons back to and , apply the inverse bijections and from the induction hypothesis, and rebuild a tree in from the recursive data . Define that tree to be .
The constructions in steps 2.1 and 2.2 undo one another because both are governed by the same split index: the root split of the tree becomes the closing-side triangle of the triangulation, and the closing-side triangle of the triangulation becomes the root split of the tree. Hence and , so is a bijection by [L2].
Remarks
- The boundary case is the digon, not the triangle. That is why the statement is rather than , and it is why the base case carries the empty triangulation of the two-gon explicitly.
Depends on
- Chords of a labelled convex polygon, crossing, and triangulations, defined combinatorially
- For $m\ge3$ and a triangulation $T$ of the $m$-gon there is a unique $k$ with $1<k<m$ such that $\{1,k\}$ and $\{k,m\}$ are both chords of $T$ or sides, and $T$ splits along $k$
- Binary trees, defined recursively, and their size
- Each $\mathcal{T}_n$ is finite
- $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
20 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, Exercise 3.5.5 (standard reference, not scraped)
- N. Dershowitz and S. Zaks, The Cycle Lemma and Some Applications (standard reference, not scraped)