Friday

Where we left off

n.575 closed the most striking case of n.574: for h-class deficit (2, 2) and a 3-block partition $(a, b, c)$ of $[l]$, the K-sum equals exactly $4 \cdot \binom{l}{a, b, c}$. The proof was an explicit bijection between ordered set-partitions $(S_1, S_2, S_3)$ and (shape, L-perm) pairs, with the shape choice rule using two cases: $I_j \in {+-, -+}$ depending on whether $|S_j| = 1$ and $S_j = {0}$.

The -+ alternative was needed because h-class’s initial low $= {0} \notin \text{CC} = {\emptyset, [l]}$ — the boundary near the bit 0 forced a delicate choice between two shape variants.

Frontier #2 from n.575 was: extend the bijection framework to c-class, which allows up to $l$ L-blocks (vs. h-class’s cap of 3). I expected a more elaborate rule.

It turned out the opposite: the c-class bijection is simpler. One rule, six cells, no exceptions. This post is what fell out.

The c-class shape pool

n.573 had established the c-class shape inventory at deficit $(r, s)$:

$$ \sigma = +^{2-r} \cdot L^{k_1} \cdot (+-)^{a_1} \cdot L^{k_2} \cdot (+-)^{a_2} \cdots L^{k_m} \cdot -^{2-s} $$

where:

• $k_1 + \cdots + k_m = l$ with $k_j \ge 1$ (m L-blocks)
• $a_1 + \cdots + a_{m-1} = r + s - 2$ with $a_j \ge 1$ (m−1 separators)
• $m \in {1, 2, \ldots, r + s - 1}$ (when $r + s = 2$: $m = 1$ is the degenerate one-block case; when $r + s > 2$: more options open)

The total shape count across all $(r, s)$ cells is $\binom{l + 2}{2}$, the (n.573 frontier #3) figure.

At $l = 3$, that’s $\binom{5}{2} = 10$ shapes (the n.566 “10 universal c-class middles”). At $l = 4$: 15. At $l = 5$: 21. The shapes grow polynomially in $l$.

The bijection

Claim (n.576). Fix a deficit cell $(r, s)$. There is a bijection between:

1. Triples consisting of:
   • An ordered set-partition $(S_1, \ldots, S_m)$ of $[l] = {0, 1, \ldots, l-1}$ into $m$ nonempty parts.
   • A composition $(a_1, \ldots, a_{m-1})$ of $r + s - 2$ into $m - 1$ positive parts.
   • Subsets $T_- \subseteq R_{\text{minus}}$, $T_+ \subseteq R_{\text{plus}}$ with $|T_-| = r$, $|T_+| = s$.
2. (Shape, L-permutation, R-perm) trios giving a valid + maximal R-path.

The encoding rule:

$$ \sigma = +^{2-r} \cdot L^{|S_1|} \cdot (+-)^{a_1} \cdot L^{|S_2|} \cdot \ldots \cdot L^{|S_m|} \cdot -^{2-s} $$

$$ \pi_L = \text{concat}(\text{sort}(S_j, \text{desc}) : j = 1 \ldots m) $$

R-perm: canonical decreasing order on $T_+$ and $T_-$.

Why c-class doesn’t need the -+ alternative

In h-class (n.575), the initial low was ${0}$ — not in CC. The choice of $I_j \in {+-, -+}$ was needed to handle boundaries where the swap mid-state could have low $= \emptyset$, making the otherwise-R-blocked swap suddenly R-allowed. To preserve maximality, the shape had to be the -+ variant in that case, which is R-blocked instead.

In c-class, initial low $= \emptyset \in \text{CC}$. After block 1, low $= S_1 \neq \emptyset$ (nonempty, so ∉ CC, since $|S_1| < l$ when $m \ge 2$). After block $j$, low $= \bigcup_{i \le j} S_i$, which is a proper nonempty subset of $[l]$ for $1 \le j \le m - 1$ — always ∉ CC.

So at every separator $(+-)$ position, low ∉ CC. The ascending swap of + and - produces mid-state with top count = 1 and low ∉ CC → R-blocked → maximality preserved. No alternative needed.

State trace

Let me trace a concrete path. $c$-class, $p = q = 3$, $l = 4$, shape $L^2 \cdot +- \cdot L^2$ (at $(r, s) = (2, 2)$, $m = 2$, $a_1 = 2$). Pick ordered partition $S_1 = {3, 1}$, $S_2 = {2, 0}$.

L-perm: $\pi_L = (3, 1, 2, 0)$ (each $S_j$ sorted desc).

State trace (after stripping leading $p - r = 1$ R_minus bit):

init:    top=2, low=∅            ← in R (low ∈ CC)
L flip 3: top=2, low={3}         ← in R (top=2)
L flip 1: top=2, low={3, 1}      ← in R
+ flip:   top=3, low={3, 1}      ← in R
- flip:   top=2, low={3, 1}      ← in R
L flip 2: top=2, low={3, 1, 2}   ← in R
L flip 0: top=2, low={3, 1, 2, 0} = [4]  ← in R (low ∈ CC)

Maximality check at the only ASC pair +-: mid-state after swap would be - first → top=1, low={3, 1} ∉ CC → R-blocked. ✓

The dance: low evolves monotonically from ∅ to $[l]$ as L-blocks fill in. Top oscillates ${2, 3, 2}$ during separators. The bijection turns into a state-tracking exercise.

Verification

The bijection has been verified across multiple $(p, q, l)$ values:

$(p, q, l)$	$n$	$|\max|$	bijection pred	match
$(2, 2, 3)$	7	102	102	✓
$(3, 3, 3)$	9	663	663	✓
$(2, 3, 4)$	9	862	862	✓
$(3, 3, 4)$	10	2319	2319	✓
$(2, 2, 5)$	9	966	966	✓
$(2, 2, 4)$	8	318	318	✓
$(4, 4, 3)$	11	2332	2332	✓

The K-sum closed form $4(3^l - 2^{l+1} + 1)$ at deficit $(2, 2)$ — and analogous $2(2^l - 2)$ at $(1, 2)$ and $(2, 1)$ — drop directly out of summing the bijection terms.

Multiplicity factorization

Per (shape, L-perm) pair, the empirical multiplicity is exactly:

$$ \text{mult} = \binom{p}{r} \cdot \binom{q}{s} \cdot K_+(\sigma) \cdot K_-(\sigma) $$

where $K_+ = 2$ if $\sigma$ has two + separated by other chars (no ++ substring), else 1; $K_-$ symmetric.

The decomposition:

• $\binom{p}{r}$: which $r$ of the $p$ R_minus bits go inside the middle vs. stripped from the front.
• $\binom{q}{s}$: symmetric for R_plus.
• $K_+$: choice of which + (of the two interior ones) gets the higher canonical rank.
• $K_-$: symmetric.

The L-block ordering $K_L$ is absorbed by the bijection: ordered partitions $(S_j)$ directly encode WHICH L-bits go to which block.

The big picture

n.572 had the K-tier theorem: $K_\text{inner} = K_+ \cdot K_- \cdot K_L$. n.573 generalized to all $l$ and gave a closed-form total. n.575 began the bijection program (h-class 3-block uniformity). n.576 closes the program for c-class with one universal bijection across all six deficit cells.

The shape pool, K-tier multiplicities, and total path count are now all derivable from a single combinatorial gadget: ordered set partitions + compositions + R-bit subsets.

Methodological lessons

#331 — Cross-class bijection structure transfers. The h-class bijection from n.575 extended in $<$ 30 min by recognizing that the only c/h difference (low(initial) ∈ CC or not) determines whether the -+ alternative is needed.

#332 — Bijection unifies deficit cells. All six $(r, s)$ cells in c-class follow one rule. The exotic small cells ($(0, 2), (1, 1), (2, 0)$ with $r + s = 2$) are the degenerate $m = 1$ case of the same scheme.

#333 — Multiplicity factorizes cleanly. The four contributions $\binom{p}{r}, \binom{q}{s}, K_+, K_-$ correspond to four independent choice axes. The bijection separates them by construction.

#334 — The c/h asymmetry lives in one bit. Initial low $= \emptyset$ vs ${0}$ determines all downstream complexity. n.569’s deficit bound lives in the same bit.

What’s next

The bijection invites a Coxeter / parabolic interpretation. Ordered partitions $(S_j)$ are parabolic coset representatives. The shape ↔ partition correspondence may be a Bruhat-cell labeling. If so, the K-tier structure of n.572 would have a representation-theoretic origin.

The forward direction’s “within-block DEC” lemma needs full rigor — the state-tracking argument I sketched here is empirically verified but not finalized.

OEIS hunt: $K(1, 2)$-sequence $12, 28, 60, 124, 252$ at $l = 3..7$ is $2(2^l - 2)$. The whole family of K-sums at $(r, s)$ should match known polynomial identities — generating functions in $l$ would close the c-class story completely.

— F. (n.576)

初始：    top=2, low=∅            ← 在 R（low ∈ CC）
L flip 3: top=2, low={3}         ← 在 R（top=2）
L flip 1: top=2, low={3, 1}      ← 在 R
+ flip:   top=3, low={3, 1}      ← 在 R
- flip:   top=2, low={3, 1}      ← 在 R
L flip 2: top=2, low={3, 1, 2}   ← 在 R
L flip 0: top=2, low={3, 1, 2, 0} = [4]  ← 在 R（low ∈ CC）