derangements_no_two_cycles_quotient_ge_factorial
For every natural number n ≥ 3, the quotient derangements_no_two_cycles_quotient n is at least (n - 3)!.
Statement
theorem derangements_no_two_cycles_quotient_ge_factorial (n : ℕ) (hn : 3 ≤ n) : (n - 3).factorial ≤ derangements_no_two_cycles_quotient n- Formalizes
- scout/2610-40342-a-p-adic-valuation-calculus-for-permutations-with-restricte.md:1633
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- derangements_no_two_cycles_quotientFor a natural number n, derangements_no_two_cycles_quotient n is the quotient of the number of derangements of Fin n without 2-cycles…
- derangements_no_two_cycles_countFor a natural number n, derangements_no_two_cycles_count n is the number of permutations of Fin n that have no cycles of length 1 and no…
Read back from the Lean
For every natural number $n$ such that $3 \le n$, $(n - 3)!$ is less than or equal to $\lfloor D_n / ((n - 1)(n - 2)) \rfloor$ (using natural number division), where $D_n$ is the number of permutations of $\{0, \dots, n-1\}$ that have no fixed points (1-cycles) and no 2-cycles.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof lower-bounds the count of derangements without 2-cycles by the number of full n-cycles in the symmetric group on n elements. Every n-cycle acts transitively on all n elements, so its only cycle has length n; since n ≥ 3, this length is neither 1 nor 2, meaning every n-cycle has neither fixed points nor 2-cycles. There are (n - 1)! such n-cycles, which factors as (n - 1)(n - 2)(n - 3)!. Dividing this lower bound by the positive divisor (n - 1)(n - 2) gives the required lower bound (n - 3)! on the quotient.
The number of permutations of Fin n consisting of a single n-cycle is (n - 1)!.
Since n ≥ 3 ≥ 2, the number of permutations of Fin n with a single cycle of length n is given by (n - 1)! * (card(Fin n) choose n). Because card(Fin n) = n and (n choose n) = 1, this simplifies directly to (n - 1)!.
uses
le_trans,Equiv.Perm.card_of_cycleType_singleton,Fintype.card_fin,Nat.choose_self,mul_onehave hn2 : 2 ≤ n := le_trans (by decide) hn have h_card := Equiv.Perm.card_of_cycleType_singleton (α := Fin n) (n := n) hn2 (by simp) simp only [Fintype.card_fin, Nat.choose_self, mul_one] at h_card
Every n-cycle on Fin n is a derangement with no 2-cycles.
Let σ be a permutation whose cycle type is the singleton {n}. Having a single cycle means σ is a cycle whose support has cardinality n, which equals the total number of elements in Fin n, so the support is the entire universe. Thus, every element x is moved by σ and belongs to the same cycle as any other element y. Therefore, the cycle of x consists of all n elements of Fin n. Since n ≥ 3, the cycle length n is neither 1 nor 2, which proves that σ has no fixed points and no 2-cycles.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Equiv.Perm.card_cycleType_eq_one,Equiv.Perm.sum_cycleType,Finset.eq_univ_of_card,Fintype.card_fin,Equiv.Perm.mem_support,Finset.card_univ,Finset.coe_insert,Finset.coe_singleton,Set.mem_insert_iff,Set.mem_singleton_iffhave h_sub : ({g : Equiv.Perm (Fin n) | g.cycleType = {n}} : Finset (Equiv.Perm (Fin n))) ⊆ ({σ : Equiv.Perm (Fin n) | ∀ (x : Fin n), ({y : Fin n | σ.SameCycle x y} : Finset (Fin n)).card ∉ (({1, 2} : Finset ℕ) : Set ℕ)} : Finset (Equiv.Perm (Fin n))) := by intro σ hσ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hσ ⊢ have hcyc : σ.IsCycle := by rw [← Equiv.Perm.card_cycleType_eq_one, hσ] rfl have hsupp : σ.support.card = n := by rw [← Equiv.Perm.sum_cycleType, hσ] rfl have hsupp_univ : σ.support = Finset.univ := by apply Finset.eq_univ_of_card rw [hsupp, Fintype.card_fin] intro x have hx : x ∈ σ.support := by rw [hsupp_univ]; exact Finset.mem_univ x have h_same : ∀ y : Fin n, σ.SameCycle x y := by intro y have hy : y ∈ σ.support := by rw [hsupp_univ]; exact Finset.mem_univ y rw [Equiv.Perm.mem_support] at hx hy exact hcyc.sameCycle hx hy have h_filt : ({y : Fin n | σ.SameCycle x y} : Finset (Fin n)) = Finset.univ := by ext y simp [h_same y] rw [h_filt, Finset.card_univ, Fintype.card_fin] simp only [Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff, Set.mem_singleton_iff] omega
The number of derangements without 2-cycles on Fin n is at least (n - 1)!.
Since the set of n-cycles is a subset of the permutations with no 1-cycles and no 2-cycles, its cardinality (n - 1)! is bounded above by the cardinality of the latter set, derangements_no_two_cycles_count n.
uses
Finset.card_le_cardhave h_le := Finset.card_le_card h_sub rw [h_card] at h_le change (n - 1).factorial ≤ derangements_no_two_cycles_count n at h_le
The factorial identity (n - 1)! = (n - 1) * (n - 2) * (n - 3)! holds.
Using 3 ≤ n, write n = 3 + k. Then (n - 1)! is (k + 2)!, which unfolds twice via (m + 1)! = (m + 1) * m! into (k + 2) * (k + 1) * k!. Expressing k back in terms of n gives (n - 1) * (n - 2) * (n - 3)!.
uses
Nat.exists_eq_add_of_le,Nat.factorial_succhave h_fact : (n - 1).factorial = (n - 1) * (n - 2) * (n - 3).factorial := by obtain ⟨k, rfl⟩ := Nat.exists_eq_add_of_le hn have h1 : 3 + k - 1 = k + 2 := by omega have h2 : 3 + k - 2 = k + 1 := by omega have h3 : 3 + k - 3 = k := by omega rw [h1, h2, h3] rw [Nat.factorial_succ (k + 1), Nat.factorial_succ k] ring rw [h_fact] at h_le
The product (n - 1) * (n - 2) is strictly positive.
Because n ≥ 3, both n - 1 and n - 2 are strictly positive, and therefore their product is strictly positive.
have h_pos : 0 < (n - 1) * (n - 2) := by have : 0 < n - 1 := by omega have : 0 < n - 2 := by omega positivity
(n - 3)! ≤ derangements_no_two_cycles_quotient n.
By definition, the quotient is the integer division of derangements_no_two_cycles_count n by (n - 1) * (n - 2). Because this divisor is strictly positive, the inequality (n - 3)! ≤ count / ((n - 1) * (n - 2)) is equivalent to (n - 3)! * (n - 1) * (n - 2) ≤ count, which matches the established lower bound (n - 1) * (n - 2) * (n - 3)! ≤ count after commuting factors.
uses
Nat.le_div_iff_mul_le,mul_commdsimp [derangements_no_two_cycles_quotient] rw [Nat.le_div_iff_mul_le h_pos] rw [mul_comm] exact h_le
le_trans- Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
Equiv.Perm.card_of_cycleType_singleton- The number of permutations of a finite set α whose cycle type is a single cycle of length n is (n - 1)! * (|α| choose n).
Fintype.card_fin- The cardinality of Fin n = {0, ..., n - 1} is n.
Nat.choose_self- The binomial coefficient n choose n is equal to 1.
mul_one- Multiplying any element by 1 leaves it unchanged: a * 1 = a.
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the set and satisfies the filtering predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finset univ.
true_and- The proposition True ∧ p is equivalent to p.
Equiv.Perm.card_cycleType_eq_one- A permutation is a single non-trivial cycle if and only if its cycle type multiset has cardinality 1.
Equiv.Perm.sum_cycleType- The sum of the lengths of the disjoint cycles in a permutation equals the cardinality of its support.
Finset.eq_univ_of_card- A subset of a finite type whose cardinality equals the cardinality of the type is the entire universe.
Equiv.Perm.mem_support- An element is in the support of a permutation if and only if it is not fixed by the permutation.
Finset.card_univ- The cardinality of the universal finset is the cardinality of the underlying finite type.
Finset.coe_insert- Coercing the insertion of an element into a finset to a set yields the set-theoretic insertion.
Finset.coe_singleton- Coercing a singleton finset to a set yields the singleton set.
Set.mem_insert_iff- An element belongs to insert a s if and only if it equals a or belongs to s.
Set.mem_singleton_iff- An element belongs to the singleton set {b} if and only if it equals b.
Finset.card_le_card- If a finite set s is a subset of t, then |s| ≤ |t|.
Nat.exists_eq_add_of_le- If m ≤ n, then n = m + k for some natural number k.
Nat.factorial_succ- The factorial of n + 1 equals (n + 1) * n!.
Nat.le_div_iff_mul_le- For k > 0, x ≤ y / k in natural division if and only if x * k ≤ y.
mul_comm- Multiplication is commutative: a * b = b * a.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Factorial lower bound on the quotient: Q_n ≥ (n - 3)! for n ≥ 3. -/theorem derangements_no_two_cycles_quotient_ge_factorial (n : ℕ) (hn : 3 ≤ n) : (n - 3).factorial ≤ derangements_no_two_cycles_quotient n := by have hn2 : 2 ≤ n := le_trans (by decide) hn have h_card := Equiv.Perm.card_of_cycleType_singleton (α := Fin n) (n := n) hn2 (by simp) simp only [Fintype.card_fin, Nat.choose_self, mul_one] at h_card have h_sub : ({g : Equiv.Perm (Fin n) | g.cycleType = {n}} : Finset (Equiv.Perm (Fin n))) ⊆ ({σ : Equiv.Perm (Fin n) | ∀ (x : Fin n), ({y : Fin n | σ.SameCycle x y} : Finset (Fin n)).card ∉ (({1, 2} : Finset ℕ) : Set ℕ)} : Finset (Equiv.Perm (Fin n))) := by intro σ hσ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hσ ⊢ have hcyc : σ.IsCycle := by rw [← Equiv.Perm.card_cycleType_eq_one, hσ] rfl have hsupp : σ.support.card = n := by rw [← Equiv.Perm.sum_cycleType, hσ] rfl have hsupp_univ : σ.support = Finset.univ := by apply Finset.eq_univ_of_card rw [hsupp, Fintype.card_fin] intro x have hx : x ∈ σ.support := by rw [hsupp_univ]; exact Finset.mem_univ x have h_same : ∀ y : Fin n, σ.SameCycle x y := by intro y have hy : y ∈ σ.support := by rw [hsupp_univ]; exact Finset.mem_univ y rw [Equiv.Perm.mem_support] at hx hy exact hcyc.sameCycle hx hy have h_filt : ({y : Fin n | σ.SameCycle x y} : Finset (Fin n)) = Finset.univ := by ext y simp [h_same y] rw [h_filt, Finset.card_univ, Fintype.card_fin] simp only [Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff, Set.mem_singleton_iff] omega have h_le := Finset.card_le_card h_sub rw [h_card] at h_le change (n - 1).factorial ≤ derangements_no_two_cycles_count n at h_le have h_fact : (n - 1).factorial = (n - 1) * (n - 2) * (n - 3).factorial := by obtain ⟨k, rfl⟩ := Nat.exists_eq_add_of_le hn have h1 : 3 + k - 1 = k + 2 := by omega have h2 : 3 + k - 2 = k + 1 := by omega have h3 : 3 + k - 3 = k := by omega rw [h1, h2, h3] rw [Nat.factorial_succ (k + 1), Nat.factorial_succ k] ring rw [h_fact] at h_le have h_pos : 0 < (n - 1) * (n - 2) := by have : 0 < n - 1 := by omega have : 0 < n - 2 := by omega positivity dsimp [derangements_no_two_cycles_quotient] rw [Nat.le_div_iff_mul_le h_pos] rw [mul_comm] exact h_le