AFTD Auto-Formalizing Theoretical Domains

loopless_digraph_count

def

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
See it in the graphDiscuss this resultChallenge it