0
$\begingroup$

I simplified the above problem to

Prove$$\sum_{k=1}^n\left(\sum_{i=0}^{n-k}\frac{(-1)^i}{(k-1)!\,i!}\right)=1$$

Here $p_n(k)$ denotes number of permutations of $\{1,2,\dots ,n\}$ such that we have k fixed points.

How to proceed?

$\endgroup$

marked as duplicate by Anvit, Community Jun 11 '18 at 5:59

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ That sounds like the reverse of simplification. $\endgroup$ – Lord Shark the Unknown Jun 11 '18 at 4:21
  • $\begingroup$ Should the inner sum go from $0$ to $k-1$? $\endgroup$ – Lord Shark the Unknown Jun 11 '18 at 4:40
5
$\begingroup$

There are exactly $n!$ permutations of $\{1, 2, \dots, n\}$, and the equation is just classifying each permutation with respect to number of fixed points.

$\endgroup$
  • $\begingroup$ Sorry I missed a $k$ in the equation in the title. Does your argument still hold with the $k$? $\endgroup$ – Anvit Jun 11 '18 at 5:46
1
$\begingroup$

Answer for the new question. We can adopt the indicator function technique:

Let $S_n$ be the set of permutations on $\{1,\cdots,n\}$. Then for each $\sigma\in S_n$, the number of fixed points of $\sigma$ can be written as $\sum_{i=1}^{n}\mathbf{1}_{\{\sigma(i)=i\}}$. So

$$\sum_{k=0}^{n}k p_n(k) =\sum_{\sigma\in S_n}\sum_{i=1}^{n}\mathbf{1}_{\{\sigma(i)=i\}} =\sum_{i=1}^{n}\sum_{\sigma\in S_n}\mathbf{1}_{\{\sigma(i)=i\}} =\sum_{i=1}^{n}(n-1)!=n!.$$

$\endgroup$
0
$\begingroup$

You have changed the problem in the edit.

You can rewrite $$\sum_{k=0}^n kp_k(n)$$ as $$\sum_{\sigma\in S_n}|\textrm{fix}(\sigma)|$$ where $\textrm{fix}(\sigma)$ is the set of fixed points of $\sigma$. By Burnside's lemma, this equals $n!M$ where $M$ is the number of orbits of $S_n$ on its natural action on $\{1,\ldots,n\}$. But $M=1$.

$\endgroup$
  • $\begingroup$ Is there any more elementary way? I Dont think I'll be allowed to use burnside's lemma without proving it $\endgroup$ – Anvit Jun 11 '18 at 5:47

Not the answer you're looking for? Browse other questions tagged or ask your own question.