Permutation classes

Uniform random generation

A combinatorial specification counts its class, and the counts are all it takes to draw a permutation uniformly at random. Going down the specification, the draw takes each branch, and each way of splitting its points, in proportion to how many permutations lie that way. Watch one draw make its choices and build its permutation, then let thousands of draws gather into a heatmap of the class.

Permutations of length

One permutation, drawn at random

Loading the specification…

The heatmap

A cell's shade counts the permutations drawn so far whose value at that place is that value: the place from left to right, the value from bottom to top. The shading grows with the square root of the count, so that the rarer cells show.

How the sampler draws

First, the counts

Before its first draw, the sampler counts. For every tiling of the specification, it works out how many permutations the tiling has at every size a draw of length n can ask of it: a branch adds its children's counts, a split adds the product of its parts' counts over every way of sharing the points, and a leaf, a single point or the empty permutation, has its own. The root is asked for every size up to n, since the specification comes back to it; a tiling below a split is never asked for more points than the other parts leave, so the deepest tilings are counted a few sizes short of n. The counts are worked out once, and every draw then uses them. Count does just this, in your browser.

At a branch

A step that asks a question, such as whether a cell is empty, splits the permutations of a tiling into those on each branch. With n points to place, the draw takes a branch with probability

c_branch(n) / c_tiling(n)

where c counts the permutations of a tiling with n points. Every count comes from the specification itself.

At a split

A step that splits a tiling into independent parts makes each permutation from one permutation of each part. The draw chooses how many points each part gets, n₁ + … + n_k = n, with probability

c₁(n₁) ⋯ c_k(n_k) / c_tiling(n)

and then draws each part on its own. A step that only rearranges the tiling, such as placing a point in a row and column of its own, leaves nothing to choose.

Why it is uniform

Every count in these fractions but one cancels against another: what a tiling passes down to its parts, they divide among their own. Multiplied over the whole draw, the probabilities leave one over the class's count. So each permutation of length n comes out with the same probability, 1 over c(n), and the heatmap shows a typical permutation of the class.