Exact enumeration of closed and open meanders in O*(2^n) time and space via a first-crossing partition of matching pairs

A closed meander of order n is a pair of noncrossing perfect matchings on 2n ordered points whose union is a single cycle. We give an exact algorithm for the closed meandric number M_n that uses O*(2^n) bit time and bit space, where O* suppresses factors polynomial in n. The algorithm partitions ordered matching pairs according to the first cut at which their combined Dyck height reaches a threshold K. Pairs that never reach K are counted by a bounded-height planar connectivity transfer costing O*(4^(K-1)). Every other pair is assigned to a sector determined by its first-hit data. Exact down budgets allow guaranteed through arches to be joined during an asymmetric inward scan, while a four-seam noncrossing representation keeps the retained boundary within 2(n-K)+O(1) endpoints. This gives O*(4^(n-K)) for all sectors together. Balancing the two branches yields O*(2^n). An exterior-arch cut identity extends the computation to open meanders, so one run returns M_n, Open(2n-1), and Open(2n). The reference evaluator’s correctness, the width bounds, and a carrier-cardinality bound with the required exponential factors are formally verified in Lean 4; the polynomial-factor bit-time and bit-space accounting is proved on paper. The optimized Rust implementation is validated differentially. It reproduces published values through closed order 28 and returns production outputs through closed order 30 and open crossing count 60. Values beyond the published OEIS range have no independent numerical validation or certificate replay. Small-order certificates are accepted by a checker whose soundness is proved in Lean. To our knowledge, an O*(2^n) bound for unrestricted exact closed meander counting has not previously been established. The accompanying tagged repository and GitHub release include the source code, Lean formalization, certificate checker, reproduction scripts, and canonical production-run archive.