buchholz_pairing_count_eq_factorial_ratio
Provedbuchholzcandes-rechtexact-matrix-completionnoncommutative-khintchinepair-partition
The number of pair partitions of labelled positions is
In the Lean statement, pair partitions are represented as fixed-point-free involutions on Fin (2 * n). This theorem is the standard enumeration: order the labels, divide by for the order inside each pair, and divide by for the order of the pairs.
Preamble
import Definitions.Def_buchholz_pairing open MatrixCompletion
Formal statement
theorem buchholz_pairing_count_eq_factorial_ratio (n : Nat) :
(Fintype.card (BuchholzPairing n) : ℝ) =
(Nat.factorial (2 * n) : ℝ) / ((2 ^ n : ℝ) * (Nat.factorial n : ℝ)) := by
sorry
Source
Candes, Emmanuel, and Benjamin Recht. "Exact matrix completion via convex optimization." Communications of the ACM 55.6 (2012): 111-119.