enumeratio

Appearance

The collection atlas ​

A map of what's in the library and how the pieces relate — the families, the bijections between them, and the counting sequences that tie them together. Written for the curious: no combinatorics background assumed. It's a companion to the explorer, not a spec; where a claim is a known theorem it's flagged, and collections we don't have yet are called out as (not yet built) so the gaps are visible too.

Two words used throughout:

  • carrier — the data type an element is (a permutation is an array; a subset is a sorted list; a partition is a list of parts). Several collections can share one carrier.
  • grading — how a collection is sliced into fibers by size parameters. The same objects under a different grading is a different, order-isomorphic collection (see "Grading grids" below).

The organizing ideas ​

A few patterns recur across the whole library. Spot these and the ~130 collections stop looking like a list and start looking like a small number of ideas seen from many angles.

Grading grids → order-isomorphic siblings ​

One carrier often hosts several collections that differ only in how they're sliced. The cleanest example:

graded by n (everything)graded by (n, k)
subsets of [n]subsets — all 2ⁿ (the powerset)finite_sets — the k-subsets, C(n,k)
set partitionsset_partitions — Bell(n)set_partitions_into_k_blocks — Stirling₂(n,k)
ordered set partitionsset_compositions / surjections — Fubini(n)surjections_onto_k — k!·S(n,k)
integer partitionsinteger_partitions — p(n)k_part_partitions — p(n into k parts)
integer compositionsinteger_compositions — 2ⁿ⁻¹compositions_into_k_parts — C(n−1,k−1)

Same elements, same order, different fiber structure — order-isomorphic siblings. When we want a new slicing we add a sibling rather than overload one collection. (Sage's family constructors — SetPartitions(n) vs SetPartitions(n,k), OrderedSetPartitions(n) vs (n,k) — are the reference for which slicings are canonical.)

The word side of a structure ​

Many structures have a "word encoding" — a string that records the structure — realized as its own collection over its own carrier, order-isomorphic to the structure:

  • set_partitions ↔ restricted_growth_strings (RGS: the block-id of each element, 010 = {1,3}/{2})
  • set_compositions ↔ surjections (the surjection word: which ordered block each element lands in)
  • permutations ↔ lehmer_codes (the inversion table)
  • ordered_trees ↔ dyck_paths (balanced parens (()) vs up/down steps UUDD)

Restriction hierarchies ​

A collection is often a parent filtered by a property — same carrier, a predicate carves out the sub-family. These form little lattices:

  • permutations ⊃ derangements (no fixed point), involutions (self-inverse), even_permutations (sign +1), cyclic_permutations (a single n-cycle), connected_permutations (indecomposable), alternating_permutations (up-down), grassmannian_permutations (≤1 descent), cograssmannian_permutations (≤1 ascent), baxter_permutations (avoid the vincular 2-41-3, 3-14-2), simple_permutations (no non-trivial interval), non_crossing_permutations (cycles form a non-crossing partition).
  • integer_partitions ⊃ distinct_partitions, odd_partitions, self_conjugate_partitions, bounded_part_partitions, square_partitions, triangular_partitions.
  • integer_compositions ⊃ odd_compositions, palindromic_compositions, carlitz_compositions (no two equal adjacent parts), proper_compositions (parts ≥ 2).
  • set_partitions ⊃ non_crossing_partitions, non_nesting_partitions.
  • binary_words ⊃ binary_palindromes, primitive_binary_strings (aperiodic), binary_necklaces (lex-least rotation) ⊃ lyndon_words (aperiodic necklaces), binary_bracelets (lex-least under rotation+reflection, reflection = reversal); sparse_subsets / independent_sets_cycle (no two adjacent 1s, on a path / a cycle). The k-ary generalisations k_necklaces/k_bracelets/k_lyndon_words are the same predicates over the words carrier (base letters).

Dualities and bijections (the theorems worth knowing) ​

  • Euler's theorem: |distinct_partitions(n)| = |odd_partitions(n)| — partitions into distinct parts and into odd parts are equinumerous (a classic bijection). The library asserts this directly in its examples.
  • Crossing ↔ nesting: non_crossing_partitions and non_nesting_partitions are different sets of set partitions but both counted by Catalan — dual under an arc involution. (The lone size-4 witness: {1,3}/{2,4} crosses but doesn't nest; {1,4}/{2,3} nests but doesn't cross.) The same duality recurs on chord diagrams: non_crossing_matchings vs non_nesting_matchings.
  • Grassmannian ↔ cograssmannian: ≤1 descent vs ≤1 ascent, related by complement-reverse; both 2ⁿ−n.
  • Conjugation: transposing a partition's Young diagram; self_conjugate_partitions are its fixed points.
  • RSK: the number of standard_tableaux with n cells equals the number of involutions of [n] (the telephone numbers) — a shadow of the Robinson–Schensted correspondence. (RSK itself is referenced but not yet a map here.)

The connective tissue: counting sequences ​

The strongest relationships are the numbers that show up in unrelated-looking places. Each of these is a bridge between collections that otherwise share no structure.

  • Catalan 1,1,2,5,14,42,… — the library's busiest number. Counts dyck_paths, ordered_trees, binary_trees, non_crossing_partitions, non_nesting_partitions, the vertices of the associahedron, and (theorem, Knuth) the permutations avoiding any single length-3 pattern — see the pattern-avoidance gap below.
  • Fibonacci 1,2,3,5,8,… — sparse_subsets (binary strings with no two adjacent 1s = independent sets of the path Pₙ), and fibonacci_numbers.
  • Lucas 2,3,4,7,11,18,… — independent_sets_cycle (independent sets of the cycle Cₙ); the cyclic cousin of the Fibonacci/sparse_subsets line.
  • Bell / Stirling / Fubini — the set-partition grid: Bell(n) = set_partitions, Stirling₂(n,k) = set_partitions_into_k_blocks, Fubini(n) = set_compositions = surjections, and the surjection triangle k!·S(n,k) = surjections_onto_k.
  • Factorial n! — permutations, factorial_numbers, lehmer_codes, subexcedant_seqs (both factorial-base codes for permutations), and the full-length arrangements; the derangement numbers (derangements) and telephone/involution numbers (involutions, standard_tableaux) are its famous relatives; single n-cycles (cyclic_permutations) give (n−1)!.
  • Euler zigzag 1,1,2,5,16,61,… — alternating_permutations (up-down permutations).
  • Cayley (n+1)ⁿ⁻¹ — labeled_trees and parking_functions (equinumerous, a beautiful non-obvious fact).
  • Double factorial (2n−1)!! — perfect_matchings of 2n points, and the sequence itself double_factorial_numbers.
  • Powers — 2ⁿ (subsets/finite_sets), 3ⁿ (signed_subsets), bⁿ (words), 2^⌈n/2⌉ (binary_palindromes).
  • Gaussian binomials (q-analogs) — box_confined_partitions in a parts×max_part box number C(parts+max_part, parts); grouped by size |λ| they give the coefficients of the Gaussian binomial [parts+max_part choose parts]_q (e.g. box(2,2) → 1,1,2,1,1 = 1+q+2q²+q³+q⁴). The q-analog of the ordinary binomial that counts finite_sets.
  • Motzkin / Schröder / Delannoy — the lattice-path cousins of Catalan: motzkin_paths, schroeder_paths, delannoy_paths, central_delannoy_numbers, and the peak-refinement narayana_numbers.
  • Fuss-Catalan C(kn,n)/((k−1)n+1) — k_dyck_paths, the k-ary generalisation of Catalan (k=2); counts k-ary trees with n internal nodes. Catalan is the k=2 row.
  • Baxter 1,1,2,6,22,92,422,… — baxter_permutations (avoiding the vincular 2-41-3, 3-14-2); the two-stack-sortable permutations, in bijection with pairs of twin binary trees.
  • Unsigned Stirling-1 (cycle triangle) — k_cycle_permutations: c(n,k) permutations of [n] with k cycles; the row sum is n!, the same distribution as left-to-right maxima.
  • Eulerian A008292 — k_descent_permutations: ⟨n,k⟩ permutations of [n] with k descents (equidistributed with excedances); each row is a palindrome and sums to n!.
  • Colored / wreath kⁿ·n! — k_colored_permutations = ℤ_k ≀ Sₙ; k=1 is permutations (n!), k=2 is signed_permutations (2ⁿ·n! = |Bₙ|).

Connections to computer science ​

Several collections are the solution spaces of classic (often NP-complete) CS problems — subset sum, maximum-independent-set, Hamiltonian path, modular square roots, sorting. Overview: Connections to computer science; the verified q-binomial ↔ subset-sum connection is detailed in Subset sum & q-binomials.

The families ​

Grouped as the explorer groups them (the tag layer). Every collection carries a fiber_symbol (its ambient-set notation, e.g. Sₙ, 2^[n], C(n,k)), so the explorer can render an element in its set: 1234 ∈ S₄.

Numbers ​

  • Number types (value-addressed, with real arithmetic — the algebra lattice): natural_numbers ℕ, integer_numbers ℤ, rational_numbers ℚ (Calkin–Wilf order), cardinal_numbers (ℕ∪{ℵ₀}), omega_ordinals (< ω^ω), gaussian_integers ℤ[i], modular_residues ℤ/nℤ. Enumerated by a Cantor(zigzag) pairing over the fraction/Gaussian grid: fractional_numbers (unreduced n/d over ℤ×ℕ⁺), gaussian_rationals ℚ(i) (over a signed-ℚ index — rational_numbers zigzagged into all of ℚ), gaussian_fractionals (ℚ(i) as unreduced-fraction pairs).
  • Figurate — polynomial counts of dots in a shape: triangular, square, pentagonal…, plus centered and pyramidal (tetrahedral, pentatope, …).
  • Primes — prime_numbers and the configuration families: twin/cousin/sexy (gap 2/4/6), safe/sophie_germain (p and 2p±1), semiprime/sphenic/k_almost (by number of prime factors), primorial.
  • Factorization shape — square_free, powerful, perfect_power, achilles, integer_factorizations.
  • Divisor sums — abundant/deficient/perfect (σ vs 2n), amicable, practical, arithmetic.
  • Recurrences — fibonacci, lucas, pell, jacobsthal, padovan, perrin, tribonacci, and stern_diatomic_sequence (fusc: a(2n)=a(n), a(2n+1)=a(n)+a(n+1); consecutive pairs enumerate ℚ⁺ once).
  • Counting sequences — the OEIS regulars that count a combinatorial family: catalan, bell, motzkin, schroeder, partition, factorial, double_factorial (matchings of K₂ₙ), narayana, central_delannoy.
  • Digit-based — happy, kaprekar, narcissistic, automorphic, evil/odious (bit parity), pernicious, smith, harshad.
  • Automatic / self-similar — thue_morse (the binary digit-sum parity, fixed point of 0↦01, 1↦10) and stern_diatomic (fusc: the 2-regular hyperbinary counts, whose consecutive pairs enumerate ℚ⁺).

Selections (from an alphabet) ​

subsets (powerset) / finite_sets (k-subsets); signed_subsets (each element absent/+/−, 3ⁿ); sparse_subsets (no adjacent 1s, Fibonacci); arrangements (injective words = k-permutations, the falling factorial [n]^(k̲)).

Set partitions ​

The grid above (set_partitions, set_partitions_into_k_blocks, set_compositions, surjections, surjections_onto_k, restricted_growth_strings) + the crossing/nesting duals (non_crossing_partitions, non_nesting_partitions).

Permutations ​

permutations (the symmetric group Sₙ) and its restriction classes (see the hierarchy above); signed_permutations (the hyperoctahedral / type-B group); lehmer_codes (the word side); affine_permutations, decorated_permutations.

  • Pattern-avoidance family. Permutations avoiding a given pattern. Built:
    • length-3: permutations_avoiding_123/132/213/231/312/321. Knuth's theorem — avoiding any single length-3 pattern gives Catalan — so all six are Wilf-equivalent (same counts, different sets); a bridge from permutations back to Dyck paths and trees. (stack_sortable = Av(231) coincides with permutations_avoiding_231.)
    • length-4: vexillary_permutations = Av(2143) (A005802); separable_permutations = Av(2413,3142) = the large Schröder numbers (tying back to schroeder_paths/schroeder_numbers); smooth_permutations = Av(3412,4231) — the σ whose Schubert variety X_σ is smooth (Lakshmibai–Sandhya), reading an algebraic-geometry property straight off pattern avoidance.
    • boolean_permutations — products of pairwise-commuting simple reflections, equivalently no non-adjacent inversion; counted by Fibonacci F(n+1) (independent sets of the path), tying the class to fib_strings.
    • beyond plain avoidance: baxter_permutations (the vincular patterns 2-41-3, 3-14-2 — the Baxter numbers A001181, two-stack-sortable) and simple_permutations (interval-based — the substitution-decomposition atoms, A111111). The two non-Baxter permutations of [4] are exactly the two simple ones, 2413 and 3142.
  • Cycle geometry. non_crossing_permutations — permutations whose cycle partition is non-crossing (borrows the crossing check from non_crossing_partitions); the lone crossing at n=4 is (1 3)(2 4) = 3412.
  • Statistic gradings (the (n,k) refinements, one identity in two roles — a fiber count is a triangle entry): k_cycle_permutations (exactly k cycles — the unsigned Stirling-1 triangle) and k_descent_permutations (exactly k descents — the Eulerian triangle A008292). Both sum over k back to n!.
  • Colored / wreath. k_colored_permutations = ℤ_k ≀ Sₙ (a colour per position, kⁿ·n!) — the k-parameter generalization of signed_permutations (k=2 = the hyperoctahedral group Bₙ).

Compositions & integer partitions ​

integer_compositions + part-restricted siblings (odd/palindromic/carlitz/proper/into-k-parts, the step/tri/tetra part-set families, and triangular_composition = parts drawn from the triangular numbers {1,3,6,…}); integer_partitions

  • its siblings (distinct/odd/prime_partition/self-conjugate/bounded/square/triangular/k-part), plus plane_partitions, skew_partitions, core_partitions, multiplicative_partitions, largest_part_partitions, and box_confined_partitions (partitions inside a parts×max_part box — Gaussian binomials). The part-set restrictions tie compositions to the named counts: {1,2}→Fibonacci, {1,2,3}→tribonacci, primes→A023360, triangulars→A023361.

Lattice paths ​

dyck_paths (Catalan), motzkin_paths, schroeder_paths, delannoy_paths, riordan_paths, ballot_sequences, and the peak-graded narayana_numbers. All are lattice walks under different step sets / constraints. Two Motzkin refinements sit here too: k_motzkin_paths grades length-n paths by their number of level steps k — the Motzkin triangle C(n,k)·Catalan((n−k)/2), telescoping to Motzkin(n) — and colored_motzkin_paths gives each level step one of r colors, so r=1 is plain Motzkin and r=2 hits Catalan(n+1) (2-colored Motzkin ↔ Dyck of semilength n+1).

Trees, tableaux, matchings, matrices, functions ​

  • Trees: binary_trees (Catalan), ordered_trees (Catalan, = Dyck words), plane_trees (Catalan, the same plane trees carried by their pre-order child-count / Łukasiewicz word rather than the parenthesis word — a distinct carrier, order-isomorphic to dyck_paths), labeled_trees (Cayley, as Prüfer codes), labeled_forests (rooted forests on n vertices, (n+1)ⁿ⁻¹ — the super-root trick makes them labeled_trees on n+1 vertices).
  • Tableaux: standard_tableaux, semistandard_tableaux, gelfand_tsetlin patterns. Shape-restricted SYT: syt_two_row (≤2 rows) and its conjugate syt_two_column (≤2 columns) — both the central binomial coefficients C(n,⌊n/2⌋); syt_hook_shape (hooks (a,1ᵇ)) — 2ⁿ⁻¹.
  • Matchings: perfect_matchings (double factorial), non_crossing_matchings and non_nesting_matchings (both Catalan — the crossing/nesting duality again, on chord diagrams).
  • Matrices: alternating_sign_matrices (the ASM numbers — a famously deep enumeration).
  • Functions: endofunctions (nⁿ), surjections, parking_functions (Cayley), non_decreasing_parking_functions, subexcedant_seqs (aᵢ ≤ i — the factorial-base sequences, n!, a lehmer_codes cousin), rook_placements (non-attacking rooks on the n×n board = the partial permutations of [n], A002720).

Species notation ​

A second way to read an element: as an algebraic expression in the atomic combinatorial species — X (a single labelled point), E (a set), E+ (a nonempty set), C (a cycle), L (a linear order) — carrying the actual labels. Product is juxtaposition and composition (∘) is nesting, so a family's species identity becomes an element rendering: a permutation reads as L = X·X·… (its one-line word, 231 → X[{2}]X[{3}]X[{1}]) or as E∘C (its cycle set, 2143 → C[{1,2}]C[{3,4}]); a set partition reads as E∘E₊ ({1,3}/{2} → E[{E+[{1,3}],E+[{2}]}]). These are representations of the existing carriers — permutations and cyclic_permutations share the cycle reading, every set-partition class shares the block reading — not new collections. The one exception is singleton_species, the atom X itself: it has its own enumeration (one structure, at n=1 only) and so is a collection in its own right — the seed the other species expressions are built from.

Words, polytopes, symmetric ​

  • Words: words (over a b-letter alphabet), binary_words, gray_codes (a Hamiltonian reordering of the same 2ⁿ words), binary_palindromes, primitive_binary_strings (aperiodic — the Lyndon-word representatives, A027375), lyndon_words (the lex-least reps, A001037), independent_sets_cycle (no two cyclically-adjacent 1s — Lucas), binary_necklaces (up to rotation, A000031) and binary_bracelets (up to rotation + reflection=reversal, A000029) — realized by lex-least representatives, ascent_sequences. The run-avoidance strings: fib_strings (no "11" — Fibonacci F(n+2), the linear analogue of independent_sets_cycle), tri_strings (no "111" — tribonacci), and lucas_strings (circular no "11", wrap included — Lucas; differs from independent_sets_cycle only at n=1, where the C₁ self-loop excludes "1").
  • Polytopes (elements = faces): associahedron, permutahedron, cross_polytope, dissections.
  • Signed / type-B: signed_permutations, signed_subsets.

Not yet built (the visible gaps) ​

  • Prüfer sequences — a notation sibling borrowing the labeled_trees carrier, still to port. (labeled_forests and primitive_binary_strings are now done.)
  • Maps between collections (RSK, cycle-type, complement/reverse bijections) as first-class objects — some map data exists; a full morphism layer is future work.

Keeping the atlas whole ​

Adding a collection includes updating this atlas — it's the last step of the build checklist, not optional. Place the new collection in its family, note its counting sequence, and wire in any relationship (an order-iso sibling, a restriction parent, a duality, a shared count) — those relationships are the whole point of the map, and they're easy to lose. If it fills a gap listed above, move it out of "Not yet built". The atlas is only as useful as it is current.