Combinatorial classes and bijections

A graded combinatorial class is a collection split into size layers $\mathcal A_n$, with finitely many objects in each layer. Size might mean the length of a word, the number of vertices of a tree, or the total weight of an integer partition. These are different statistics, so stating the size rule is essential. A class can be infinite overall while each counting problem remains finite. If infinitely many distinct zero-size decorations are allowed, however, even the zero layer is infinite and the ordinary counting setup breaks down.

An empty object often contributes one, rather than zero, to a count. There is exactly one empty binary word and exactly one way to choose no items. This convention makes product decompositions work at their boundaries. It does not require every class to contain an empty object: a class of nonempty words deliberately excludes one. Before writing a formula, specify whether labels matter, whether order matters, whether repetitions are allowed, and whether two drawings that differ only by rotation represent the same object.

To count subsets of a set of numbered sockets, encode membership by a binary word: write one at exactly the occupied positions. The inverse sends a word to the set of positions carrying one. Checking these two procedures undo one another proves injectivity and surjectivity together. Merely writing down a plausible encoding is not enough. If two different objects produce the same code, information has been lost; if some proposed codes cannot occur, counting the full code space overcounts the objects.

A bijection can preserve a statistic as well as total size. Membership words preserve subset cardinality as the number of ones, so a fixed-cardinality count becomes a fixed-weight word count. Such a refinement explains an entire family of identities at once. A map that forgets order is usually many-to-one instead. Dividing by the number of orderings is justified only when every fiber has that same size; repeated entries or internal symmetries can make fiber sizes vary. The inverse test reveals exactly where an attempted shortcut fails.

A disjoint alternative adds counts; an ordered pair of independent structural choices multiplies them. Here independent means that every allowed choice from the first set can be combined with every allowed choice from the second, not probabilistic independence. If a rule couples the choices, count compatible pairs instead. When total size is additive, split by the size of the first component before multiplying. This produces a convolution, because each total-size object belongs to exactly one size split.

For example, a word with one distinguished divider is equivalent to an ordered pair of words, obtained by cutting immediately before and after the divider. A word without a marked divider is different: several cuts may yield the same underlying word. Keeping the divider as part of the object restores unique decoding. This small example captures a general habit: whenever a product formula seems natural, identify the cut, mark, or canonical feature that lets a reader reconstruct its components uniquely.