Ranking and Unranking

There are 479 001 600 permutations of twelve things. You would not want the list. But "how many" and "which one is the hundred-millionth" are both perfectly reasonable questions, and neither needs the list to exist.

That is the whole idea here. A combinatorial family is not a sequence you generate and hold — it is a bijection with an interval of the integers. Fix an order, and the family becomes an indexed collection: rank takes an object to its position, unrank takes a position back to an object. Everything else follows.

@enumeratio/combinatorics/collections declares each family as a lazy indexed collection on compute-engine, so its own Count and At answer by arithmetic rather than by enumeration.

#Counted and indexed, not built

12! permutations, and the hundred-millionth of them. Neither call builds a list.

In$\mathrm{Count}(\mathrm{SymmetricGroup}(12))$Out$479\,001\,600$In$\mathrm{SymmetricGroup}(12)[100\,000\,000]$Out${\operatorname{Permutation}}([3, 7, 8, 9, 2, 4, 12, 5, 10, 6, 11, 1])$In$\mathrm{Subsets}(20)[700\,000]$Out$\operatorname{Finset}(\operatorname{Tuple}(20,\bigl\lbrack1, 4, 7, 9, 10, 12, 14, 16, 17, 19, 20\bigr\rbrack))$

source · editable

<notatio-cell value="Count(SymmetricGroup(12))" data-allow-mismatch="children" /> <notatio-cell value="SymmetricGroup(12)[100000000]" data-allow-mismatch="children" /> <notatio-cell value="Subsets(20)[700000]" data-allow-mismatch="children" />

At is 1-based: At(F, 1) is the first object and At(F, Count(F)) the last, and a negative index counts from the end. Past the count At is Missing rather than an error, so a slider can run past the end of a family without breaking anything.

Count is the combinatorics you already know

Ask a family how big it is and the classical numbers fall out — not as a lookup table, but because counting the family is what those numbers do.

#The counting sequences, recovered

Dyck paths are Catalan, set partitions are Bell, k-subsets are binomial. Each pair is the same number arrived at from two directions.

In$\mathrm{Count}(\mathrm{DyckPaths}(4))$Out$14$In$\mathrm{CatalanNumber}(4)$Out$14$In$\mathrm{Count}(\mathrm{SetPartitions}(4))$Out$15$In$\mathrm{BellNumber}(4)$Out$15$In$\mathrm{Count}(\mathrm{KSubsets}(5, 3))$Out$10$In$\binom{5}{3}$Out$10$

source · editable

<notatio-cell value="Count(DyckPaths(4))" data-allow-mismatch="children" /> <notatio-cell value="CatalanNumber(4)" data-allow-mismatch="children" /> <notatio-cell value="Count(SetPartitions(4))" data-allow-mismatch="children" /> <notatio-cell value="BellNumber(4)" data-allow-mismatch="children" /> <notatio-cell value="Count(KSubsets(5, 3))" data-allow-mismatch="children" /> <notatio-cell value="Binomial(5, 3)" data-allow-mismatch="children" />

This is a good way to check an implementation, and a better way to remember what a counting sequence counts. If Count(Derangements(5)) did not come back 44, one of the two would be wrong.

#Two more, for the habit

In$\mathrm{Count}(\mathrm{Derangements}(5))$Out$44$In$\mathrm{Count}(\mathrm{Involutions}(5))$Out$26$In$\mathrm{Count}(\mathrm{IntegerPartitions}(6))$Out$11$

source · editable

<notatio-cell value="Count(Derangements(5))" data-allow-mismatch="children" /> <notatio-cell value="Count(Involutions(5))" data-allow-mismatch="children" /> <notatio-cell value="Count(IntegerPartitions(6))" data-allow-mismatch="children" />

Walk a family with a slider

An index is a dial. Sweep it and you see the family in its order, one object at a time — which is the fastest way to learn what the order is.

#The 56 three-subsets of an eight-set

Press ▶ and watch the order: the last element climbs fastest. That is lexicographic order — subsets are compared by their smallest element first.

source · editable

<notatio-manipulate params="{ {r, 1}, 1, 56, 1}"> <graphics-box class="inline-figure" value='Show(CellDiagram(At(KSubsets(8, 3), _r)), ImageSize -> [Automatic, 46], GestureHandling -> "none")' legend-at="none" /> </notatio-manipulate>

The slider's value fills the _r wildcard, the expression is evaluated, and the glyph draws whatever came back. Nothing about that is specific to subsets — point it at a different family and the same rig walks that one.

#The same dial, two families

24 permutations of four things against 14 Dyck paths of semilength four. At does not wrap, so the paths take the index modulo their count themselves, Mod(_r - 1, 14) + 1, and start over while the permutations are still going.

source · editable

<notatio-manipulate params="{ {r, 1}, 1, 24, 1}"> <graphics-box class="inline-figure" value='Show(StrandDiagram(At(SymmetricGroup(4), _r)), ImageSize -> [Automatic, 72], GestureHandling -> "none")' legend-at="none" /> <graphics-box class="inline-figure" value='Show(PathDiagram(At(DyckPaths(4), Mod(_r - 1, 14) + 1)), ImageSize -> [Automatic, 86], GestureHandling -> "none")' legend-at="none" /> </notatio-manipulate>

Statistics over the index

Once an object is addressable, a statistic of it is an ordinary function call. The permutation statistics — inversions, descents, major index, cycles — compose with At directly, which makes "what does this statistic look like across the family" a question you can just ask.

#Statistics of the seventh permutation

The 7th permutation of four things is [2,1,3,4] — one inversion, one descent.

In$\mathrm{SymmetricGroup}(4)[7]$Out${\operatorname{Permutation}}([2, 1, 3, 4])$In$\mathrm{Inversions}(\mathrm{SymmetricGroup}(4)[7])$Out$1$In$\mathrm{Descents}(\mathrm{SymmetricGroup}(4)[7])$Out$1$

source · editable

<notatio-cell value="SymmetricGroup(4)[7]" data-allow-mismatch="children" /> <notatio-cell value="Inversions(SymmetricGroup(4)[7])" data-allow-mismatch="children" /> <notatio-cell value="Descents(SymmetricGroup(4)[7])" data-allow-mismatch="children" />

The order is part of the contract

A family and an order are not separable: change the order and At answers differently, so the order has to be stated. KSubsets is lexicographic — the 4th 3-subset of {1..5} is {1,3,4}, not {1,2,5}, because lex compares the smallest element first.

#Lex, from both ends

First and last.

In$\mathrm{KSubsets}(5, 3)[1]$Out$\operatorname{Finset}(\operatorname{Tuple}(5,\bigl\lbrack1, 2, 3\bigr\rbrack))$In$\mathrm{KSubsets}(5, 3)[10]$Out$\operatorname{Finset}(\operatorname{Tuple}(5,\bigl\lbrack3, 4, 5\bigr\rbrack))$

source · editable

<notatio-cell value="KSubsets(5, 3)[1]" data-allow-mismatch="children" /> <notatio-cell value="KSubsets(5, 3)[10]" data-allow-mismatch="children" />

Where this goes next

Unranking is the same operation as writing a number in a numeral system whose places are combinatorial rather than geometric — the factoradic digits of $n$ are the Lehmer code of the $n$-th permutation, and the combinatorial number system's digits are the $n$-th k-subset. Numeral systems makes that identification properly.

Every family here is catalogued, with its order and its counting sequence, in the symbol reference. The pictures are Shows of their frame layers and the slider is <Manipulate>.