Matpic
mathematics, in pictures
Concept

Transposition

A permutation that exchanges two things and leaves everything else where it was. Every permutation is a product of transpositions, and whether the number needed is even or odd is always the same for a given permutation — its sign.

Named by 4 essays across 2 fields — each of them below, with the objects they name alongside it.

The permutation (1 3 4 2) drawn as 4 strings, crossing 3 times. A permutation drawn as strings running from a row of numbered pegs to another, with every place two strings cross marked, and the crossing count checked against the number of pairs that are out of order.

The crossings that will not come out even

Draw a rearrangement as strings from one row of pegs to another and count where they cross. The count depends on how the strings are drawn; whether it is odd or even does not, and that single bit is what makes determinants exist and a sliding puzzle unsolvable.

algebra · Permutation parity Which arrangements sliding tokens reach, on nine graphs, against Wilson's theorem. A table of 9 small graphs drawn as icons, each with the searched count of reachable token arrangements and the fraction of all arrangements it is: a six-cycle 5/120; K₂,₃ 12/24; the 2×3 tray 60/120; a house 24/24; a six-cycle with one chord 120/120; a wheel of six 120/120; θ, inner paths 2, 2, 2 2520/5040; θ₀, inner paths 1, 2, 2 120/720; θ, inner paths 1, 3, 3 20160/40320.

Which graphs let the tokens go anywhere

A sliding puzzle is a graph with a token on every vertex but one. Richard Wilson found in 1974 what every such puzzle can reach, and the answer has a surprise in it — the half the tray is stuck with is not a fact about permutations at all, but about the board being two-coloured — and one exception, a graph of seven vertices that reaches exactly 120 of 720.

algebra · Permutation parity The far end of a sliding tray falls as holes are added. Exhaustive search of the 2×3, 2×4 and 3×3 sliding trays with one to all-but-one holes. Far ends for the 3×3 tray: 31, 24, 21, 17, 13, 10, 7, 4; averages 21.97, 16.04, 12.70, 9.99, 7.88, 5.92, 3.75, 2.00.

A second empty square

With one empty square a sliding tray can reach exactly half its arrangements, and the half it misses is guarded by a sign. Leave a second square empty and the guard disappears — every arrangement is reachable, two tiles can be exchanged in four moves, and the far end of the three-by-three tray comes in from thirty-one moves to twenty-four. Searching every tray with every number of holes shows what each extra square of room is worth.

algebra · Permutation parity One swap splits the long cycle. A shuffle of 100 boxes whose longest cycle has 61 boxes, drawn as a ring; swapping the contents of two boxes 30 steps apart splits it into cycles of 30 and 31, so every cycle has at most 50 and all prisoners succeed.

One swap saves every prisoner

A hundred prisoners following the cycles of a shuffle all survive about 31% of the time. Let a helper look into the room first and swap the contents of two boxes, and they survive every time. With fewer boxes each, more swaps are needed — exactly one per cut a long cycle needs — and the number of swaps a random room demands has an exact distribution.

probability · Inclusion exclusion

Named alongside it

The objects these essays reach for when they reach for this one.

PermutationExhaustive searchParityGroupInvariantSignState spaceBijectionBipartite graphCounting argumentCycle decompositionDeterminant

All concepts