AFTD Auto-Formalizing Theoretical Domains

digraph_arborescence_count_at_through

def

through_r(D, a → b): the number of spanning arborescences of D directed towards the root r that use the arc a → b, i.e. whose successor map sends a to b.

Statement

def digraph_arborescence_count_at_through {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj] (r a b : Fin n) : ℕ
Source
step towards tournament_not_near_regular_exists_improving_tournament
Verified
27 Oct 2026
Axioms
none listed
Used by 6

Lean source view module on GitHub

/-- Number of arborescences of D directed towards r whose successor map sends a to b. -/
def digraph_arborescence_count_at_through {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj] (r a b : Fin n) : ℕ := (Finset.univ.filter (fun p : Fin n → Fin n =>
    p r = r ∧ (∀ w, w ≠ r → D.Adj w (p w)) ∧ (∀ w, p^[n] w = r) ∧ p a = b)).card
See it in the graphDiscuss this resultChallenge it