LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26

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.

Every Dyck path of semilength $n + 1$ factors uniquely as $U P D Q$ with $P \in D_{i}$ and $Q \in D_{n - i}$

Statement

Let $n \in N$ and put

$Z_{n} : = {(i, P, Q) : i \in N, i \leq n, P \in D_{i}, Q \in D_{n - i}} .$

The map $Θ$ sending $(i, P, Q)$ to the diagonal path of length $2 n + 2$ from $(0, 0)$ whose step word is $U$ , then the step word of $P$ , then $D$ , then the step word of $Q$ , is a bijection

$Θ : Z_{n} ⟶ D_{n + 1}$

onto the Dyck paths of semilength $n + 1$ (Dyck paths of semilength $n$ ). The index $i$ is recovered from the image as the first return: $2 i + 2$ is the least positive index at which the height of $Θ (i, P, Q)$ is $0$ .

Facts & Assumptions

Given: a natural number $n$ , and the set $Z_{n}$ above.

[F1]

$D_{m}$ is the set of diagonal paths of length $2 m$ from $(0, 0)$ to $(2 m, 0)$ whose height function satisfies $h (j) \geq 0$ for every $j \leq 2 m$ (Dyck paths of semilength $n$ ).

[F2]

A diagonal path of length $ℓ$ from $(0, α)$ is the same datum as a function $h : {0, \dots, ℓ} \to Z$ with $h (0) = α$ and $h (j) - h (j - 1) \in {1, - 1}$ for $1 \leq j \leq ℓ$ ; with $μ (j)$ the number of up-steps among the first $j$ its height is $h (j) = α + 2 μ (j) - j$ (Diagonal lattice paths with steps $U = (1, 1)$ and $D = (1, - 1)$ , and the height function).

[L1]

For a step set $S$ , a point $P^{'}$ and $ℓ \in N$ , the map sending a lattice path to its step word is a bijection $L_{S} (P^{'}; ℓ) \to S^{ℓ}$ (For each start point the step word is a bijection onto $S^{n}$ ).

[L2]

For $f : A \to B$ : $f$ is a bijection if and only if there is a function $g : B \to A$ with $g \circ f = Δ_{A}$ and $f \circ g = Δ_{B}$ ( $f : A \to B$ is a bijection if and only if there is a function $g : B \to A$ with $g \circ f = Δ_{A}$ and $f \circ g = Δ_{B}$ ; such a $g$ is unique, equals the inverse relation $f^{- 1}$ , and is itself a bijection).

[L3]

Every nonempty subset $S \subseteq N$ has a least element (The well-ordering principle).

Proof

technique · direct

1.1F1F2L1

$Θ$ lands in $D_{n + 1}$ , and for its image the first return to height $0$ is at the index $2 i + 2$ . The concatenated word has length $1 + 2 i + 1 + 2 (n - i) = 2 n + 2$ , so by [L1] it is the step word of exactly one diagonal path $v$ of length $2 n + 2$ from $(0, 0)$ . Writing $h$ , $h_{P}$ , $h_{Q}$ for the three height functions, [F2] gives $h (0) = 0$ , $h (1 + j) = 1 + h_{P} (j)$ for $0 \leq j \leq 2 i$ , and $h (2 i + 2 + j) = h (2 i + 2) + h_{Q} (j)$ for $0 \leq j \leq 2 (n - i)$ ; since $h_{P} (2 i) = 0$ we get $h (2 i + 1) = 1$ and $h (2 i + 2) = 0$ , so $h (2 i + 2 + j) = h_{Q} (j)$ . Hence $h \geq 0$ throughout and $h (2 n + 2) = h_{Q} (2 (n - i)) = 0$ , so $v \in D_{n + 1}$ by [F1]; and $h (1 + j) = 1 + h_{P} (j) \geq 1$ for $0 \leq j \leq 2 i$ , so no index in the range from $1$ to $2 i + 1$ has height $0$ and the first return is exactly at $2 i + 2$ .

1.2F1F2L1L3

$Θ$ is surjective. Let $v \in D_{n + 1}$ have height $h$ and step word $w$ . Since $h (1) \geq 0$ and $h (1) - h (0) \in {1, - 1}$ , the first step is up and $h (1) = 1$ . The set of positive indices $j \leq 2 n + 2$ with $h (j) = 0$ contains $2 n + 2$ , so by [L3] it has a least element $τ$ , and $τ \geq 2$ because $h (1) = 1$ . By [F2] the number $h (j) + j = 2 μ (j)$ is even for every $j$ , so $h (τ) = 0$ forces $τ$ even, say $τ = 2 i + 2$ with $i \in N$ and $i \leq n$ . For $1 \leq j \leq τ - 1$ we have $h (j) \neq 0$ and $h (j) \geq 0$ , hence $h (j) \geq 1$ ; in particular $h (2 i + 1) \geq 1$ , and since $h (2 i + 2) = 0$ the step at $2 i + 2$ is down and $h (2 i + 1) = 1$ . Let $P$ be the diagonal path of length $2 i$ from $(0, 0)$ with step word $w_{1} \dots w_{2 i}$ and $Q$ the one of length $2 (n - i)$ with step word $w_{2 i + 2} \dots w_{2 n + 1}$ , both supplied by [L1]. Then $h_{P} (j) = h (1 + j) - 1 \geq 0$ with $h_{P} (2 i) = h (2 i + 1) - 1 = 0$ , so $P \in D_{i}$ ; and $h_{Q} (j) = h (2 i + 2 + j) \geq 0$ with $h_{Q} (2 (n - i)) = h (2 n + 2) = 0$ , so $Q \in D_{n - i}$ . The word of $v$ is $U$ , then that of $P$ , then $D$ , then that of $Q$ , so $v = Θ (i, P, Q)$ .

2.1L1step 1.1

$Θ$ is injective. If $Θ (i, P, Q) = Θ (i^{'}, P^{'}, Q^{'})$ then by step 1.1 the common image has first return at $2 i + 2$ and at $2 i^{'} + 2$ , so $i = i^{'}$ ; the three blocks of the step word are then determined by their positions, so $P$ and $P^{'}$ have the same step word and likewise $Q$ and $Q^{'}$ , whence $P = P^{'}$ and $Q = Q^{'}$ by [L1].

3.1L2step 1.1step 2.1step 1.2∎

By steps 2.1 and 1.2 the map $Θ$ is injective and surjective, so it is a bijection, and by [L2] it has a two-sided inverse, namely the map sending $v$ to the triple built in step 1.2. At $n = 0$ the set $Z_{0}$ has the single element $(0, ε, ε)$ with both factors the empty path, and $Θ$ sends it to the path with step word $U D$ , which is the unique member of $D_{1}$ .

Remarks

Why the first return and not the last. The decomposition is forced by reading the path from the left: the first step is up, and the index at which the height first comes back to $0$ is the only place the path can be cut so that the inner block is a Dyck path after a shift and the outer remainder is one outright. Cutting at the last return also gives a decomposition, of a different shape, and the two must not be mixed.
Three later theorems on this page are this lemma applied elsewhere. The Motzkin and Schröder equations and the recursion for binary trees are the same first-return argument run over a different step set or a different recursive family, and each states the analogue rather than reusing this statement.

Depends on

Used by

Dependency tree · two levels

28 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

A. Postnikov (notes by A. Lin), MIT 18.212 Algebraic Combinatorics, Spring 2019, Proposition 5 (standard reference, not scraped)
D. Guichard, An Introduction to Combinatorics and Graph Theory, §3.5 (standard reference, not scraped)

Every Dyck path of semilength n+1n+1 factors uniquely as U P D QUPDQ with P∈DiP∈Di​ and Q∈Dn−iQ∈Dn−i​