We define a function f on the m-tuples (n1,n2,...,nm) in the following way: f(n1,n2,...,nm)=0 for the m-tuples for which it does not hold that:
n1≥n2≥⋯≥nm≥0.(1)
If n1≥n2≥⋯≥nm≥0, then it holds that
f(n1,n2,…,nm,0)=f(n1,n2,…,nm).(2)
f(n1,n2,…,nm)=f(n1−1,n2,…,nm)+f(n1,n2−1,…,nm)+⋯+f(n1,n2,…,nm−1).(3)
f(n)=1, for n≥0.(4)
The function f is well-defined. We will show that f(n1,n2,…,nm) is the number of grids of type (n1,n2,…,nm). 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,…,n). Condition (2) is also clear. To show that a grid of type (n1,n2,…,nm) 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, n1=n2, then f(n1−1,n2,…,nm)=0 since n1−1<n2. Therefore in condition (3) all expressions
f(n1−1,n2,…,nm),f(n1,n2−1,…,nm),…,f(n1,n2,…,nm−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).
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.