cycle_greedy_s
def
The rational Cayley-tree product sum cycle_greedy_s (n : ℕ) : ℚ := ∑ d ∈ Finset.range n, ∏ j ∈ Finset.Icc 1 d, (1 - (j : ℚ) / (n : ℚ)) as a rational number for any natural number n.
Statement
def cycle_greedy_s (n : ℕ) : ℚ- Defined in
- arXiv:2610.15776, Theorem 9 (equation 13)
- Verified
- 02 Nov 2026
- Axioms
- none listed
- Used by 7
- cycle_greedy_second_moment_formulaThe conjectured rational closed-form second moment formula…
- cycle_greedy_second_moment_formula_eq_mean_formFor every natural number n,…
- cycle_greedy_known_meanThe known rational expected assignment cost
cycle_greedy_known_mean (n : ℕ) : ℚ := (n : ℚ) * cycle_greedy_s n / 4under greedy online… - cycle_greedy_second_moment_twoFor n = 2, the exact rational second moment equals the conjectured formula value:…
- cycle_greedy_s_twoThe rational Cayley product sum evaluates to 3/2 at n = 2:
cycle_greedy_s 2 = 3 / 2. - cycle_greedy_second_moment_threeFor n = 3, the exact rational second moment equals the conjectured formula value:…
- cycle_greedy_second_moment_formula_twoThe closed-form second moment formula evaluates to 2/3 at n = 2:
cycle_greedy_second_moment_formula 2 = 2 / 3.
Read back from the Lean
For a natural number $n$, cycle_greedy_s n is the rational number defined as the sum over $d \in \{0, \dots, n-1\}$ (Finset.range n) of the product over integers $j$ from $1$ to $d$ (Finset.Icc 1 d) of $(1 - j/n)$. (When $d = 0$, the product over Finset.Icc 1 0 is empty, evaluating to $1$; when $n = 0$, the sum is empty, evaluating to $0$.)
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The rational Cayley-tree product sum S_n = sum_{d=0}^{n-1} prod_{j=1}^d (1 - j / n). -/ def cycle_greedy_s (n : ℕ) : ℚ := ∑ d ∈ Finset.range n, ∏ j ∈ Finset.Icc 1 d, (1 - (j : ℚ) / n)