I came across an equation, but I am not able to prove it. Can somebody help me proving this equation.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
I came across an equation, but I am not able to prove it. Can somebody help me proving this equation.
Название |
---|
$$$\sum_{x=1}^{n-k+1} \frac{(n-k)!}{(x-1)!(n-k-x+1)!} . (x-1)!(n-x)!$$$
$$$= (n-k)!(k-1)! \sum_{x=1}^{n-k+1} \frac{(n-x)!}{(k-1)!(n-x-(k-1)!}$$$
$$$= (n-k)!(k-1)! \sum_{x=1}^{n-k+1} \binom{n-x}{k-1}$$$
$$$\sum_{x=1}^{n-k+1} \binom{n-x}{k-1} = \binom{n-1}{k-1} + \binom{n-2}{k-1} + .... + \binom{k-1}{k-1} = \binom{n}{k}$$$ (Repeatedly using $$$\binom{n+1}{r} = \binom{n}{r-1} + \binom{n}{r}$$$ on last 2 elements)
$$$=> LHS = \binom{n}{k} . (n-k)!(k-1)! = \frac{n!}{k}$$$
Reminded me of my JEE days
It is always nice to find combinatorial proofs for such equations.
Here's my proof.
Suppose $$$S = \sum_{x=1}^{n-k+1} \binom{n-k}{x-1} \cdot (x-1)! \cdot (n-x)!$$$
$$$S$$$ denotes the number of permutations $$$p$$$ of $$$[1,2,3, \ldots n]$$$ such $$$pos(p, 1) < \min\limits_{i = n-k+2}^{n} pos(p, i)$$$, where $$$pos(p, e)$$$ denotes the index at which the element $$$e$$$ is present in $$$p$$$($$$p_{pos(p, e)}=e$$$).
In other words, $$$S$$$ denotes the number of permutations of $$$[1,2,3, \ldots n]$$$ in which the element $$$1$$$ is present before $$$n-k+2, n-k+3, \ldots n$$$.
Consider an empty array $$$b$$$. First choose an integer $$$x$$$ among $$$[1,2, \ldots n-k+1]$$$. Select $$$x-1$$$ elements from $$$[2, 3, \ldots n-k+1]$$$. We have $$$\binom{n-k}{x-1}$$$ ways to select them. First, we append these $$$x-1$$$ elements to $$$b$$$ in any arbitrary order. We have $$$(x-1)!$$$ ways to do that. Now append $$$1$$$ to $$$b$$$. $$$n - x$$$ elements are remaining. We can insert them in any order. So there are $$$(n-x)!$$$ ways to append them. Thus for some $$$x$$$, we can get $$$\binom{n-k}{x-1} \cdot (x-1)! \cdot (n-x)!$$$ distinct permutations $$$b$$$. So, the total number of distinct permutations that we can get is $$$\sum_{x=1}^{n-k+1} \binom{n-k}{x-1} \cdot (x-1)! \cdot (n-x)!$$$.
Now, let us look for an easy way to find $$$S$$$. Consider an empty set $$$X$$$. We will insert permutations of length $$$n$$$ into it. Let us traverse all the valid $$$S$$$ permutations. For each permutation $$$b$$$, we will first insert $$$b$$$ into $$$X$$$. For each $$$i$$$ from $$$n-k+2$$$ to $$$n$$$, let $$$c$$$ be the permutation if we swap $$$1$$$ and $$$i$$$ in original $$$b$$$. Insert $$$c$$$ into $$$X$$$. For each $$$b$$$, we will insert $$$k$$$ distinct permutations.
It is not hard to observe that $$$X$$$ will finally contain all the $$$n!$$$ distinct permutations, and no permutation would have been inserted more than once.
So we get $$$S \cdot k = n!$$$.
Thus $$$S = \frac{n!}{k}$$$
where can i start if i'd like to learn proofs?
Thanks all...