ASHWANTH_K's blog

By ASHWANTH_K, history, 3 weeks ago, In English

I came across an equation, but I am not able to prove it. Can somebody help me proving this equation.


Problem Link

  • Vote: I like it
  • +22
  • Vote: I do not like it

»
3 weeks ago, # |
Rev. 2   Vote: I like it +69 Vote: I do not like it

$$$\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

»
3 weeks ago, # |
  Vote: I like it +44 Vote: I do not like it

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$$$.

Proof

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}$$$

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    where can i start if i'd like to learn proofs?

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Thanks all...