Cancellation for multiplication by a nonzero factor

Depends on

• Order on the natural numbers
• Multiplication of natural numbers
• Trichotomy of the order on $\mathbb{N}$
• Order is compatible with multiplication

Used by

• (n+1) Cₙ=C(2n, n) Corollary
• For K≤ H≤ G with G finite, [G:K]=[G:H][H:K] Corollary
• The weak ballot count: for p≥ q≥0 the orderings in which the first candidate is never behind satisfy (p+1) N=(p-q+1)C(p+q, q) Corollary
• The factorial n! and the falling factorial n^k̲, defined by recursion in ℕ Definition
• Arrangements of a word with repeated letters, counted by the multinomial coefficient Example
• Five-card hands from a 52-card deck: C(52, 5) = 2598960, and the count of hands with all cards of one suit Example
• The 15 weak compositions of 4 into 3 parts, listed and matched against stars and bars Example
• Vandermonde's identity checked at m = 4, n = 3, k = 3, both sides equal to 35 Example
• [xᵏ](1-4x)^1/2=-2/kC(2k-2, k-1) for k≥1, and 1 for k=0 Lemma
• Laws of finite sums and products in ℕ, and ι(∑_k<n aₖ) = ∑_k<n ι(aₖ) Lemma
• (2n+1) Cₙ=C(2n+1, n), a second derivation of the Catalan count Theorem
• Bertrand's ballot problem: for p>q≥0 the orderings in which the first candidate is strictly ahead throughout satisfy (p+q) N=(p-q)C(p+q, p) Theorem
• C(n, k) k! (n-k)! = n! for k ≤ n; hence C(n, k) k! = n^k̲, the quotient n!/(k!(n-k)!) is a natural number, and C(n, k) = C(n, n-k) Theorem
• ℕ × ℕ ≈ ℕ Theorem
• The Chung–Feller theorem: for each k with 0≤ k≤ n, exactly Cₙ of the diagonal paths from (0,0) to (2n,0) have exactly 2k steps lying above level 0 Theorem
• The multinomial coefficient equals n!/∏_i<m kᵢ!, and (x₀+…+xₘ₋₁)ⁿ = ∑ iotaC(n, k)∏_i<m xᵢ^kᵢ in ℝ Theorem

Dependency tree · two levels

19 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

• T. Tao, Analysis I, 3rd ed., §2.1-2.3 (Peano axioms, recursion, arithmetic) (standard reference, not scraped)
• Peano axioms (Wikipedia) (standard reference, not scraped)
• W. Aitken, MATH 378 Ch. 1: The Peano Axioms (CSU San Marcos) (standard reference, not scraped)