
In One Line and Anywhere. Permutations as Linear Orders. 73
PROOF As we have proved Theorem 2.17 by a bijection, this time we
present an inductive proof. Just as in the proof of Theorem 2.28, we first
treat the special case when K consists of a
1
copies of 1 and a
2
copies of 2
only, with a
1
+ a
2
= n. Denote this specific multiset by K
2
. In this special
case, the statement is obviously true for n = 1. Now let us assume that we
know the statement for all positive integers less than n, and prove it for n.
Now let us partition our permutations of K
2
according to the position of
the last 2. If the position of the last 2 is i, then we can be sure that there are