- c(12 \cdots
k)}} {\mathcal{S}}(p^{\circ})$.

The other consequences follow directly from the definitions.

Thus, it suffices to restrict our attention to subtrees lying under increasing prefixes. To avoid clutter in the remainder of the results, we abuse notation to let ${\mathcal{S}}(p), {\mathcal{S}}(p^{\circ})$, and ${\mathcal{S}}(\bar{p})$ each refer to their numerators over the standard denominator $\sum_{p\text{-prefixed } \pi \in {\mathfrak{S}}_N}
\theta^{c(\pi)}$. To ensure that this is valid, we avow that all of our equalities will occur between quantities for which their implied denominators agree.

\[t:pc\] For the increasing prefixes $p = [12 \cdots (k-1)]$ and $q = [12 \cdots k]$, we have $${\mathcal{S}}(p^{\circ}) = {\mathcal{S}}(\bar{q}) + {\mathcal{S}}(q^{\circ}) \sum_{\substack{\text{nontrivial
permutations} \\r \text{ of } q \text{ having } p \text{ as a prefix }}} \theta^{c(r)-c(q)}, \text{ and }$$ $${\mathcal{S}}(p) = {\mathcal{S}}(q) \sum_{\substack{\text{nontrivial permutations} \\r \text{ of }
q \text{ having } p \text{ as a prefix }}} \theta^{c(r)-c(q)}.$$

There are $k$ children of $p$ in the prefix tree; they are distinguished by their value in the last position. The prefix $q$ itself is an eligible child so ${\mathcal{S}}(\bar{q})$ is the optimal probability under this subtree. The subtrees under each of the other $k-1$ children of $p$ are isomorphic to ${\mathcal{T}}(q^{\circ})$ via the bijection 