Eleven assortments and four that are empty

Before any search over relabellings, and before any matrix, there is one number per link that costs nothing: how many pins it carries. Two, three, four. The multiset of those is the link assortment, and it is where every published census table is organised.

It is the coarsest invariant in the subject and the first thing anybody applies. Two chains with different assortments are certainly different chains, and no search is needed to know it. What this rung is about is how much of the answer the assortment carries, and — more interestingly — what it gets wrong.

Where the eleven come from #

Two lines of arithmetic.

A planar chain of one degree of freedom has $j = (3n-4)/2$ pins — which is Grübler’s rule rearranged — so ten links have thirteen. Each pin touches two links, so the degrees sum to twenty-six. And no link may carry fewer than two pins.

So the question is: in how many ways can twenty-six be written as a sum of ten integers, each at least two? Written in non-increasing order the answer is eleven, and they run from four links of degree three and six of degree two, through the mixed cases, to the extreme one where a single link carries eight pins and the other nine carry two each.

At four links there is one assortment and it is forced: four links of degree two. At six there are two, and only one of them contains anything. At eight there are five and at ten eleven, so the number of assortments grows far more slowly than the number of chains — which is the first sign that the assortment is a weak invariant.

Four rows with nothing in them #

Seven of the eleven contain at least one mechanism. Four contain none.

The four are the ones requiring a link with six, seven or eight pins: two ternary links and one senary; one quaternary and one senary; one ternary and one septenary; and one link with all eight of its possible neighbours. Between them the census reaches seventy-eight graphs with those degrees.

Every one of the seventy-eight is connected. Every one is simple. Every one gives each link at least two pins. Every one has a Grübler count of exactly one. And every one contains a subchain that is already a structure, so none of them is a ten-link mechanism.

That is a statement about all seventy-eight rather than about any of them, and no arithmetic could have produced it. The assortment arithmetic never looks at where a pin goes, and where the pins go is the whole of the question.

Why a crowded link drags a structure in #

The reason is not deep and it is worth stating, because it explains why the empty rows are the ones they are rather than being scattered.

A link carrying six pins in a ten-link chain is pinned to six of the other nine. Those six links have to go somewhere, and there are only thirteen pins in the whole chain — six of them are already spoken for, leaving seven to connect nine links into one piece with none below degree two.

That is very tight. Every one of the six neighbours needs at least one further pin, which uses six of the remaining seven, and the three links not touching the crowded one need two pins each. The arithmetic just barely closes, and it closes only in configurations where some small set of links ends up with more pins between them than a mechanism can afford — which is exactly the definition of a structure.

Push further and it becomes obvious. The last of the eleven assortments has one link pinned to all nine others and nine binary links; the nine need eighteen pin-ends between them and have already used nine, so the remaining four pins have to give eight ends to nine links, which is impossible without something doubling up. That row contains exactly one graph and it is a structure.

The four empty rows, one at a time #

They are worth taking individually, because the reason each is empty is slightly different and the last one is a proof rather than an enumeration.

Seven binary links, two ternary and one senary — a link with six pins. Fifty-four graphs, none a chain. The senary link’s six neighbours use six of the thirteen pins; the two ternary links need three each; and the arithmetic leaves so little slack that some subset always closes on itself.

Eight binary links, one quaternary and one senary. Fifteen graphs, none a chain. Same argument with the ternaries replaced by a single link carrying four pins, which concentrates the problem further.

Eight binary links, one ternary and one septenary — a link pinned to seven of the other nine. Eight graphs, none a chain.

Nine binary links and one octonary — a link pinned to all nine others. One graph, and it is not a chain.

The last case can be settled without enumerating anything. If one link is pinned to all nine others, those nine pins are used, and four remain. The nine binary links each need one further pin, which is nine pin-ends from four pins — and four pins supply eight ends. One link is left short, so it carries only one pin, and a link with one pin is excluded. The single graph the search finds is the one where the arithmetic is patched by giving some link a pin it should not have, and it contains a structure as a result.

That is the shape of all four: the arithmetic balances the totals and the adjacency cannot balance the distribution, and the gap grows with how crowded the crowded link is.

Counting pin-ends, which settles a row without a search #

The octonary row was disposed of without enumerating anything, and the argument that did it generalises far enough to be worth writing down as a method rather than left as a remark about one case.

The accounting is in pin-ends rather than in pins. A chain of ten links has thirteen pins and therefore twenty-six pin-ends, distributed as the assortment says. Now suppose one link is a hub of degree $d$. It consumes $d$ ends and it occupies one end on each of $d$ other links. Every link, hub or not, needs at least two ends. So the links that are not the hub need at least $2(n-1)$ ends between them, of which $d$ are already supplied by their pins to the hub, and the remainder has to come from pins joining them to one another — which costs two ends each and therefore has to be even and has to fit inside what is left.

Run that on the octonary. The hub takes eight ends and supplies one to each of the other nine links, which is nine ends, so seventeen of the twenty-six are spent. Nine ends remain and the nine outer links need at least one more each, which is nine ends — but those nine ends must come in pairs, because a pin joining two outer links contributes two of them. Nine is odd. The row is empty, and no graph was ever built.

That is a parity argument, and parity arguments are the cheapest kind there is. It costs a handful of additions, it settles a whole row of the table, and it needs nothing about how the links might be wired — which is precisely the property that makes it usable before a search rather than after one.

The honest limit is that it settled one of the four rows and not the other three. Those needed the enumeration: fifteen graphs here, sixty-odd there, every one of them built and every one of them rejected by the subset scan for containing a structure. So the method is a filter that fires sometimes rather than a replacement for the search, and the four empty rows are empty for two different reasons — one arithmetic and three structural.

Knowing which is which matters more than it might seem. An arithmetically impossible row is impossible at every link count where the same parity works out the same way, so the argument transfers upward with no new computation. A structurally empty row is empty because of how adjacency behaves at this size, and nothing about it transfers — a row that is empty at ten links may perfectly well be populated at fifteen. The table’s four zeros therefore have different futures, and only the enumeration can say which zero is which.

What the assortment does carry #

Having established that it is weak, it is worth being fair about what it is good for, because it is used constantly and mostly correctly.

It is a complete invariant in one direction. Different assortments prove different chains, always, in the way a difference in a characteristic polynomial does, with no exceptions and no cost. As a first filter in a pairwise comparison it eliminates most pairs immediately.

It organises a census into readable groups. Nine of the sixteen eight-link chains have four ternary links; five have two ternaries and a quaternary; two have a pair of quaternaries. That is how a person holds sixteen objects in mind, and it is how every table in the literature is laid out.

And it says something physical. A binary link is a bar; a ternary link is a plate with three bearings — and every bearing is a hole with a tolerance on it; a quaternary link is a plate with four. The assortment is therefore a rough statement about what the mechanism is made of — how many simple bars, how many machined plates — which is a manufacturing fact rather than a kinematic one and is the reason a designer cares about it directly.

And where it fails #

Two failures, and they are of different kinds.

Same assortment, different chains. Watt’s chain and Stephenson’s are the smallest example: four binary links and two ternary, both of them, and two different mechanisms. At eight links the largest assortment holds nine distinct chains, so the assortment separates them into groups of nine, five and two rather than into sixteen.

Different assortment, same everything else. The more surprising failure is at ten links, where one of the two cospectral pairs consists of a chain with two ternary and two quaternary links and a chain with six ternary links. Those two have different assortments and identical characteristic polynomials — so on that pair the cheap invariant works and the expensive one does not, which is the reverse of what anybody would predict.

Neither failure is a reason to stop using it. They are reasons to know which question it answers: are these certainly different? — which it answers well — rather than are these the same?, which it cannot answer at all.

The distribution is not flat #

One more thing the census makes visible and a table of assortments does not.

The seven non-empty ten-link assortments hold 95, 57, 50, 15, 8, 3 and 2 chains. So more than 60 per cent of the census lives in two rows, and the two smallest rows hold five chains between them.

That skew has a consequence for anybody using the census as a design space. A requirement stated as at least one quaternary link keeps 163 of the 230; a requirement stated as no link above degree three keeps 50, all of them in a single row. Neither is a small restriction and neither is obvious from the assortment table, because the table’s rows are not the same size.

The same skew explains why the graphs that pass the count outnumber the chains so heavily in some rows and not others: the assortment with six ternary links yields 198 graphs and 50 chains, roughly four to one, while the one with three quaternary links yields 47 and 3, roughly sixteen to one. A crowded link makes structures easy, so the crowded rows are where the count is worst.

What a designer reads off it #

The assortment is the one thing in this field a working engineer already thinks in, so it is worth saying what the census adds to the way it is normally used.

The normal use is as a specification. A mechanism with many binary links is cheap: bars with two bearings, easy to make, easy to adjust, and a length is then a range rather than a number. A mechanism with quaternary links has plates with four bearings whose relative positions all matter, which is expensive and is where the accuracy goes. So how many plates is a real design variable and the assortment is exactly it.

What the census adds is the cost of each specification in variety. Asking for no link above degree three at ten links leaves 50 chains — a fifth of the census, all in one row. Asking for at least one quaternary leaves 163. Asking for a senary link leaves nothing at all, which is not a restriction but an impossibility, and it is the kind of answer only an enumeration gives.

There is a second thing worth reading off. The assortment bounds the loop structure, because a link of degree $d$ sits on at least $d-1$ independent loops’ worth of the graph. A chain with three quaternary links is far more heavily interconnected than one with six ternary links, even though both have thirteen pins, and that shows up in the shortest loop basis and therefore in the smallest stack-up any tolerance analysis can have.

What the arithmetic is for #

The right way to hold all of this is that the assortment arithmetic is a necessary condition stated in advance, and that its value is in what it excludes before any graph is built.

Eleven assortments at ten links means the search runs eleven times, each with a fixed degree sequence, and a fixed degree sequence is what makes the pruning rule work at all — the rule compares links of equal degree, and there are no equal degrees to compare until the sequence is chosen.

So the assortment is not merely a way of presenting the answer. It is the first step of the computation, it is the reason the computation finishes, and its four empty rows are a result the computation produces rather than an input it was given.

The row that is not there #

One last observation, and it is about the shape of the table rather than about any row in it.

There is no assortment at ten links with two links of degree five and nothing above two otherwise — there is, and it holds two chains — but there is no assortment anywhere in the table with a link of degree nine, because a link cannot be pinned to itself and nine is the most a ten-link chain allows. The table runs out at eight for that reason, and it runs out of mechanisms at five.

So the effective statement, which is much stronger than the table’s eleven rows suggest, is: a ten-link mechanism of one degree of freedom has no link carrying more than five pins. That is not something anybody put into the search. It is a consequence of the fourth condition, established by exhausting the seventy-eight graphs the arithmetic allowed and finding that all of them fail.

It is worth carrying because it is the kind of rule a designer could use directly and could not have derived. A plate with six bearings in a ten-link linkage is not merely unusual; it cannot occur, and the reason has nothing to do with manufacturing.

The same accounting run in reverse is worth a line, because it explains why the populous rows are populous. An assortment made entirely of binary links with a couple of ternaries leaves most of its pin-ends free to be arranged, so the number of ways of arranging them is large and the row fills up. An assortment concentrating ends on one link spends most of its budget before any choice is made, and what remains is too tightly constrained to admit much. The skew in the census — 95 chains in the largest row and 2 in the smallest — is that budget argument showing up as a distribution, and it is the same argument that empties the last four rows entirely, run one step further.