**Claim:** for

.

**Proof:** We proceed by induction. For

this is clear since

and so

as claimed. Assume now that this is true for

and notice that

is partitioned into two blocks call the blocks

and

. Namely, those which fix

and those that don't. Identify now each

with it's associated

-tuple. Then,

is partitioned into the two blocks of the form

and

. Note that if

is of the second form with

and if

is the element of

which results from removing that

slot (the one containing

) then

. Thus, it's clear from this that

Noticing then that for each

we have that

is just a permutation of

with the extra condition that

always maps to

(and in particular it adds not inversions) we can see that

Thus,

and the induction is complete.