FPRD LabShare an approach

← Claims

Theorem · exact enumeration

CRD-RW-1a

Complete reductions are counted by permutations and binary trees

Exact statement

In the occurrence-labelled rewriting system R={aa→a}R=\{aa\to a\}, the complete reductions an⇒∗aa^n\Rightarrow^*a are in bijection with the (n−1)!(n-1)! orders in which the original gaps are deleted. After identifying consecutive contractions with disjoint residual supports, the equivalence classes are the Cn−1C_{n-1} planar full binary trees on nn leaves.

StatusProved in the stated occurrence-labelled model
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

This result separates the number of concrete reduction histories from the number of histories that differ only by the scheduling of independent contractions.

Definitions

  • An occurrence-labelled reduction records the contracted occurrence at every step.
  • Two histories are square-equivalent when one can be obtained from the other by swapping consecutive contractions with disjoint residual supports.

Hypotheses and scope

  • Complete reductions from ana^n to aa in R={aa→a}R=\{aa\to a\}, with occurrence identity retained.

Proof or evidence

A contraction deletes exactly one surviving original gap, and every ordering of the n−1n-1 gaps is legal, giving (n−1)!(n-1)! histories. Each history also determines a planar full binary merge tree. The histories producing a fixed tree are the linear extensions of its internal-vertex dependency order. Adjacent swaps of incomparable internal vertices are exactly swaps of contractions on disjoint leaf intervals, so the square classes are precisely the merge trees. The Catalan recurrence then gives Cn−1C_{n-1} classes.

Enumeration and binary-tree proof →

Verification notes

The counting bijection, the linear-extension argument, and the scope of the quotient were reconstructed from the preserved proof. Exhaustive checks through n=9 are corroborating evidence, not a substitute for the proof.

Limitations

  • The result concerns complete reductions and retains occurrence identity.
  • The Catalan classification does not say that disjoint squares connect different merge trees.
  • No novelty claim is made for the permutation or Catalan combinatorics.

Open work

Compare the classification with standard trace-monoid and associahedral formulations.