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 2 essays across one field — 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

Named alongside it

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

GroupParityPermutationBijectionBipartite graphCounting argumentDeterminantExhaustive searchInvariantSignState spaceSymmetry

All concepts