Session-authored (Fable 5 assisted)

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.

✓ 16 results · all verified · 9 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 7 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Lattice Paths and Catalan Numbers — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-adaptedprecheck passaudited 2026-08-26Open item page →

The ten monotone lattice paths from $(0, 0)$ to $(3, 2)$

Example

The ten monotone paths from $(0, 0)$ to $(3, 2)$ are exactly the length- $5$ words in ${E, N}$ with two $N$ steps. Grouped by the positions of the $N$ steps, they are:

positions of the $N$ steps	step word
${3, 4}$	`EEENN`
${2, 4}$	`EENEN`
${2, 3}$	`EENNE`
${1, 4}$	`ENEEN`
${1, 3}$	`ENENE`
${1, 2}$	`ENNEE`
${0, 4}$	`NEEEN`
${0, 3}$	`NEENE`
${0, 2}$	`NENEE`
${0, 1}$	`NNEEE`

Facts & Assumptions

Given: the step set ${E, N}$ .

[L1]

The number of monotone paths from $(0, 0)$ to $(m, n)$ is $(\binom{m + n}{n})$ , and the same translation formula holds for arbitrary endpoints ( $∣ M ((0, 0), (m, n)) ∣ = (\binom{m + n}{n})$ ).

Verification

technique · direct

1.1

Every word in the table has length $5$ with three $E$ steps and two $N$ steps, so each is a monotone path from $(0, 0)$ to $(3, 2)$ .

given

1.2

Every monotone path from $(0, 0)$ to $(3, 2)$ has length $5$ with exactly two $N$ steps, so its step word appears in the table at the row indexed by those two positions.

2.1

The table has ten rows, which agrees with [L1] because $(\binom{5}{2}) = 10$ .

L1step 1.1step 1.2

3.1

The boundary cases of the theorem are visible too: there is one path from $(0, 0)$ to $(3, 0)$ , namely EEE, and one path from $(0, 0)$ to $(0, 0)$ , namely the empty path.

L1∎

Remarks

The table is the concrete instance of the subset bijection used in the proof of the general counting theorem: the path is determined by the positions of its north steps.

ExampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passaudited 2026-08-26Open item page →

The five Dyck paths of semilength $3$ , with their height functions

Example

The five Dyck paths of semilength $3$ are:

step word	height sequence
`UUUDDD`	$0, 1, 2, 3, 2, 1, 0$
`UUDUDD`	$0, 1, 2, 1, 2, 1, 0$
`UUDDUD`	$0, 1, 2, 1, 0, 1, 0$
`UDUUDD`	$0, 1, 0, 1, 2, 1, 0$
`UDUDUD`	$0, 1, 0, 1, 0, 1, 0$

Facts & Assumptions

Given: the Dyck paths of semilength $3$ .

[L1]

$C_{3}$ is the number of Dyck paths of semilength $3$ (The Catalan number $C_{n} : = ∣ D_{n} ∣$ ).

[L2]

The closed formula gives $(3 + 1) C_{3} = (\binom{6}{3})$ ( $(n + 1) C_{n} = (\binom{2 n}{n})$ ).

Verification

technique · direct

1.1

Every word in the table has three up steps, three down steps, starts at height $0$ , ends at height $0$ , and never drops below height $0$ , so every row is a Dyck path of semilength $3$ .

given

2.1

Any Dyck path of semilength $3$ must begin with U; listing the five possible continuations that keep the height nonnegative gives exactly the five rows of the table and no others.

step 1.1

3.1

The table therefore has all the Dyck paths of semilength $3$ , so [L1] gives $C_{3} = 5$ . This matches [L2], since $(\binom{6}{3}) = 20$ and therefore $4 C_{3} = 20$ .

L1L2step 2.1∎

Remarks

The five words are the first nontrivial Catalan family large enough for the reflection, cycle-lemma and triangulation examples to display all members explicitly.

ExampleConstruction: AI-generatedVerification: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

The five Dyck paths, balanced bracket words, binary trees and pentagon triangulations at semilength $3$

Example

At semilength $3$ , the three Catalan families on this page match as follows.

Dyck path	balanced brackets	binary tree	pentagon triangulation
`UDUDUD`	`()()()`	${ε, 0, 1, 10, 11, 110, 111}$	${{2, 5}, {3, 5}}$
`UDUUDD`	`()(())`	${ε, 0, 1, 10, 100, 101, 11}$	${{2, 4}, {2, 5}}$
`UUDDUD`	`(())()`	${ε, 0, 00, 01, 1, 10, 11}$	${{1, 3}, {3, 5}}$
`UUDUDD`	`(()())`	${ε, 0, 00, 01, 010, 011, 1}$	${{1, 4}, {2, 4}}$
`UUUDDD`	`((()))`	${ε, 0, 00, 000, 001, 01, 1}$	${{1, 3}, {1, 4}}$

Facts & Assumptions

Given: the five Dyck paths of semilength $3$ displayed in the table above.

[L1]

Balanced bracket words are exactly the words with equal totals and nonnegative prefix balance ( $B_{n}$ is exactly the set of words of length $2 n$ over ${(,)}$ in which every prefix has at least as many $($ as $)$ and the totals are equal); under $(\mapsto U$ , $) \mapsto D$ , these are exactly the step words of Dyck paths (Dyck paths of semilength $n$ ).

[L2]

There is a bijection from the binary trees of size $3$ to the Dyck paths of semilength $3$ (There is a bijection $T_{n} \to D_{n}$ for every $n$ ).

[L3]

There is a bijection from the binary trees of size $3$ to the triangulations of the labelled pentagon (There is a bijection $T_{n} \to P_{n + 2}$ for every $n \in N$ ).

Verification

technique · direct

1.1

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.

1.2

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.

2.1

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.

L3step 1.2∎

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.

ExampleConstruction: AI-generatedVerification: AI-adaptedprecheck passaudited 2026-08-26Open item page →

The reflection bijection applied to $U D D U D U$

Example

Take the diagonal path with step word UDDUDU. Its height sequence is

$0, 1, 0, - 1, 0, - 1, 0.$

The first visit to the level $- 1$ is at index $3$ . Reflecting the initial segment through the line $y = - 1$ changes the first four heights to

$- 2, - 3, - 2, - 1,$

so the reflected path has step word DUUUDU and runs from $(0, - 2)$ to $(6, 0)$ .

Facts & Assumptions

Given: the path UDDUDU.

[L1]

If $a > c$ and $b > c$ , reflection sends a path from $(0, a)$ to $(n, b)$ that first visits level $c$ at $τ$ to the path with heights $h^{'} (i) = 2 c - h (i)$ for $i \leq τ$ and $h^{'} (i) = h (i)$ for $i \geq τ$ ; this is a bijection onto the paths from $(0, 2 c - a)$ to $(n, b)$ (Reflecting the initial segment at the first visit to level $c$ ).

[L2]

The Catalan count at semilength $3$ is $C_{3} = (\binom{6}{3}) - (\binom{6}{4}) = 5$ ( $C_{n} + (\binom{2 n}{n + 1}) = (\binom{2 n}{n})$ , The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ).

Verification

technique · direct

1.1

The path UDDUDU starts at height $0$ , ends at height $0$ , and first reaches the level $- 1$ at the index $3$ .

given

2.1

Reflecting the heights $0, 1, 0, - 1$ through the line $y = - 1$ gives $- 2, - 3, - 2, - 1$ , so the reflected step word is DUUUDU; applying the same reflection to DUUUDU returns UDDUDU.

L1step 1.1

3.1

The count behind the example agrees with [L2]: there are $(\binom{6}{3}) = 20$ diagonal paths from $(0, 0)$ to $(6, 0)$ , $(\binom{6}{4}) = 15$ of them touch the level $- 1$ , and the remaining $5$ are the Dyck paths of semilength $3$ .

L2∎

Remarks

The reflected path is not a Dyck path; that is the whole point. The bijection removes exactly the paths that touch the forbidden level.

ExampleConstruction: AI-generatedVerification: AI-adaptedprecheck passaudited 2026-08-26Open item page →

The ballot problem with three votes for $A$ and two for $B$

Example

The ten orderings of three $A$ votes and two $B$ votes are:

$A A A B B, A A B A B, A A B B A, A B A A B, A B A B A, A B B A A, B A A A B, B A A B A, B A B A A, B B A A A .$

Exactly two of them, AAABB and AABAB, keep candidate $A$ strictly ahead after every vote.

Facts & Assumptions

Given: $p = 3$ and $q = 2$ .

[L1]

The ballot theorem gives $(p + q) N = (p - q) (\binom{p + q}{p})$ (Bertrand's ballot problem: for $p > q \geq 0$ the orderings in which the first candidate is strictly ahead throughout satisfy $(p + q) N = (p - q) (\binom{p + q}{p})$ ).

[L2]

For $p \geq q \geq 0$ , if $N$ counts the orderings in which the first candidate is never behind, then $(p + 1) N = (p - q + 1) (\binom{p + q}{q})$ (The weak ballot count: for $p \geq q \geq 0$ the orderings in which the first candidate is never behind satisfy $(p + 1) N = (p - q + 1) (\binom{p + q}{q})$ ).

Verification

technique · direct

1.1

The ten words displayed above are exactly the words of length $5$ with three $A$ letters and two $B$ letters, so there are $(\binom{5}{3}) = 10$ of them.

given

2.1

Reading the lead $A - B$ after each vote shows that only AAABB and AABAB stay strictly positive at every stage, so $N = 2$ .

step 1.1

3.1

This agrees with [L1], since $(3 + 2) N = (3 - 2) (\binom{5}{3})$ reads $5 N = 10$ and therefore $N = 2$ .

L1step 2.1

4.1

For the weak form with $p = q = 2$ , the orderings AABB and ABAB are exactly the ones in which $A$ is never behind, so the weak count is $2$ ; that is $C_{2}$ and agrees with [L2].

L2∎

Remarks

The strict and weak counts differ because ties are allowed only in the second statement. At this size the difference is already visible.

ExampleConstruction: AI-generatedVerification: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

The cycle lemma on the word $(- 1, + 1, + 1, - 1, + 1, - 1, + 1)$

Example

Let

$a = (- 1, + 1, + 1, - 1, + 1, - 1, + 1),$

a word of length $7$ and weight $1$ . Its seven cyclic shifts and their partial sums are:

shift	partial sums
$(- 1, + 1, + 1, - 1, + 1, - 1, + 1)$	$- 1, 0, 1, 0, 1, 0, 1$
$(+ 1, + 1, - 1, + 1, - 1, + 1, - 1)$	$1, 2, 1, 2, 1, 2, 1$
$(+ 1, - 1, + 1, - 1, + 1, - 1, + 1)$	$1, 0, 1, 0, 1, 0, 1$
$(- 1, + 1, - 1, + 1, - 1, + 1, + 1)$	$- 1, 0, - 1, 0, - 1, 0, 1$
$(+ 1, - 1, + 1, - 1, + 1, + 1, - 1)$	$1, 0, 1, 0, 1, 2, 1$
$(- 1, + 1, - 1, + 1, + 1, - 1, + 1)$	$- 1, 0, - 1, 0, 1, 0, 1$
$(+ 1, - 1, + 1, + 1, - 1, + 1, - 1)$	$1, 0, 1, 2, 1, 2, 1$

Facts & Assumptions

Given: the two words above and the weight-two word $(+ 1, + 1, + 1, - 1)$ .

[L1]

If every letter of a length- $m$ integer word is at most $1$ and its weight is $1$ , then exactly one starting index gives a cyclic shift whose nonempty partial sums are all positive (The cycle lemma (Dvoretzky–Motzkin): if every $a_{i} \leq 1$ and $∥ a ∥ = k \geq 1$ , then exactly $k$ of the $m$ cyclic shifts of $a$ have all partial sums positive).

[L2]

The cycle-lemma Catalan count gives $(2 \cdot 3 + 1) C_{3} = (\binom{7}{3})$ ( $(2 n + 1) C_{n} = (\binom{2 n + 1}{n})$ , a second derivation of the Catalan count).

Verification

technique · direct

1.1

In the table, only the second row has all partial sums strictly positive, so the word $a$ has exactly one good shift.

given

2.1

Deleting the leading $+ 1$ from that good shift gives $(+ 1, - 1, + 1, - 1, + 1, - 1)$ , which is the Dyck word UDUDUD of semilength $3$ .

step 1.1

2.2

This agrees with [L1] and [L2]: [L1] predicts one good shift, and [L2] reads $7 C_{3} = (\binom{7}{3}) = 35$ , so $7 \cdot 5 = 35$ .

L1L2step 1.1

3.1

The weight-two word $(+ 1, + 1, + 1, - 1)$ has exactly the two good shifts $(+ 1, + 1, + 1, - 1)$ and $(+ 1, + 1, - 1, + 1)$ , so the general statement is visible too: the number of good shifts is the weight.

given∎

Remarks

The good shift is the second row because the page's convention counts strict positivity of every partial sum, not nonnegativity.

ExampleConstruction: AI-generatedVerification: AI-adaptedprecheck passaudited 2026-08-26Open item page →

The Catalan numbers through $C_{6}$ , from the recurrence and from the closed formula

Example

The Catalan numbers through $C_{6}$ are:

$n$	from the recurrence	$(\binom{2 n}{n})$	from $(n + 1) C_{n} = (\binom{2 n}{n})$
$0$	$1$	$1$	$1$
$1$	$1$	$2$	$1$
$2$	$2$	$6$	$2$
$3$	$5$	$20$	$5$
$4$	$14$	$70$	$14$
$5$	$42$	$252$	$42$
$6$	$132$	$924$	$132$

Facts & Assumptions

Given: the Catalan recurrence and the closed formula.

[L1]

$C_{n + 1} = \sum_{i = 0}^{n} C_{i} C_{n - i}$ with $C_{0} = 1$ ( $C_{n + 1} = \sum_{i = 0}^{n} C_{i} C_{n - i}$ , with $C_{0} = 1$ ).

[L2]

$(n + 1) C_{n} = (\binom{2 n}{n})$ ( $(n + 1) C_{n} = (\binom{2 n}{n})$ ).

Verification

technique · direct

1.1

Starting from $C_{0} = 1$ , the recurrence [L1] gives successively $C_{1} = 1$ , $C_{2} = 2$ , $C_{3} = 5$ , $C_{4} = 14$ , $C_{5} = 42$ and $C_{6} = 132$ .

1.2

The central binomial coefficients in the third column are $(\binom{0}{0}) = 1$ , $(\binom{2}{1}) = 2$ , $(\binom{4}{2}) = 6$ , $(\binom{6}{3}) = 20$ , $(\binom{8}{4}) = 70$ , $(\binom{10}{5}) = 252$ and $(\binom{12}{6}) = 924$ .

given

2.1

Dividing the third column by $n + 1$ as [L2] prescribes gives exactly the second column again, so the two routes agree term by term.

L2step 1.1step 1.2∎

Remarks

The table is the finite check behind the three proofs on the A page: every one of them lands on the same sequence before any general theorem is applied.

ExampleConstruction: AI-generatedVerification: AI-adaptedprecheck passaudited 2026-08-26Open item page →

All fourteen triangulations of the labelled hexagon

Example

Grouped by the split index $k$ of For $m \geq 3$ 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$ , the triangulations of the labelled hexagon are:

$k$	triangulations
$2$	${{2, 4}, {2, 5}, {2, 6}}$ , ${{2, 4}, {2, 6}, {4, 6}}$ , ${{2, 5}, {2, 6}, {3, 5}}$ , ${{2, 6}, {3, 5}, {3, 6}}$ , ${{2, 6}, {3, 6}, {4, 6}}$
$3$	${{1, 3}, {3, 5}, {3, 6}}$ , ${{1, 3}, {3, 6}, {4, 6}}$
$4$	${{1, 3}, {1, 4}, {4, 6}}$ , ${{1, 4}, {2, 4}, {4, 6}}$
$5$	${{1, 3}, {1, 4}, {1, 5}}$ , ${{1, 3}, {1, 5}, {3, 5}}$ , ${{1, 4}, {1, 5}, {2, 4}}$ , ${{1, 5}, {2, 4}, {2, 5}}$ , ${{1, 5}, {2, 5}, {3, 5}}$

Facts & Assumptions

Given: the labelled hexagon with vertices $1, \dots, 6$ .

[L1]

The split index $k$ on the closing side is unique (For $m \geq 3$ 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$ ).

[L2]

The number of triangulations of the labelled hexagon is $C_{4} = 14$ ( $∣ P_{n + 2} ∣ = C_{n}$ , The Catalan number $C_{n} : = ∣ D_{n} ∣$ ).

Verification

technique · direct

1.1

Every diagonal set in the table has three pairwise non-crossing diagonals, so each row is a triangulation of the hexagon.

given

2.1

The four groups are disjoint because the split index $k$ of [L1] is unique, and the group sizes are $5$ , $2$ , $2$ and $5$ , so the table contains $14$ triangulations altogether.

L1step 1.1

3.1

This agrees with [L2], since $C_{4} = 14$ . The same grouped count is the recursion $∣ P_{2} ∣ ∣ P_{5} ∣ + ∣ P_{3} ∣ ∣ P_{4} ∣ + ∣ P_{4} ∣ ∣ P_{3} ∣ + ∣ P_{5} ∣ ∣ P_{2} ∣ = 5 + 2 + 2 + 5$ .

L2step 2.1∎

Remarks

The two extreme groups are the fan triangulations based at the vertices $2$ and $5$ , together with the four further triangulations on the corresponding pentagons.

ExampleConstruction: AI-generatedVerification: AI-adaptedprecheck passaudited 2026-08-26Open item page →

The first coefficients of the Catalan generating function

Example

Up to degree $5$ ,

$C (x) = 1 + x + 2 x^{2} + 5 x^{3} + 14 x^{4} + 42 x^{5} + O (x^{6}),$

$1 - 2 x C (x) = 1 - 2 x - 2 x^{2} - 4 x^{3} - 10 x^{4} - 28 x^{5} + O (x^{6}) .$

Facts & Assumptions

Given: the Catalan generating function $C (x)$ .

[L1]

$C (x) = 1 + x C (x)^{2}$ ( $C (x) = 1 + x C (x)^{2}$ ).

[L2]

$(1 - 2 x C (x))^{2} = 1 - 4 x$ ( $2 x C (x) = 1 - (1 - 4 x)^{1 / 2}$ , where $(1 - 4 x)^{1 / 2}$ is the unique square root with constant coefficient $1$ ).

[L3]

$(1 - 4 x)^{1 / 2} = 1 - 2 x - 2 x^{2} - 4 x^{3} - 10 x^{4} - 28 x^{5} + O (x^{6})$ ( $[x^{k}] (1 - 4 x)^{1 / 2} = - \frac{2}{k} (\binom{2 k - 2}{k - 1})$ for $k \geq 1$ , and $1$ for $k = 0$ ).

Verification

technique · direct

1.1

Using the coefficients $1, 1, 2, 5, 14, 42$ , the Cauchy product gives $C (x)^{2} = 1 + 2 x + 5 x^{2} + 14 x^{3} + 42 x^{4} + 132 x^{5} + O (x^{6})$ , so $1 + x C (x)^{2}$ agrees with $C (x)$ through degree $5$ , as [L1] says it should.

1.2

The displayed coefficients of $1 - 2 x C (x)$ are exactly those of [L3], so the closed form predicts $1 - 2 x C (x) = (1 - 4 x)^{1 / 2}$ modulo $x^{6}$ .

2.1

Squaring $1 - 2 x - 2 x^{2} - 4 x^{3} - 10 x^{4} - 28 x^{5}$ gives $1 - 4 x$ modulo $x^{6}$ , which matches [L2].

L2step 1.2∎

Remarks

This is the finite coefficient check behind the formal closed form. The theorem on the A page proves the identity in all degrees; the example shows the first place where the numbers become recognisably Catalan.

ExampleConstruction: AI-generatedVerification: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

A two-by-two determinant counting non-intersecting path pairs

Example

At $n = 1$ , the two monotone paths from $(1, 0)$ to $(2, 1)$ are EN and NE, and the two monotone paths from $(0, 1)$ to $(1, 2)$ are again EN and NE.

Facts & Assumptions

Given: the four paths above.

[L1]

The count of non-intersecting pairs is ${(\binom{2}{1})}^{2} - (\binom{2}{2}) (\binom{2}{0})$ (For $n \geq 1$ the pairs of non-intersecting monotone paths $(1, 0) \to (n + 1, n)$ and $(0, 1) \to (n, n + 1)$ number ${(\binom{2 n}{n})}^{2} - (\binom{2 n}{n + 1}) (\binom{2 n}{n - 1})$ , The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ).

Verification

technique · direct

1.1

The four ordered pairs of paths are (EN,EN), (EN,NE), (NE,EN) and (NE,NE).

given

2.1

Exactly one of them, (NE,EN), meets at the lattice point $(1, 1)$ ; the other three are non-intersecting.

step 1.1

3.1

Therefore the direct count is $3$ , which matches [L1] because ${(\binom{2}{1})}^{2} - (\binom{2}{2}) (\binom{2}{0}) = 2^{2} - 1 \cdot 1 = 3$ .

L1step 2.1∎

Remarks

This is the smallest instance in which the determinant count differs from the product of the individual path counts.

ExampleConstruction: AI-generatedVerification: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

The tail-swap involution on a concrete intersecting pair

Example

Take the identity system with

$P_{1} : (1, 0) \to (2, 1), P_{2} : (0, 1) \to (1, 2),$

where $P_{1}$ has step word NE and $P_{2}$ has step word EN. The two paths meet at the lattice point $(1, 1)$ .

Facts & Assumptions

Given: the intersecting pair above.

[L1]

The intersecting-system involution swaps the tails at the first canonical intersection point and changes the permutation by a transposition (Tail-swapping is a sign-reversing involution on the intersecting systems).

Verification

technique · direct

1.1

The first common point of $P_{1}$ and $P_{2}$ is $(1, 1)$ , reached after the first step in each path.

given

2.1

Splitting at $(1, 1)$ , the prefixes are N and E, and the tails are E and N; swapping the tails therefore gives the new pair NN from $(1, 0)$ to $(1, 2)$ and EE from $(0, 1)$ to $(2, 1)$ .

L1step 1.1

3.1

The new pair carries the transposed endpoint assignment, and applying the same tail swap at $(1, 1)$ again returns the original pair. That is exactly the involution property of [L1] in this concrete case.

L1step 2.1∎

Remarks

The example shows why the meeting point has to be selected canonically. A different intersection choice would not necessarily be undone by a second application.

False statementConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

FALSE: the quotient $(\binom{2 n}{n}) / (n + 1)$ is an integer only for small $n$

Statement

False claim: the quotient

$\frac{(\binom{2 n}{n})}{n + 1}$

is an integer only for small values of $n$ .

Facts & Assumptions

Given: a natural number $n$ .

[L1]

$(n + 1) C_{n} = (\binom{2 n}{n})$ ( $(n + 1) C_{n} = (\binom{2 n}{n})$ ).

[L2]

$n + 1$ divides $(\binom{2 n}{n})$ for every $n$ ( $n + 1$ divides $(\binom{2 n}{n})$ for every $n \in N$ ).

Refutation

technique · direct

1.1

The first values of the quotient are $1, 1, 2, 5, 14, 42, 132$ at $n = 0, 1, 2, 3, 4, 5, 6$ respectively, so the quotient keeps producing integers beyond the first few cases.

2.1

More generally, [L1] rewrites the quotient as $C_{n}$ for every natural number $n$ , and $C_{n}$ is a natural number by definition. So the quotient is an integer for every $n$ , not merely for small ones.

L1L2∎

Remarks

The point of the refutation is that the divisibility is proved by exhibiting a count. Once the quotient is $C_{n}$ , no separate arithmetic argument is needed.

False statementConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

FALSE: the monotone paths from $(0, 0)$ to $(n, n)$ staying weakly below the diagonal are exactly half of all monotone paths

Statement

False claim: among the monotone paths from $(0, 0)$ to $(n, n)$ , exactly half stay weakly below the diagonal $y = x$ .

Facts & Assumptions

Given: the case $n = 2$ .

[L1]

Replacing $U$ by $N$ and $D$ by $E$ gives a bijection in which diagonal height is $y - x$ for the corresponding monotone path (The two step sets describe the same objects: $U \mapsto N$ , $D \mapsto E$ is a bijection matching the diagonal $y = x$ with the level $0$ ).

[L2]

The total number of monotone paths from $(0, 0)$ to $(n, n)$ is $(\binom{2 n}{n})$ ( $∣ M ((0, 0), (m, n)) ∣ = (\binom{m + n}{n})$ ).

[L3]

$(n + 1) C_{n} = (\binom{2 n}{n})$ ( $(n + 1) C_{n} = (\binom{2 n}{n})$ ).

Refutation

technique · direct

1.1

At $n = 2$ there are $(\binom{4}{2}) = 6$ monotone paths from $(0, 0)$ to $(2, 2)$ by [L2].

1.2

The weakly-below ones are exactly EENN and ENEN, so there are $2$ of them.

given

2.1

Half of the total would be $3$ , not $2$ , so the claim is false already at $n = 2$ . The general reason is that some monotone paths cross the diagonal and therefore belong to neither weak half-plane, so the naive symmetry "below equals above equals half of all paths" breaks down.

step 1.1step 1.2L1L3∎

Remarks

The true count is $C_{n}$ , not $(\binom{2 n}{n}) / 2$ . At $n = 2$ that is $C_{2} = 2$ , exactly as the two listed paths show.

False statementConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

FALSE: the Catalan numbers satisfy a constant-coefficient linear recurrence

Statement

False claim: the sequence $(C_{n})_{n \geq 0}$ of Catalan numbers satisfies a linear recurrence with constant coefficients.

Facts & Assumptions

Given: the Catalan numbers and their generating function.

[L1]

A sequence over a field satisfies an eventual constant-coefficient linear recurrence exactly when its generating function is rational (A coefficient sequence is eventually linearly recurrent if and only if its formal generating function is rational).

[L2]

The Catalan generating function is not rational ( $C (x)$ is not a rational formal power series, so $(C_{n})$ satisfies no eventual constant-coefficient linear recurrence).

[L3]

The Catalan numbers satisfy $C_{n + 1} = \sum_{i = 0}^{n} C_{i} C_{n - i}$ with $C_{0} = 1$ ( $C_{n + 1} = \sum_{i = 0}^{n} C_{i} C_{n - i}$ , with $C_{0} = 1$ ).

Refutation

technique · direct

1.1

If the false claim were true, [L1] would make the Catalan generating function rational.

L1assume-contra

2.1

That contradicts [L2].

L2step 1.1discharge-contradiction

3.1

The recurrence of [L3] does not rescue the false claim: it is a convolution recurrence, so the next term depends on products of earlier terms rather than on a fixed linear combination.

L3∎

Remarks

The tempting mistake is to see the word "recurrence" and forget to ask which kind. The Catalan sequence does have a recurrence, but not the rational-series kind.

CounterexampleConstruction: AI-generatedVerification: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

A map from hexagon triangulations to size-four binary trees that is not injective

Statement refuted

Equal Catalan counts do not make a natural-looking rule injective. Define

$f : P_{6} ⟶ T_{4}$

by sending a triangulation $T$ of the labelled hexagon to the canonical comb tree determined only by its closing-side split index $k$ :

if $k = 2$ , take the tree whose left subtree has size $0$ and right subtree has size $3$ ;
if $k = 3$ , take the tree whose subtrees have sizes $1$ and $2$ ;
if $k = 4$ , take the tree whose subtrees have sizes $2$ and $1$ ;
if $k = 5$ , take the tree whose left subtree has size $3$ and right subtree has size $0$ ;

and in every case fill each nonzero subtree by the right comb of the required size.

Facts & Assumptions

Given: the two triangulations $T_{1} = {{2, 4}, {2, 5}, {2, 6}}, T_{2} = {{2, 6}, {3, 5}, {3, 6}} .$

[L1]

Every triangulation of the hexagon has a unique closing-side split index $k$ (For $m \geq 3$ 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$ ).

[L2]

A function is injective when equal outputs force equal inputs (Injection, surjection, bijection).

Counterexample

technique · direct

1.1

Both $T_{1}$ and $T_{2}$ are triangulations of the labelled hexagon, and both have the same closing-side split index $k = 2$ : the side ${2, 6}$ is present in each, and no index smaller than $2$ is available.

L1given

2.1

By the definition of $f$ , both triangulations therefore map to the same canonical size-four comb tree, namely the tree with empty left subtree and right comb of size $3$ . So $f (T_{1}) = f (T_{2})$ .

step 1.1

3.1

The input triangulations are distinct because ${2, 4} \in T_{1}$ but ${2, 4} \notin T_{2}$ . Hence equal outputs do not force equal inputs, so [L2] shows that $f$ is not injective.

L2step 2.1∎

Remarks

The failure is deliberate: the rule remembers only the top split and then replaces the two sides by canonical combs, so it discards most of the triangulation.

CounterexampleConstruction: AI-generatedVerification: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26Open item page →

The step set ${(1, 1), (1, - 2)}$ breaks the reflection argument

Statement refuted

The reflection argument on the A page depends on the step set ${U, D}$ with height changes $\pm 1$ . It does not extend unchanged to arbitrary step sets.

Facts & Assumptions

Given: the step set $S = {(1, 1), (1, - 2)}$ and the level $0$ .

[L1]

A diagonal path with $h (0) \leq c \leq h (n)$ or $h (n) \leq c \leq h (0)$ meets the level $c$ somewhere (A diagonal path with $h (0) \leq c \leq h (n)$ or $h (n) \leq c \leq h (0)$ satisfies $h (i) = c$ for some $i$ ).

[L2]

For diagonal paths with steps $(1, 1)$ and $(1, - 1)$ whose endpoints lie above the level $c$ and which first visit $c$ at some index $τ$ , the initial segment up to $τ$ may be reflected across the line $y = c$ to obtain the bijection of Reflecting the initial segment at the first visit to level $c$ .

[L3]

For diagonal paths with steps $(1, 1)$ and $(1, - 1)$ and endpoints strictly above a level, the reflection principle identifies paths touching that level with paths from the reflected starting height, and subtracts their count from the total (The reflection principle: paths from $(0, a)$ to $(n, b)$ staying strictly above level $c$ are counted by a difference of two binomial coefficients).

Counterexample

technique · direct

1.1

The one-step path from $(0, 1)$ to $(1, - 1)$ with step $(1, - 2)$ starts above the level $0$ and ends below it, but its heights are only $1$ and $- 1$ , so it never has height $0$ . This path is outside [L1]'s diagonal-step hypothesis and shows that the conclusion of [L1] fails if that hypothesis is dropped.

L1given

2.1

Because the path of step 1.1 never visits the level $0$ , the first-visit reflection of [L2] is undefined on it. So the bijection on which the reflection count rests is absent.

L2step 1.1

3.1

The naive analogue of the count fails too. For these same steps there is no path from $(0, 1)$ to $(2, 1)$ , so the total count is $0$ and the count of paths staying strictly above $0$ is also $0$ ; but there is one path from $(0, - 1)$ to $(2, 1)$ , namely UU. Illegally extending the subtraction pattern of [L3] would therefore give $0 - 1 = - 1$ , which is not a count of paths.

L3step 2.1∎

Remarks

The broken step is exactly the one hidden in the ordinary proof: when the height jump can skip over the forbidden level, "changes side" no longer means "meets the level first."

Lattice Paths and Catalan Numbers — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

The ten monotone lattice paths from (0,0)(0,0) to (3,2)(3,2)

Example

Facts & Assumptions

Verification

Remarks

The five Dyck paths of semilength 33, with their height functions

Example

Facts & Assumptions

Verification

Remarks

The five Dyck paths, balanced bracket words, binary trees and pentagon triangulations at semilength 33

Example

Facts & Assumptions

Verification

Remarks

The reflection bijection applied to UDDUDUUDDUDU

Example

Facts & Assumptions

Verification

Remarks

The ballot problem with three votes for AA and two for BB

Example

Facts & Assumptions

Verification

Remarks

The cycle lemma on the word (−1,+1,+1,−1,+1,−1,+1)(−1,+1,+1,−1,+1,−1,+1)

Example

Facts & Assumptions

Verification

Remarks

The Catalan numbers through C6C6​, from the recurrence and from the closed formula

Example

Facts & Assumptions

Verification

Remarks

All fourteen triangulations of the labelled hexagon

Example

Facts & Assumptions

Verification

Remarks

The first coefficients of the Catalan generating function

Example

Facts & Assumptions

Verification

Remarks

A two-by-two determinant counting non-intersecting path pairs

Example

Facts & Assumptions

Verification

Remarks

The tail-swap involution on a concrete intersecting pair

Example

Facts & Assumptions

Verification

Remarks

FALSE: the quotient (2nn)/(n+1)(n2n​)/(n+1) is an integer only for small nn

Statement

Facts & Assumptions

Refutation

Remarks

FALSE: the monotone paths from (0,0)(0,0) to (n,n)(n,n) staying weakly below the diagonal are exactly half of all monotone paths

Statement

Facts & Assumptions

Refutation

Remarks

FALSE: the Catalan numbers satisfy a constant-coefficient linear recurrence

Statement

Facts & Assumptions

Refutation

Remarks

A map from hexagon triangulations to size-four binary trees that is not injective

Statement refuted

Facts & Assumptions

Counterexample

The ten monotone lattice paths from $(0, 0)$ to $(3, 2)$

The five Dyck paths of semilength $3$ , with their height functions

The five Dyck paths, balanced bracket words, binary trees and pentagon triangulations at semilength $3$

The reflection bijection applied to $U D D U D U$

The ballot problem with three votes for $A$ and two for $B$

The cycle lemma on the word $(- 1, + 1, + 1, - 1, + 1, - 1, + 1)$

The Catalan numbers through $C_{6}$ , from the recurrence and from the closed formula

FALSE: the quotient $(\binom{2 n}{n}) / (n + 1)$ is an integer only for small $n$

FALSE: the monotone paths from $(0, 0)$ to $(n, n)$ staying weakly below the diagonal are exactly half of all monotone paths

The step set ${(1, 1), (1, - 2)}$ breaks the reflection argument