AFTD Auto-Formalizing Theoretical Domains

q_ary_subsequence_num_embeddings

def

For words u of length m and w of length n over an alphabet of size q represented by Fin q, q_ary_subsequence_num_embeddings q m n u w is the number of strictly increasing maps f from Fin m to Fin n such that w (f i) = u i for all i.

Statement

def q_ary_subsequence_num_embeddings (q m n : ℕ) (u : Fin m → Fin q) (w : Fin n → Fin q) : ℕ
Defined in
arXiv:2611.01064, Section 2; arXiv:2407.10026
Verified
10 Nov 2026
Axioms
none listed
Built on 2
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 10
  • qary_two_deletion_posteriorFor a received q-ary word y of length n, qary_two_deletion_posterior q n y x is the posterior probability of transmitting x of length n +…
  • binary_deletion_collision_eq_q_ary_twoFor every k, n and binary word w of length n, the binary k-deletion collision sum of w equals the q-ary k-deletion collision sum (q = 2)…
  • min_q_ary_deletion_collisionFor natural numbers q, k, and n, min_q_ary_deletion_collision q k n is the minimum over all q-ary words w of length n of the sum over all…
  • op_1537_binary_length_two_one_deletionFor any nonconstant binary word y : Fin 2 → Fin 2 of length 2, there exists a longest run [a, b) of y and an immediately adjacent run [a',…
  • min_q_ary_deletion_collision_two_eq_min_binaryFor all k and n, the minimum q-ary k-deletion collision sum over words of length n with q = 2 equals the minimum binary k-deletion…
  • q_ary_deletion_collisionFor natural numbers q, k, and n, and a q-ary word w of length n represented as a function from Fin n to Fin q, q_ary_deletion_collision q…
  • op_1534_constant_word_deletion_envelope_eqFor integers t ≥ 1, q ≥ 2, and n ≥ 1, and any threshold r, the t-deletion hinge sum of the all-zero word qary_all_zero_word q n (by omega)…
  • qary_multiple_deletion_hingeFor natural numbers t, q, n, and r, and a q-ary word y of length n (y : Fin n → Fin q), the t-deletion hinge sum is the sum over all words…
  • op_1537_ternary_length_two_one_deletionFor any nonconstant ternary word y : Fin 2 → Fin 3 of length 2, there exists a longest run [a, b) of y and an immediately adjacent run…
  • qary_two_deletion_hingeFor integers q, n, and r, and a q-ary word y of length n, qary_two_deletion_hinge q n r y is the sum over all words x : Fin (n + 2) → Fin…

Read back from the Lean

Given natural numbers q, m, and n, a sequence u : Fin m → Fin q, and a sequence w : Fin n → Fin q, q_ary_subsequence_num_embeddings q m n u w is defined as the number of strictly monotone functions f : Fin m → Fin n such that for all i : Fin m, w (f i) = u i.

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

/-- Number of strictly increasing index embeddings from Fin m to Fin n spelling u from w over Fin q. -/
def q_ary_subsequence_num_embeddings (q m n : ℕ) (u : Fin m → Fin q) (w : Fin n → Fin q) : ℕ := (Finset.univ.filter (fun f : Fin m → Fin n => StrictMono f ∧ ∀ i, w (f i) = u i)).card
See it in the graphDiscuss this resultChallenge it