Capstone A: The Counting Laboratory

A reproducible counting question

The laboratory asks whether three independently specified families have the same number of objects of size $n$, and, if so, whether structural decompositions and invertible maps explain the agreement. We will count 231-avoiding permutations, noncrossing set partitions, and Dyck paths. Their common answer will be the Catalan number $C_n$, but enumeration must start from each family's definition rather than generating one family and renaming its objects.

The parameters are fixed as follows. A permutation uses each integer in $[n]=\{1,\ldots,n\}$ once and avoids 231 when no positions $i\lt j\lt k$ satisfy $\sigma_j>\sigma_i>\sigma_k$. A set partition divides $[n]$ into nonempty disjoint blocks; it is noncrossing when no $a\lt b\lt c\lt d$ place $a,c$ in one block and $b,d$ in a different block. Blocks are unordered, but the ground-set order matters. A Dyck path is a word with $n$ letters U and $n$ letters D, interpreting them as height increments $+1$ and $-1$, with every prefix height nonnegative. Its size is the semilength $n$, not its word length $2n$.

At $n=0$, each family has one empty object: an empty permutation, an empty partition, and an empty word. Do not confuse a set partition with an integer partition or permit repeated permutation values. These choices determine the question and its answer.

Exact enumeration with independent checks

The program uses only the Python standard library. Save the panel as counting_lab.py and run python3 counting_lab.py in an otherwise empty output directory. It writes counts.csv and asymptotics.csv, prints the interpreter version and output checksums, and stops on any failed assertion. The reference run used Python 3.12.14. Reproduction should retain the source bytes, invocation, interpreter version, and exact outputs; checksums identify bytes but do not prove correctness.

The permutation enumerator tests all $n!$ tuples against the defining inequality. The partition enumerator inserts successive labels into existing blocks or a new last block, so every set partition appears once; a separate alternating-four-label test removes crossings. The path enumerator appends an up-step when fewer than $n$ have been used and a down-step only when the height is positive. Every valid word has exactly one sequence of such choices. Thus the three enumeration mechanisms are independent of the Catalan recurrence and of the bijections used later.

The independent arithmetic checks are the recurrence derived from first returns and the binomial formula derived from reflection. Both must agree with the three enumerator lengths. Duplicate checks, positive and negative predicate examples, full image-set comparisons, and both directions of each round trip add different checks rather than merely repeating one count. The conversion functions below are specified on valid family members only; they are not validators for arbitrary external input.

from itertools import combinations, permutations
from math import comb, pi, sqrt
import csv
import hashlib
from pathlib import Path
import sys


def dyck_paths(n):
    def visit(word, up, down):
        if up == down == n:
            yield word
        if up < n:
            yield from visit(word + 'U', up + 1, down)
        if down < up:
            yield from visit(word + 'D', up, down + 1)
    yield from visit('', 0, 0)


def avoids_231(p):
    return not any(p[j] > p[i] > p[k]
                   for i, j, k in combinations(range(len(p)), 3))


def set_partitions(n):
    def visit(i, blocks):
        if i > n:
            yield blocks
            return
        for j in range(len(blocks)):
            new = blocks[:j] + (blocks[j] + (i,),) + blocks[j + 1:]
            yield from visit(i + 1, new)
        yield from visit(i + 1, blocks + ((i,),))
    yield from visit(1, ())


def noncrossing(blocks):
    owner = {v: j for j, block in enumerate(blocks) for v in block}
    return not any(owner[a] == owner[c] and owner[b] == owner[d]
                   and owner[a] != owner[b]
                   for a, b, c, d in combinations(sorted(owner), 4))


def to_dyck(p):
    if not p:
        return ''
    n = len(p)
    j = p.index(n)
    right = tuple(x - j for x in p[j + 1:])
    return 'U' + to_dyck(p[:j]) + 'D' + to_dyck(right)


def from_dyck(word):
    if not word:
        return ()
    height = 0
    for t, step in enumerate(word):
        height += 1 if step == 'U' else -1
        if height == 0:
            break
    left = from_dyck(word[1:t])
    right = from_dyck(word[t + 1:])
    n = len(word) // 2
    return left + (n,) + tuple(x + len(left) for x in right)


def partition_to_dyck(blocks):
    n = sum(map(len, blocks))
    starts = {block[0]: len(block) for block in blocks}
    return ''.join('U' * starts.get(i, 0) + 'D'
                   for i in range(1, n + 1))


def dyck_to_partition(word):
    stack, blocks = [], {}
    t = 0
    for i in range(1, len(word) // 2 + 1):
        while t < len(word) and word[t] == 'U':
            stack.append(i)
            t += 1
        label = stack.pop()
        blocks.setdefault(label, []).append(i)
        assert word[t] == 'D'
        t += 1
    assert not stack and t == len(word)
    return tuple(tuple(blocks[k]) for k in sorted(blocks))


def checked_counts(limit):
    recurrence = [1]
    rows = []
    for n in range(limit + 1):
        if n:
            recurrence.append(sum(recurrence[j] * recurrence[n - 1 - j]
                                  for j in range(n)))
        paths = list(dyck_paths(n))
        perms = [p for p in permutations(range(1, n + 1)) if avoids_231(p)]
        parts = [p for p in set_partitions(n) if noncrossing(p)]
        assert len(set(paths)) == len(paths)
        assert len(set(perms)) == len(perms)
        assert len(set(parts)) == len(parts)
        formula = comb(2 * n, n) // (n + 1)
        assert len(paths) == len(perms) == len(parts) == recurrence[n] == formula
        for p in perms:
            assert from_dyck(to_dyck(p)) == p
        for p in parts:
            assert dyck_to_partition(partition_to_dyck(p)) == p
        for word in paths:
            assert to_dyck(from_dyck(word)) == word
            assert partition_to_dyck(dyck_to_partition(word)) == word
        assert {to_dyck(p) for p in perms} == set(paths)
        assert {partition_to_dyck(p) for p in parts} == set(paths)
        rows.append((n, len(perms), len(parts), len(paths), formula))
    return rows


def main():
    assert avoids_231((1, 2, 3)) and not avoids_231((2, 3, 1))
    assert not noncrossing(((1, 3), (2, 4)))
    assert noncrossing(((1, 4), (2, 3)))
    assert set(dyck_paths(2)) == {'UUDD', 'UDUD'}
    rows = checked_counts(7)
    with open('counts.csv', 'w', newline='', encoding='utf-8') as f:
        writer = csv.writer(f, lineterminator='\n')
        writer.writerow(['n', 'permutations', 'noncrossing_partitions',
                         'dyck_paths', 'formula'])
        writer.writerows(rows)
    with open('asymptotics.csv', 'w', newline='', encoding='utf-8') as f:
        writer = csv.writer(f, lineterminator='\n')
        writer.writerow(['n', 'exact', 'leading_relative_error',
                         'corrected_relative_error'])
        for n in (5, 10, 20, 50, 100):
            exact = comb(2 * n, n) // (n + 1)
            leading = 4.0 ** n / (sqrt(pi) * n ** 1.5)
            corrected = leading * (1 - 9 / (8 * n))
            writer.writerow([n, exact, format(leading / exact - 1, '.12g'),
                             format(corrected / exact - 1, '.12g')])
    for n in range(1, 201):
        exact = comb(2 * n, n) // (n + 1)
        error = 4.0 ** n / (sqrt(pi) * n ** 1.5) / exact - 1
        assert 0 < error < 9 / (8 * n) + 1 / n ** 2
    print('Python:', sys.version.split()[0])
    print('All exact counts and inverse checks passed through n=7.')
    print('Local error conjecture passed 200 floating-point checks.')
    for name in ('counts.csv', 'asymptotics.csv'):
        print(name, hashlib.sha256(Path(name).read_bytes()).hexdigest())


if __name__ == '__main__':
    main()

The exact CSV has header n,permutations,noncrossing_partitions,dyck_paths,formula; its eight data rows are

0,1,1,1,1; 1,1,1,1,1; 2,2,2,2,2; 3,5,5,5,5; 4,14,14,14,14; 5,42,42,42,42; 6,132,132,132,132; 7,429,429,429,429.

These small enumerators are deliberately transparent rather than scalable. Pattern testing costs $O(n!n^3)$ time, and filtering set partitions costs $O(B_n n^4)$, where $B_n$ is the number of all set partitions of $[n]$. Materializing the valid lists uses $O(nC_n)$ space, aside from temporary enumeration. Generating counts by the recurrence needs only $O(N^2)$ integer operations through size $N$, but that faster method is not an independent enumerator. Arbitrary-precision integer operation costs grow with the numbers involved.

Exercise: how many size-three permutations are rejected? Hint: only a length-three tuple can be its own full 231 occurrence. Solution: one, namely $(2,3,1)$, leaving five. For partitions, $\{\{1,3\},\{2,4\}\}$ is the smallest crossing example; checking it guards against treating every set partition as noncrossing.

Generating functions as executable specifications

Let $C(z)=\sum_{n\ge0}C_nz^n$ be an ordinary generating function, with size recorded by the exponent. A nonempty Dyck path has a unique first-return decomposition U L D R, where $L,R$ are Dyck paths. The first up-step and its matching down-step contribute one unit of semilength, so

$$C(z)=1+zC(z)^2,\qquad C_0=1,\qquad C_n=\sum_{j=0}^{n-1}C_jC_{n-1-j}.$$

The recurrence is executable coefficient extraction: each new coefficient depends only on earlier ones. At $n=4$, its four summands are $5,2,2,5$, totaling 14. The unique formal-series solution with constant term one is

$$C(z)=\frac{1-\sqrt{1-4z}}{2z}=1+z+2z^2+5z^3+14z^4+42z^5+\cdots.$$

The apparent singularity at zero is removable. The other quadratic branch has a pole at zero and is not a counting series. This branch choice is part of the specification, not a numerical convention.

For a 231-avoiding permutation, split at its maximum as $L\,n\,R$. Every left value must be smaller than every right value: otherwise a left value, $n$, and a right value form 231. Each part must itself avoid 231. Conversely, separated values and avoiding parts prevent an occurrence crossing the split. If the left size is $j$, its values are forced to be $[j]$; no binomial factor for distributing labels is needed. This gives the same recurrence, hence the same generating function. Using an exponential generating function or adding a label-choice factor here would describe another counting problem.

For a noncrossing partition, let the block containing 1 have $k$ members. Its successive members delimit $k-1$ intervening intervals and one final interval. Other blocks cannot cross these boundaries, and each interval carries an arbitrary noncrossing partition. Conversely, these choices reconstruct a unique partition; interval sizes determine the distinguished block's labels. Therefore

$$C(z)=1+\sum_{k\ge1}z^kC(z)^k=\frac{1}{1-zC(z)},$$

which rearranges to $C=1+zC^2$. The geometric series is valid formally because $zC$ has zero constant term. These are three structural derivations, not an assumption that matching initial coefficients imply matching infinite sequences.

For a separate closed-form check, there are $\binom{2n}{n}$ unrestricted words with equally many up- and down-steps. Reflect the prefix through the first visit to height $-1$ in a bad word, interchanging U and D there. This bijects bad words with words having $n+1$ up-steps and $n-1$ down-steps: the inverse reflects through the first visit to height $+1$. Thus, for $n\ge1$,

$$C_n=\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}.$$

The empty case is handled separately. The program compares this integer formula with the recurrence and all three independently generated lists.

Exercise: extract the coefficient of size five from the recurrence. Solution: $14+5+4+5+14=42$. This coefficient check applies to all three families only because their decompositions have been proved.

Bijections with verified inverses

The permutation map is recursive: send the empty permutation to the empty word, and send $L\,n\,R$ to U followed by the path of $L$, then D, then the path of standardized $R$. Standardization subtracts the left size $j$ from every right value. The inverse finds the first return to height zero, decodes the enclosed path and the suffix, inserts the new maximum, and shifts right values upward by the decoded left size.

General inverse proof: proceed by induction on size. The maximum split determines exactly the left and right subobjects, and the path's first-return split recovers exactly those two subwords. By induction, both recursive calls invert each other. The forced value sets recover the original labels. The same reasoning starting from a path proves the reverse composition is the identity. Nonnegative enclosed heights and suffix heights show the forward output is Dyck; separated values show the inverse output avoids 231. Both domain and codomain claims are needed in addition to the round trips.

The partition map reads labels $i=1,\ldots,n$. If $i$ is a block minimum, emit as many U letters as that block has members; then emit one D for label $i$. Otherwise emit just D. Every prefix has nonnegative height because every processed label belongs to a block whose minimum has already been processed, so the number of emitted up-steps is at least the number of down-steps. At the end both numbers equal $n$.

The inverse labels each up-step in the run immediately before the $i$th down-step by $i$, pushes these labels onto a stack, and assigns $i$ to the block named by the label popped on that down-step. A nonempty up-run creates a block containing its own minimum. The Dyck condition guarantees that every pop is possible, and the final height guarantees an empty stack.

Why noncrossing is essential: suppose a label of an older unfinished block were assigned while a newer unfinished block remained above it on the stack. Their minima and the current and later members would give four alternating labels, a crossing. Therefore the forward encoding of a noncrossing partition must finish the top unfinished block first, exactly the inverse's rule. Conversely, the stack rule cannot create alternating blocks: a newly started block must finish before an older block resumes. This proves both inverse identities and noncrossing of the reconstructed partition.

For example, $\{\{1,4\},\{2,3\}\}$ emits UUDUUDDD. On down-steps numbered 1 through 4, the popped block labels are $1,2,2,1$, reconstructing exactly those blocks. The same block sizes attached to minima in an arbitrary crossing partition would not necessarily recover it, which explains the need for the domain restriction.

The finite tests check both maps on every valid object through size seven, not on a random sample. There are 626 objects across sizes zero through seven in each family. Such tests can reveal errors in code, but only the preceding induction and stack arguments establish the maps in all sizes.

Exercise: decode UDUD by both inverses. Solution: the permutation is $(2,1)$ and the partition is $\{\{1\},\{2\}\}$. A bijection need not preserve intuitive notions of order; test the specified map rather than an expected visual resemblance.

Asymptotic estimates against exact data

The singularity-analysis method in Flajolet and Sedgewick's Analytic Combinatorics, Chapter VI, transfers local singular behavior to coefficient estimates. The full treatment is available through the authors' book resources. Here we check the square-root case rather than applying a theorem solely because a radical appears.

The branch of $\sqrt{1-4z}$ equal to one at zero gives an analytic continuation away from the ray beginning at $\rho=1/4$ on the positive real axis. Zero is removable, and $\rho$ is the unique singularity on the circle of convergence. The function is analytic in a slit neighborhood of that circle, in particular a dented, or $\Delta$, domain avoiding the ray from $\rho$. Setting $t=\sqrt{1-4z}$ gives $C(z)=2/(1+t)=2-2t+2t^2-2t^3+\cdots$ locally. The noninteger exponent $1/2$ and its nonzero coefficient control the leading asymptotic; analytic integer-power terms do not supply its leading singular contribution.

The square-root transfer formula gives a contribution proportional to $\rho^{-n}n^{-3/2}/\Gamma(-1/2)$, where $\Gamma(-1/2)=-2\sqrt\pi$. Multiplying by the singular coefficient $-2$ yields

$$C_n\sim A_n:=\frac{4^n}{\sqrt\pi\,n^{3/2}}.$$

For an independent analytical derivation, Stirling's expansion gives $\binom{2n}{n}=4^n(\pi n)^{-1/2}(1-1/(8n)+O(n^{-2}))$. Dividing by $n+1$ yields

$$C_n=A_n\left(1-\frac{9}{8n}+O(n^{-2})\right).$$

Thus use the corrected estimate $B_n=A_n(1-9/(8n))$. It is an asymptotic correction, not a universally positive counting formula: at $n=1$ it is negative. Both estimates are used only at positive sizes, and the comparison below starts at size five.

Define signed relative errors $e_n=A_n/C_n-1$ and $f_n=B_n/C_n-1$. The exact denominators come from integer arithmetic; the estimates and displayed percentages use floating-point arithmetic and rounding. The reproducible numerical results are:

• $n=5$, exact 42: $e_n=23.032748\%$, $f_n=-4.649621\%$.
• $n=10$, exact 16,796: $e_n=11.383051\%$, $f_n=-1.147542\%$.
• $n=20$, exact 6,564,120,420: $e_n=5.658236\%$, $f_n=-0.285039\%$.
• $n=50$, exact 1978261657756160653623774456: $e_n=2.255315\%$, $f_n=-0.045430\%$.
• $n=100$, exact 896519947090131496687170070074100632420837521538745909320: $e_n=1.126328\%$, $f_n=-0.011343\%$.

The CSV retains the full exact integers at every displayed size. The expansion proves leading relative error $O(1/n)$ and corrected relative error $O(1/n^2)$ as $n\to\infty$; the table alone does not. It does not provide a certified finite-size error bound with an explicit constant. Larger numerical studies should use logarithms or higher precision to avoid overflow and cancellation.

Exercise: does a 23% error at size five contradict $C_n\sim A_n$? Solution: no. Asymptotic equivalence concerns the limiting ratio, not an exact formula or a prescribed error threshold at every finite size.

Counting laboratory report and assessment

The reference result is that all three families have count $C_n=\binom{2n}{n}/(n+1)$, established by structural decompositions and bijections, with independent exhaustive validation through size seven. The generating-function branch and singularity hypotheses justify the leading estimate, while Stirling's expansion independently verifies its constant and first correction. Report these as proved classical results, not new discoveries.

The code is the complete panel above. The exact count rows, CSV generation, and asymptotic definitions specify the data. A reproduction should place counting_lab.py, the two generated CSV files, and a short environment-and-invocation note together with the written proofs. The reference exact-data SHA-256 is 1dd37f09f3acd4d42907ec9eea5d144d0cecdc9867452e5d59e3777f5fb244f5 for counts.csv. Floating-point output may vary in its last digits across environments; exact integer output must not. Preserve the supplied newline and header conventions when comparing byte checksums.

Conjecture, separated from the results: motivated by numerical checks, propose that for every integer $n\ge1$,

$$0\lt e_n\lt\frac{9}{8n}+\frac{1}{n^2}.$$

This is an unproved assertion in this laboratory report, not a claim of a new open problem in the literature. The program checks it for $1\le n\le200$ using floating-point estimates. Those checks are experimental evidence and are not certified inequalities for those inputs. The asymptotic expansion suggests its scale but does not establish the assertion for every size. An optional extension must either prove explicit remainder bounds, produce a certified counterexample, or retain the conjecture label. A further literature review is required before asserting novelty.

A useful application is testing random generators: an algorithm claiming a uniform sample of Dyck paths can be compared against the exact finite universe, while the bijections transport a genuinely uniform distribution to either other family. Uniformity does not follow from a bijection alone if the initial generator is biased. Counting supplies the denominator, inverse verification supplies the correspondence, and a separate probability argument must justify the sampling rule.