Alphabeta MathHow 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.
The five Dyck paths, balanced bracket words, binary trees and pentagon triangulations at semilength
Example
At semilength , the three Catalan families on this page match as follows.
| Dyck path | balanced brackets | binary tree | pentagon triangulation |
|---|---|---|---|
UDUDUD | ()()() | ||
UDUUDD | ()(()) | ||
UUDDUD | (())() | ||
UUDUDD | (()()) | ||
UUUDDD | ((())) |
Facts & Assumptions
Given: the five Dyck paths of semilength displayed in the table above.
Balanced bracket words are exactly the words with equal totals and nonnegative prefix balance ( is exactly the set of words of length over in which every prefix has at least as many as and the totals are equal); under , , these are exactly the step words of Dyck paths (Dyck paths of semilength ).
There is a bijection from the binary trees of size to the Dyck paths of semilength (There is a bijection for every ).
There is a bijection from the binary trees of size to the triangulations of the labelled pentagon (There is a bijection for every ).
Verification
The bracket column is obtained from the Dyck-path column by the letter substitution of [L1], so each row gives matching Dyck and bracket words.
The tree column is chosen so that the bijection of [L2] sends each listed binary tree to the Dyck path in the same row: UDUDUD corresponds to the right comb, UUUDDD to the left comb, and the three middle rows are the three mixed recursive shapes.
The triangulation column is the image of the tree column under [L3], with the two diagonals determined by the same recursive split. Thus each row records one object in each of the three Catalan families, and the rows are pairwise distinct.
Remarks
- The point of the table is not the shared count but the functions. The three bijections on the A page carry the first column to the remaining ones row by row.
Depends on
- There is a bijection $\mathcal{T}_n\to\mathcal{D}_n$ for every $n$
- $\mathcal{B}_n$ is exactly the set of words of length $2n$ over $\{\texttt{(},\texttt{)}\}$ in which every prefix has at least as many $\texttt{(}$ as $\texttt{)}$ and the totals are equal
- Dyck paths of semilength $n$
- There is a bijection $\mathcal{T}_n\to\mathcal{P}_{n+2}$ for every $n\in\mathbb{N}$
- Balanced bracket words, defined by the recursive grammar
- Binary trees, defined recursively, and their size
- Chords of a labelled convex polygon, crossing, and triangulations, defined combinatorially
Used by
Nothing in the library uses this result yet.
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)