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.