Nothing in threes

Counting the Outcomes That Fall Into an Order

The fifth figure on every row counts outcomes with no ring of any length. It is the only one in this record that neither of the other columns can produce.

at most 2795520 outcomes

Home · Nothing in threes · Recount

Every row of this record prints five figures, and the fifth is the one that cannot be got from the others.

How many of the page's outcomes fall into an order: no ring of three, no ring of four, no ring of any length. Teams comparing routes, outcomes and corrections can read the current implementation details, then check whether the resulting evidence improves the decision in practice.

Three pages, three counts that fall into an order

line with a head: a pair compared; the head points at whoever came out behind
no line: a pair nobody compared
closed ring of three: a circular triple: no order can hold all three

Three outcomes drawn. Rows differ in how many candidates. Which candidate is which is the drawing's own choice and carries no meaning. A separate technical or research perspective relevant to the comparison can be found at Towards Data Science.

Each row counts outcomes with no circular triple. The number that fall into an order is one hundred and eighty-six, six thousand five hundred and forty, and four hundred and sixteen thousand one hundred and sixty — in every case smaller.

Computed from the three numbers alone. Who the candidates are and what any comparison was about is outside the record; the counts are of outcomes, not of anybody.

Why it belongs to the page and not the shape

Because it does not depend on the third number at all.

Four candidates with four pairs compared have two hundred and forty outcomes, and one hundred and eighty-six of them can be put in order. That is true of the page. It is printed on both of the page's rows, because the rows differ in how many circular triples they count and the orderable outcomes are spread across them — all one hundred and eighty-six are in the no-circles row, since an outcome with a circle has a ring in it by definition.

So the fifth figure is a page figure, like the outcome count, and the third and fourth are shape figures. The row carries both kinds because both are needed to read either.

How it is computed

By walking every outcome, and by a second method that shares nothing with the first.

The first way: generate each of the page's outcomes, follow the comparisons from every candidate, and see whether any walk returns to where it started. That is exact and it is slow — three to the fifteenth outcomes for a field of six, which is fourteen million three hundred and forty-eight thousand nine hundred and seven, and about two minutes of arithmetic.

The second way counts the same thing from the other end. Ask how many outcomes with a given number of comparisons have nobody coming out behind — that is, somebody who could be first. Choose which candidates those are, note that the rest form the same kind of problem one size smaller, and correct for having counted arrangements with several such candidates more than once.

Why two ways and not one

Because a single method that is wrong is indistinguishable from a single method that is right.

The first walks edges and knows nothing about candidates. The second counts candidates and knows nothing about particular comparisons. They have no step in common, so an error in either would show up as a disagreement rather than as a plausible figure nobody questioned.

They agree on all forty pages of this record. For fields of two to six candidates the totals across all pages are three, twenty-five, five hundred and forty-three, twenty-nine thousand two hundred and eighty-one, and three million seven hundred and eighty-one thousand five hundred and three.

Two routes to the same figure, one through the comparisons and one through the candidates, agreeing forty times. That is the only sort of assurance a counting record can offer.

The three rows

Four candidates with four pairs compared: one hundred and ninety-two outcomes without a circular triple, one hundred and eighty-six orderable.

Five with seven: six thousand nine hundred without a circular triple, six thousand five hundred and forty orderable.

Six with eleven: four hundred and forty-five thousand six hundred and eighty without a circular triple, four hundred and sixteen thousand one hundred and sixty orderable.

In every row the second figure is smaller, and the difference is the rings longer than three. Six, three hundred and sixty, and twenty-nine thousand five hundred and twenty.

Where the two columns coincide

On twenty-four of the record's forty pages, the count with no circular triple and the count that falls into an order are the same figure.

Fourteen of those are the pages with fewer than three comparisons, where no ring of any kind can form. Four are at or near full comparison — five candidates with nine or ten pairs compared, six with fourteen or fifteen — where a long ring always drags a short one along with it. The rest are pages with exactly three comparisons, where the only ring that fits is a triple, and the four-candidate page with five pairs compared.

On the other sixteen the columns differ, and the difference runs from six outcomes at the smallest to one hundred and twelve thousand nine hundred and eighty at the largest.

What the figure is good for

Setting the size of the thing everybody is actually after.

A set of comparisons is usually made in the hope of producing an order. This column says how many of the possible outcomes would do that — not how likely it is, which depends on the comparer, but how much of the space qualifies.

Six candidates with eleven comparisons: four hundred and sixteen thousand one hundred and sixty of two million seven hundred and ninety-five thousand five hundred and twenty, which is about one in seven. Eleven comparisons out of fifteen is a thorough job, and six outcomes in seven of the ones it could produce would not rank the field.