§6, display on p. 17 —
ProvedCountOrderings.NFree.display_p17_countLet be an instance of #X3C with sets and , satisfying the paper's standing assumptions (every element of lies in some set, and ), and let be an integer. For every ordering of the edge set , the number of linear extensions of the edge poset whose projection down to coincides with is
where counts the groups of copied edges attached to the last edges of (definition CountOrderings.NFree.Reduction).
This is the first step of the proof of Theorem 6.3: fixing turns the remaining constraints into a tree poset, and the hook-length formula (Lemma 2.2) counts its linear extensions. Summing over expresses as .
Formalization Note. The identity is stated in . Sets, universe elements and copies are indexed from ; the position of is the paper's position .
Differences from the source:
- generalization: a family of (distinct) 3-sets → an indexed family in which two indices may carry the same 3-set; reason: the construction and the count only use indices; for distinct sets this is exactly the paper's instance.
- encoding: defined as → the linear extensions of the edge poset of ; reason: the paper proves the two sets equal on p. 16.
- encoding: the identity between rationals → the same identity in ℝ; reason: same value.
- encoding: sets, universe elements and ordering positions numbered from 1 → zero-based Fin indices, with position p represented in rho and Ccount by p + 1 and the product index i still starting at 1; reason: bijective relabeling preserves the last i edges and every count.
import Mathlib import Definitions.Def_CountOrderings_NFree_Reduction
namespace CountOrderings.NFree
theorem display_p17_count (I : X3CInstance) (hI : I.Standing) (q : ℕ) (hq : 1 ≤ q)
(σ : Fin (4 * I.n) ≃ OrigEdge I) (hσ : σ ∈ omegaLE I) :
(linExtCountGiven I q σ : ℝ) =
((4 * I.n + 3 * I.h * q + I.n * q).factorial : ℝ) *
∏ i ∈ Finset.Icc 1 (4 * I.n), 1 / ((i : ℝ) + (q : ℝ) * (Ccount σ i : ℝ)) := by sorry
end CountOrderings.NFree
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.