XVIII-th Macedonian mathematical Olympiad

We define a function $f$ on the $m$-tuples $(n_1,n_2,...,n_m)$ in the following way: $f(n_1,n_2,...,n_m)=0$ for the $m$-tuples for which it does not hold that: $$n_1\ge n_2\ge \cdots \ge n_m\ge 0.\text{\hspace{1em}(1)}$$ If $n_1\ge n_2\ge \cdots \ge n_m\ge 0$, then it holds that $$f(n_1,n_2,\dots ,n_m,0)=f(n_1,n_2,\dots ,n_m).(2)$$ $$f(n_1,n_2,\dots ,n_m)=f(n_1-1,n_2,\dots ,n_m)+f(n_1,n_2-1,\dots ,n_m)+\cdots +f(n_1,n_2,\dots ,n_m-1).(3)$$ $$f(n)=1,\text{ for }n\ge 0.(4)$$ The function $f$ is well-defined. We will show that $f(n_1,n_2,\dots ,n_m)$ is the number of grids of type $(n_1,n_2,\dots ,n_m)$. It is clear that conditions (1) and (4) must be fulfilled for the required grid (a row of $n$ squares can be filled in a unique way with $n$ numbers such that they form an increasing sequence $:1,2,3,\dots ,n$). Condition (2) is also clear. To show that a grid of type $(n_1,n_2,\dots ,n_m)$ satisfies condition (3), we consider the number $n$. That number has to be the last number in one of the rows, so if we delete the square having number $n$, we get a grid with $n-1$ numbers that fulfills the conditions of the problem. It can happen that several rows may have the same number of squares so that the number $n$ can be in the last row in the rightmost square. If, for example, $n_1=n_2$, then $f(n_1-1,n_2,\dots ,n_m)=0$ since $n_1-1<n_2$. Therefore in condition (3) all expressions $$f(n_1-1,n_2,\dots ,n_m),f(n_1,n_2-1,\dots ,n_m),\dots ,f(n_1,n_2,\dots ,n_m-1)$$ appear, which are zero if the above condition holds. We use the previously-defined function $f$ to get the number of grids of type $(4,3,2)$. $$ $$\begin{array}{rl}f(4,3,2)& =f(3,3,2)+f(4,2,2)+f(4,3,1)=\\ & =(f(3,2,2)+f(3,3,1))+(f(3,2,2)+f(4,2,1))+(f(3,3,1)+f(4,2,1)+f(4,3,0))=\\ & =2f(3,2,2)+2f(3,3,1)+2f(4,2,1)+f(4,3)=\\ & =2(f(2,2,2)+f(3,2,1))+2(f(3,2,1)+f(3,3,0))+2(f(3,2,1)+f(4,1,1)+f(4,2,0))+(f(3,3)+f(4,2))=\\ & =2f(2,2,2)+6f(3,2,1)+2f(4,1,1)+3f(4,2)+3f(3,3)=\\ & =2(f(2,2,1))+6(f(2,2,1)+f(3,1,1)+f(3,2,0))+2(f(3,1,1)+f(4,1,0))+3(f(3,2)+f(4,1))+3(f(3,2))=\\ & =8f(2,2,1)+8f(3,1,1)+12f(3,2)+5f(4,1)=\\ & =8(f(2,1,1)+f(2,2,0))+8(f(2,1,1)+f(3,1,0))+12(f(2,2)+f(3,1))+5(f(3,1)+f(4,0))=\\ & =16f(2,1,1)+20f(2,2)+25f(3,1)+5f(4)=\\ & =16(f(1,1,1)+f(2,1,0))+20(f(2,1))+25(f(2,1)+f(3,0))+5=\\ & =16f(1,1,1)+61f(2,1)+25f(3)+5=16(f(1,1,0))+61(f(1,1)+f(2,0))+25+5=\\ & =77f(1,1)+61f(2)+30=77(f(1,0))+61+30=77f(1)+91=77+91=168.\end{array}$$