loopless_digraph_count
For a degree sequence d on n vertices, D(d) is the number of loopless digraphs on n vertices in which every vertex v has both in-degree and out-degree equal to d(v).
Statement
noncomputable def loopless_digraph_count {n : ℕ} (d : Fin n → ℕ) : ℕ
- Defined in
- arXiv:2611.02191 Sec. 1.1
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Used by 2
- threshold_loopless_digraph_ge_oneFor every natural number n and every threshold degree sequence d on n vertices, there exists at least one loopless digraph with in-degree…
- threshold_loopless_digraph_twoFor every threshold degree sequence d on 2 vertices, the number of loopless digraphs with in-degree and out-degree equal to d is 1.
Read back from the Lean
Given an implicit natural number n and a function d : Fin n → ℕ, loopless_digraph_count d is defined as the number (cardinality) of directed graphs D on the vertex set Fin n satisfying all of the following conditions:
1. D is loopless: for every vertex v : Fin n, there is no directed edge from v to v (¬ D.Adj v v).
2. Prescribed out-degrees: for every vertex v : Fin n, the out-degree of v (the number of vertices w : Fin n such that D.Adj v w) is equal to d v.
3. Prescribed in-degrees: for every vertex v : Fin n, the in-degree of v (the number of vertices u : Fin n such that D.Adj u v) is also equal to d v.
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 number D(d) of loopless digraphs on Fin n with in-degree and out-degree both equal to d. -/ noncomputable def loopless_digraph_count {n : ℕ} (d : Fin n → ℕ) : ℕ := open scoped Classical in open Finset in (univ.filter (fun D : Digraph (Fin n) => (∀ v : Fin n, ¬ D.Adj v v) ∧ (∀ v : Fin n, (univ.filter (fun w => D.Adj v w)).card = d v) ∧ (∀ v : Fin n, (univ.filter (fun u => D.Adj u v)).card = d v))).card