CorollaryStatement: AI-adaptedProof: AI-adaptedprecheck passaudited 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.

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})$

Statement

Let $p, q \in N$ with $p \geq q$ . Write

$B^{\geq} (p, q) : = {v \in W ((0, 0), (p + q, p - q)) : h (i) \geq 0 for 0 \leq i \leq p + q}, N : = ∣ B^{\geq} (p, q) ∣,$

the diagonal paths of length $p + q$ from the origin ending at height $p - q$ whose height is never negative (Diagonal lattice paths with steps $U = (1, 1)$ and $D = (1, - 1)$ , and the height function); these record the orderings of a count with $p$ votes for the first candidate and $q$ for the second in which the first candidate is never behind. Then $B^{\geq} (p, q)$ is finite and, in $N$ ,

$(p + 1) N = (p - q + 1) (\binom{p + q}{q}) .$

Facts & Assumptions

Given: natural numbers $p \geq q$ , and the set $B^{\geq} (p, q)$ above.

[F1]

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

[L1]

For natural numbers $p^{'} > q^{'}$ , the set of diagonal paths of length $p^{'} + q^{'}$ from $(0, 0)$ ending at height $p^{'} - q^{'}$ whose height is at least $1$ at every index from $1$ to $p^{'} + q^{'}$ is finite, and its cardinality $N^{'}$ satisfies $(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 $n, k \in N$ with $k \leq n$ : $(\binom{n}{k}) \cdot k! \cdot (n - k)! = n!$ in $N$ , and $(\binom{n}{k}) = (\binom{n}{n - k})$ ( $(\binom{n}{k}) k! (n - k)! = n!$ for $k \leq n$ ; hence $(\binom{n}{k}) k! = n^{\underline{k}}$ , the quotient $n! / (k! (n - k)!)$ is a natural number, and $(\binom{n}{k}) = (\binom{n}{n - k})$ ).

[L3]

$n! \neq 0$ for every $n \in N$ , and $σ (n)! = n! \cdot σ (n)$ (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $N$ ).

[L4]

For all $m, n, k \in N$ with $k \neq 0$ : if $m \cdot k = n \cdot k$ then $m = n$ (Cancellation for multiplication by a nonzero factor).

[L5]

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).

[L6]

If $A$ is finite and $f : A \to B$ is a bijection then $B$ is finite and $∣ B ∣ = ∣ A ∣$ (The cardinality $∣ A ∣$ of a finite set).

Proof

technique · direct

1.1F1L5L6construct

Prepending an up-step is a bijection from $B^{\geq} (p, q)$ onto the set of diagonal paths of length $p + q + 1$ from $(0, 0)$ ending at height $p - q + 1$ whose height is at least $1$ from the index $1$ onwards. Given $h$ in the first set, put $\tilde{h} (0) : = 0$ and $\tilde{h} (i) : = h (i - 1) + 1$ for $1 \leq i \leq p + q + 1$ : then $\tilde{h} (1) - \tilde{h} (0) = 1$ , the later differences are those of $h$ , the values from the index $1$ on are at least $1$ because $h \geq 0$ , and $\tilde{h} (p + q + 1) = p - q + 1$ . Conversely, given $\tilde{h}$ in the second set, its first step is forced upward since $\tilde{h} (1) \geq 1$ and $\tilde{h} (1) - \tilde{h} (0) \in {1, - 1}$ , so putting $h (i) : = \tilde{h} (i + 1) - 1$ for $0 \leq i \leq p + q$ gives $h (0) = 0$ , $h \geq 0$ and $h (p + q) = p - q$ . The two constructions undo one another, so [L5] and [L6] give a bijection and equal cardinalities.

1.2L2L3L4algebra

Two identities in $N$ . First, $(p + 1) (\binom{p + q + 1}{p + 1}) = (p + q + 1) (\binom{p + q}{p})$ : with $n : = p + q + 1$ and $k : = p + 1$ one has $k \leq n$ and $n - k = q$ , so [L2] gives $(\binom{n}{p + 1}) (p + 1) p! q! = n!$ , while [L2] applied to $(\binom{p + q}{p})$ gives $(\binom{p + q}{p}) p! q! = (p + q)!$ , and multiplying the latter by $n$ and using $n \cdot (p + q)! = n!$ from [L3] makes the two left sides equal; cancelling the nonzero factor $p! q!$ by [L3] and [L4] gives the identity. Second, $(\binom{p + q}{p}) = (\binom{p + q}{q})$ by the symmetry clause of [L2], since $(p + q) - p = q$ .

2.1L1step 1.1algebra

Apply [L1] with $p^{'} = p + 1$ and $q^{'} = q$ , which is legitimate because $p + 1 > q$ follows from $p \geq q$ : the set it counts is exactly the second set of step 1.1, so its cardinality is $N$ by step 1.1, and $(p + q + 1) N = (p - q + 1) (\binom{p + q + 1}{p + 1})$ .

3.1L2L4step 1.2step 2.1algebra∎

Multiplying step 2.1 by $p + 1$ and substituting the first identity of step 1.2 gives $(p + 1) (p + q + 1) N = (p - q + 1) (p + q + 1) (\binom{p + q}{p})$ ; cancelling the nonzero factor $p + q + 1$ by [L4] and rewriting $(\binom{p + q}{p})$ as $(\binom{p + q}{q})$ by the second identity of step 1.2 gives $(p + 1) N = (p - q + 1) (\binom{p + q}{q})$ . At $q = 0$ this reads $(p + 1) N = (p + 1) (\binom{p}{0}) = p + 1$ , so $N = 1$ , the single all-up path; at $p = q$ it reads $(p + 1) N = (\binom{2 p}{p})$ , which is the relation the Catalan development uses.

Remarks

Why the extra up-step and not a reflection. The weak condition $h \geq 0$ is not of the form treated by the reflection principle, whose hypothesis is a strict inequality against a level with both endpoints strictly above it. Prepending one up-step turns the weak condition at every index into the strict condition from the index $1$ onwards, and the strict count is already proved.
The case $p = q$ . Here $p - q + 1 = 1$ , and the identity says that $p + 1$ times the number of never-behind orderings is the central binomial coefficient. That is the shape the Catalan numbers take on this page, and it is why the weak form is stated separately rather than left as an exercise on the strict one.

Depends on

Used by

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

Dependency tree · two levels

49 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

C. Krattenthaler, "Lattice Path Enumeration", ch. 10 of the Handbook of Enumerative Combinatorics, §10.3 (standard reference, not scraped)

The weak ballot count: for p≥q≥0p≥q≥0 the orderings in which the first candidate is never behind satisfy (p+1) N=(p−q+1)(p+qq)(p+1)N=(p−q+1)(qp+q​)