5. We define a "table" of type $\left(n_{1}, n_{2}, \ldots, n_{m}\right), n_{1} \geq n_{2} \geq \ldots \geq n_{m}$ as follows: We place $n_{1}$ squares horizontally next to each other, then we place $n_{2}$ squares horizontally next to each other below the $n_{1}$ squares starting from the first square on the left. We continue this process until we get a "table" with $n_{1}$ squares in the first row, $n_{2}$ squares in the second row, $\ldots, n_{m}$ squares in the $m$-th row, with a total of $n=n_{1}+n_{2}+\ldots+n_{m}$ squares. The rows of placed squares always start from the square below the leftmost square of the first row (see example). We fill the obtained "table" with numbers from 1 to n such that in each row and each column, the numbers from left to right and from top to bottom, respectively, are in increasing order. Below is an example of a table of type $(5,4,2,1)$ and one of its fillings.

| 1 | 3 | 4 | 7 | 11 |
| :---: | :---: | :---: | :---: | :---: |
| 2 | 5 | 10 | 12 |  |
| 6 | 9 |  |  |  |
| 8 |  |  |  |  |
|  |  |  |  |  |

Determine the number of fillings of a "table" of type $(4,3,2)$.
Solution. We define a function $f$ on $m$-tuples $\left(n_{1}, n_{2}, \ldots, n_{m}\right)$ as follows:

$f\left(n_{1}, n_{2}, \ldots, n_{m}\right)=0$ for $m$-tuples for which $n_{1} \geq n_{2} \geq \ldots \geq n_{m} \geq 0$ does not hold.

If $n_{1} \geq n_{2} \geq \ldots \geq n_{m} \geq 0$ holds, then

$$
\begin{gathered}
f\left(n_{1}, n_{2}, \ldots, n_{m}, 0\right)=f\left(n_{1}, n_{2}, \ldots, n_{m}\right) \\
f\left(n_{1}, n_{2}, \ldots, n_{m}\right)=f\left(n_{1}-1, n_{2}, \ldots, n_{m}\right)+f\left(n_{1}, n_{2}-1, n_{3}, \ldots, n_{m}\right)+ \\
+\ldots+f\left(n_{1}, n_{2}, \ldots, n_{m-1}, n_{m}-1\right) \\
f(n)=1, \text { for } n \geq 0
\end{gathered}
$$

Clearly, the function $f$ is well-defined. We will prove that the number of fillings of a "table" of type $\left(n_{1}, n_{2}, \ldots, n_{m}\right)$ is $f\left(n_{1}, n_{2}, \ldots, n_{m}\right)$. Clearly, if $n_{1} \geq n_{2} \geq \ldots \geq n_{m} \geq 0$ does not hold, then there is no filling of the "table" and therefore $f\left(n_{1}, n_{2}, \ldots, n_{m}\right)=0$, i.e., (1) holds, and since in a row of $n$ squares the numbers from 1 to $n$ in increasing order can be written in a unique way, (4) must hold. Furthermore, it is obvious that the number of fillings of a "table" of type $\left(n_{1}, n_{2}, \ldots, n_{m}, 0\right)$ is equal to the number of fillings of a "table" of type $\left(n_{1}, n_{2}, \ldots, n_{m}\right)$, so (2) holds. To show that for the number of fillings of a table of type $\left(n_{1}, n_{2}, \ldots, n_{m}\right)$ condition (3) holds, we consider the number $n$. This number must be the last in some row, and if we remove the square with the number $n$, we get a filling with $n-1$ numbers of a "table" of one of the following types

$$
\left(n_{1}-1, n_{2}, \ldots, n_{m}\right),\left(n_{1}, n_{2}-1, n_{3}, \ldots, n_{m}\right), \ldots,\left(n_{1}, n_{2}, \ldots, n_{m-1}, n_{m}-1\right)
$$

Clearly, from each filling of a "table" of type (5) by adding the number $n$ in the appropriate row, we get a filling of a "table" of type $\left(n_{1}, n_{2}, \ldots, n_{m}\right)$. Moreover, if two or more rows have the same number of squares, then the number $n$ can only be at the far right in the last of these rows. For example, if $n_{i}=n_{i+1}$, then $n_{i}-1<n_{i+1}$, so according to condition (1) we have $f\left(n_{1}, \ldots, n_{i}-1, n_{i+1}, \ldots, n_{m}\right)=0$. Therefore, some of the values

$$
f\left(n_{1}-1, n_{2}, \ldots, n_{m}\right), f\left(n_{1}, n_{2}-1, n_{3}, \ldots, n_{m}\right), \ldots, f\left(n_{1}, n_{2}, \ldots, n_{m-1}, n_{m}-1\right)
$$

of the function $f$ on the right side of (3) can be equal to 0.

Finally, if we use the function $f$ for the number of fillings of a "table" of type $(4,3,2)$, we get

$$
\begin{aligned}
& 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) \\
& =2 f(4,2,1)+2 f(3,3,2)+2 f(3,3,1)+f(4,3)
\end{aligned}
$$

$$
\begin{aligned}
& =16 f(2,1,1)+20 f(2,2)+25 f(3,1)+5 f(4) \\
& =16(f(1,1,1)+f(2,1,0))+20 f(2,1)+25(f(2,1)+f(3,0))+5 \\
& =16 f(1,1,1)+61 f(2,1)+25 f(3)+5 \\
& =16 f(1,1,0)+61(f(1,1)+f(2,0))+25+5 \\
& =77 f(1,1)+61 f(2)+30 \\
& =77 f(1)+61+30 \\
& =77+91 \\
& =168
\end{aligned}
$$