# value of $k$ in binomial expression

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

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

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.

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

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