How a specification counts its root
A combinatorial specification is a system of equations, where every tiling's generating function appears exactly once on the left hand side of an equation, unless it is an atom, like the empty permutation or the point. This allows us to “pump” the specification for terms, in the sense that we start with the counts of the atoms and pass that information up to tilings that reference them, then those terms give us new information on other tilings, and so on until we finally reach the root.
The specification, counting
Loading the specification…
Every count, size by size
How counting works
A disjoint union adds
A step that asks a question, such as whether a cell is empty, puts each permutation of the tiling on exactly one branch. So the tiling's count is the sum of its branches' counts, at the same size:
\(c(n) = c_1(n) + c_2(n)\)
A factor shares the points
A step that factors a tiling into independent parts makes each permutation from one permutation of each part. With \(n\) points, the parts share them in every way:
\(c(n) = \displaystyle\sum_{n_1 + \cdots + n_k = n} c_1(n_1) \cdots c_k(n_k)\)
An equivalence copies
A step that only redraws a tiling, such as placing a point in a row and column of its own, or separating its rows and columns, keeps its permutations one for one, so it keeps the count:
\(c(n) = c_1(n)\)
A verified leaf is assumed known
The empty permutation has one permutation, of size 0, and a single point one, of size 1. A leaf verified as a known class, such as \(\operatorname{Av}(231)\) in one cell, brings its own counts, which comb_spec_searcher makes with a specification of its own.
Fusion needs a catalytic variable
A fusion draws two adjacent rows of a tiling as one row, or two columns as one column. A permutation of the fused tiling with \(K\) points in that row is \(K + 1\) permutations of the tiling, one for each place the line between the two rows can go. So the fused tiling is counted by its points in that row as well as by its size: a variable \(k\) counts them, and its counts, and those of the tilings it is made from, are polynomials in \(k\). The cells whose points \(k\) counts are shaded. In the tiling, \(k\) counts the points on one side of the line, and the \(K + 1\) places of the line give \(1, k, \ldots, k^K\):
\(c(n;\,k) = \displaystyle\sum_{K} [k^K]\, c_1(n;\,k)\,(1 + k + \cdots + k^K)\)
The variable is catalytic: it is needed only on the way. Where it was added, setting \(k = 1\) counts every permutation, whatever its points in those cells, so \(c(n) = c_1(n;\,1)\), the sum of the coefficients. A branch adds polynomials, and a factor multiplies them, since \(k\) then counts the points of every part.
A rule counted backwards
A specification may count a tiling with a rule used the other way round: the rule's parent is counted by a rule of its own, and this one, read backwards, counts one of its children from the parent. A disjoint union read backwards is a subtraction: the child's count is the parent's less the other branches', at the same size. A factor read backwards is a division: the product, at the size plus the other parts' least sizes, less the ways in which the child has fewer points, divided by the other parts' count at their least sizes. The arrow to the parent says counted from, and those to the others minus or divided by:
\(c_2(n) = c(n) - c_1(n)\) \(c_2(n) = c(n + 1) \,/\, c_{\bullet}(1)\)
Why it never runs in circles
A count at size \(n\) reads counts at size \(n\) only down branches, equivalences, fusions, steps that add a variable, subtractions, and factors whose other parts can be empty, and in these specifications those never lead back to the same tiling. Every way back passes through a factor whose other parts take at least one point between them, and so asks for fewer points. A division asks its product for more points, \(n + 1\) where a single point is divided out, and the specification counts that product first, from counts it has made. So each count reads only counts already made, and the terms come out one after another, as far as one likes.