value of $k$ in binomial expression

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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