I've found this problem in a math competition:
Given two positive integers $a$, $b$, we define
$$ f(a,b)=\sum_{\displaystyle \sum_{i=1}^{a}x_i\leq b}\binom{b}{b-x_1}\binom{b-x_1}{b-x_1-x_2}\binom{b-x_1-x_2}{b-x_1-x_2-x_3}\cdots\binom{b-x_1-x_2-\cdots -x_{a-1}}{b-x_1-x_2-\cdots-x_a} $$
where $x_1$, $x_2$, $\dots$, $x_a$ are non-negative integers. Find the number of zeros at the end of
$$ f(2,2)\cdot f(3,3)\cdot \text{$\dots$}\cdot f(100,100) $$
The solution to this problem (or at least the last four digits of the asked number) is 1276.
I know that in this kind of problems you should find how many 2s and 5s there are in the prime factorization of the given expression.
In order to figure out how this function works, i've tried to calculate $f(2,2)$ and $f(3,3)$.
$$ f(2,2)=\sum_{\sum_{i=1}^{2}x_i\leq 2}\binom{2}{2-x_1}\binom{2-x_1}{2-x_1-x_2} $$
In the index of the summation we find $\displaystyle\sum_{i=1}^{2}x_i\leq 2$, so I considered:
$x_1=0$, $x_2=0$ $\longrightarrow$ $x_1+x_2=0\leq 2$
$x_1=0$, $x_2=1$ $\longrightarrow$ $x_1+x_2=1\leq 2$
$x_1=0$, $x_2=2$ $\longrightarrow$ $x_1+x_2=2\leq 2$
$x_1=1$, $x_2=1$ $\longrightarrow$ $x_1+x_2=2\leq 2$
Thus,
\begin{align*} f(2,2)&= \binom{2}{2-0}\binom{2-0}{2-0-0}+\binom{2}{2-0}\binom{2-0}{2-0-1}+\binom{2}{2-0}\binom{2-0}{2-0-2}+\binom{2}{2-1}\binom{2-1}{2-1-1}\\
&=1+2+1+2 \\
&= 6 \end{align*}
In the same way, $ f(3,3)$ should be $23$.
Then, I've tried to manipulate the product in the summation and I've found that
$$ f(a,b)=\sum_{\displaystyle\sum_{i=1}^{a}x_i\leq b}\dfrac{b!}{x_1!\cdot x_2!\cdot\text{$\dots$}\cdot x_a!\cdot (b-x_1-x_2-\dots-x_a)!} $$
I'm stuck at this point. Any help would be appreciated, thanks.
Best Answer
You are misinterpreting the problem. When asked to find the sum, say for example $2$, you have to count $(0, 1), (1, 0), (0, 2), (2, 0), (0, 0), (1, 1)$. It is nowhere given that the order of $x_i$ doesn't matter.
Now note that we only deal with $f(a, b)$ such that $a = b$, so I will not use $b$ now, will only use $a$.
You correctly simplified the expression $$\sum_{\displaystyle\sum_{i=1}^{a}x_i\leq a}\dfrac{a!}{x_1!\cdot x_2!\cdot\text{$\dots$}\cdot x_a!\cdot (a-x_1-x_2-\dots-x_a)!}$$
Now look at the denominator. Do you notice something?
It's just all the $a + 1$ sequences with sum $a$.
So, expression equals $$\sum_{x_1 + x_2 + \cdots + x_{a + 1} = a} \binom{a}{x_1, x_2, \cdots, x_{a + 1}}$$
Can you identify this as the multinomial coefficient?
The expression equals $$\sum_{x_1 + x_2 + \cdots + x_{a + 1} = a} \binom{a}{x_1, x_2, \cdots, x_{a + 1}} 1 ^ {x_1} 1 ^ {x_2}\cdots 1^{x_{a + 1}}$$
This equals $$(1 + 1 + \cdots + 1) ^ {a} = (a + 1) ^ a$$
So, we are required to find $$\prod_{x = 2}^{100}{(x + 1)^x}$$
The number of power of $2$ is greater than the number of power of $5$ in this expression, and since we are interested in $$\operatorname{min}(v_2, v_5)$$ we count the power of $5$.
We count with a method similar to Legendre's Formula.
First, count the power of $5$. This is $$4 + 9 + 14 + \cdots + 99 = 1030$$
Then, count the power of $25$. This is $$24 + 49 + 74 + 99 = 246$$
Total: $$246 + 1030 = 1276$$