7
$\begingroup$

To show it is true $r\times r!$ can be algebraically decomposed as $(r+1)!-r!$

But I am trying to think of a combinatorial proof. If $S$ is the set of all permutations of $\{1,2,\cdots ,n\}$ then I need a definition for the mutually non overlapping subsets $S_r$ whose union is $S$. So I will have $|S|=\sum|S_r|$. I am unable to think of such a decomposition.

1 Answers 1

8

Hint: We are splitting up into the permutations which do not fix $1$, (There are ($(n-1)\times (n-1)!$) of these), and the ones that do (everything else). To count the ones which fix $1$, we split into the $(n-2)\times(n-2)!$ permutations that do not fix $2$, and the left over number which do fix $2$. Continuing in this way we get your sum. (The one comes from the identity permutation)

  • 1
    Nice proof. One can also look at it as giving a combinatorial proof for the identity $n! - (n-1)! = (n-1) \times (n-1)!$.2011-08-01