1
$\begingroup$

If $\displaystyle \binom{404}{4}-\binom{4}{1}\cdot \binom{303}{4}+\binom{4}{2}\cdot \binom{202}{4}-\binom{4}{3}\cdot \binom{101}{4}=(101)^k.$ Then $k$ is

Iam trying to simplify it

$\displaystyle \frac{(404)!}{4!\cdot (400)!} -4\cdot \frac{(303)!}{4!\cdot (299)!}+6\cdot \frac{(202)!}{(198)!\cdot 4!}-4\cdot \frac{(101)!}{4!\cdot (97)!}$

but i did not understand how do i find $(101)$ as a factor in that expression

may be some other way to calculate it

please Help me to solve it

$\endgroup$
1
$\begingroup$

Keep on simplifying: $$\displaystyle \frac{(404)!}{4!\cdot (400)!} -4\cdot \frac{(\color{red}{303})!}{4!\cdot (299)!}+6\cdot \frac{(202)!}{(198)!\cdot 4!}-4\cdot \frac{(101)!}{4!\cdot (97)!}=\\ \displaystyle \frac{404\cdot 403\cdot 402\cdot 401}{24} - \frac{303\cdot 302\cdot 301\cdot 300}{6}+\frac{202\cdot 201\cdot 200\cdot 199}{4}-\frac{101\cdot 100\cdot 99\cdot 98}{6}=\\ 101\cdot \left[ 403\cdot 67\cdot 401 - 302\cdot 301\cdot 150+201\cdot 100\cdot 199-50\cdot 33\cdot 98\right]=\\ 101\cdot [1030301 ]=101\cdot 101^3=101^4 \Rightarrow k=4.$$

$\endgroup$
1
$\begingroup$

I suppose that there is a typo. To me,it should be $$\displaystyle \binom{404}{4}-\binom{4}{1}\cdot \binom{303}{4}+\binom{4}{2}\cdot \binom{202}{\color{red}{4}}-\binom{4}{3}\cdot \binom{101}{4}=(101)^k$$ and thr result is a small number.

$\endgroup$
  • $\begingroup$ Was trying to identify the typo which kept me away from solving the problem :) $\endgroup$ – lab bhattacharjee Dec 7 '18 at 10:21
  • $\begingroup$ @labbhattacharjee. Even being almost blind, the $5$ was shocking to me ! Cheers :-) $\endgroup$ – Claude Leibovici Dec 7 '18 at 10:24
1
$\begingroup$

This is a particular case of the following formula $$ \tag{formula} \sum_{a=0}^{n-1} (-1)^{a} \binom{n}{a} \binom{(n-a) x}{n} = x^{n}, $$ which can be proved combinatorially by inclusion-exclusion.

Suppose you have $n$ boxes, labelled from $1$ to $n$, each containing the numbers $1, \dots, x$. RHS of (formula) represents the number of ways of extracting one element out of each box, that is, it is the number of finite sequences $a_{1}, \dots, a_{n}$, with $a_{i} \in \{ 1, \dots, x \}$. (Of course this is just the number of elements of the set $X^{n}$, where $X = \{1, 2, \dots, x\}$.)

Let us now obtain LHS of (formula), by counting in a different way.

Suppose you start by extracting $n$ objects from the boxes, but without the restriction to choose one object per box. You can do this in $$ \binom{n x}{n} = \binom{n}{0} \binom{n x}{n} $$ ways. You should, however, subtract the number of cases in which you have not taken any element from the first box, which accounts for $$ \binom{(n-1) x}{n} $$ possibilities. Do this for all the $n$ boxes, you get that you have to subtract $$ n \binom{(n-1) x}{n} = \binom{n}{1} \binom{(n-1) x}{n} $$ cases.

But by doing this, you have counted twice the cases where you did not take any elements from box $1$ and $2$, say. There are $$ \binom{(n-2) x}{n} $$ ways of doing this, and you have to do it for all $\dbinom{n}{2}$ pairs of distinct boxes, so you have to add back $$ \binom{n}{2} \binom{(n-2) x}{n} $$ cases. Arguing along like this, you get the (formula).

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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