0

Knowing that $a_{n,k}=\binom{n}{k}D_{k}$ ,where $D_{k}=\left |\left \{ \sigma \epsilon S_{n}:\sigma(i)\neq i, \forall i=1,...,n \right \} \right |$ and $a_{n,k}$=the number of permutations that move exactly k elements, how can I show that: $\sum_{k=0}^{n}\frac{D_{k}}{k!(n-k)!}=1$ ?

evinda
  • 7,823

1 Answers1

1

Updated Firstly, there appears to be a typo in the definition of $D_k$ which is more essential than I previously noted. Namely, I'll henceforth presume $a_{n,k}$ to be the number of permutations on $n$ elements which move exactly $k$ of them and fix the rest; one way of defining it would be $a_{n,k} = \binom{n}{k}D_k$ where $$D_k = \left|\left\lbrace \sigma\in S_n \colon \sigma(i)=i \iff k<i\leq n \right\rbrace\right|.$$

Taking this into account, let $A_{n,k}\subset S_n$ be the subset of permutations that move precisely $k$ elements. Then clearly:

  1. $A_{n,k}\cap A_{n,k^\prime}=\emptyset$ for all $k\neq k^\prime$

  2. $S_n = \bigsqcup_{k=0}^n A_{n,k}$;

  3. And by the question's terms we know $|A_{n,k}|=a_{n,k}$.

We therefore have that $$n! = |S_n| = \sum_{k=0}^n|A_{n,k}| = \sum_{k=0}^n a_{n,k}.$$ This implies that $$1 = \sum_{k=0}^n\frac{a_{n,k}}{n!} = \sum_{k=0}^n\frac{a_{n,k}}{k!(n-k)!\binom{n}{k}} = \sum_{k=0}^n\frac{a_{n,k}/\binom{n}{k}}{k!(n-k)!} = \sum_{k=0}^n\frac{D_k}{k!(n-k)!}$$

Jonathan Y.
  • 4,222
  • I haven't understood why $\sum_{k=0}^n a_{n,k} = |S_n| = n!$.Could you explain me why it happens? – evinda Dec 29 '13 at 17:48
  • 1
    @evinda the first equality is due to the fact that $a_{n,k}$ is the number of permutations fixing $k$ elements, and for every $\sigma\in S_n$ there exists a unique $k$ such that $\sigma$ fixes $k$ elements (i.e., every permutation gets counted, and counted exactly once). Please indicate if clarifications regarding the second equality (the order of the symmetric group) are required. – Jonathan Y. Dec 29 '13 at 17:56
  • I still haven't understood the first equation.Could you explain it to me with an example? – evinda Dec 29 '13 at 19:30
  • 1
    @evinda I made some corrections (namely, in the definition of $D_k$, which are necessary to make $a_{n,k}$ what you say it is), and added explanations. Please let me know if this clears things up. – Jonathan Y. Dec 30 '13 at 08:56
  • I understood it now.Thanks a lot..! – evinda Dec 30 '13 at 16:45