than horizontally, to take up less space. Here is our permutation:
abcdef ghi j
We start with the letter a, and play the following game. The letter
a gets mapped to the letter b, w hich in turn gets mapped to the
letter e, which in turn gets mapped to the letter h,whichinturn
gets mapped to the letter f , which in turn gets mapped to the letter
d, which in turn gets mapped to the letter i, which in turn gets
mapped to the letter j, which in turn gets mapped to the letter g,
whichinturngetsmappedtotheletterc, which in turn gets
mapped to the letter a. If you think about it for a moment, you
will realize that we had to come back to a eventually.
EXERCISE: Convince yourself that we had to return to the
letter a eventually.
SOLUTION: Because there are only 10 letters involved, the
ﬁrst thing to notice is that some letter has to show up on the
list twice if we play the game long enough. Call the ﬁrst letter
to show up twice x, and suppose that x is not the letter a.We
get a picture like this one:
a → b →···→y → x →···→z → x.Becausethe
permutation is one-to-one, we are forced to conclude that
the letter before each of the two x’s is the same as well,
contradicting the assumption that x is the ﬁrst letter to show
up twice. The only way out is if a is the ﬁrst letter to appear
Put the whole list, starting with a, on one long line:
a → b → e → h → f → d → i → j → g → c → a.
This is called a cycle, and it is customary (though confusing at ﬁrst)
to write it as (abehfdijgc). Notice that we omit the second a.