Count 'em Staircases (Count 'em All 16!)

Suppose the number of quadrilaterals in an $a\times a$ staircase grid is $Q_a$ .

Let's try finding $Q_{a+1}$ .

As shown in the figure above, to increase $a$ by 1, we simply add $a+1$ squares to the hypotenuse (the yellow squares), the newly formed quadrilaterals must contain one of the yellow squares as its top-right corner square.

Let's say we choose one of the yellow squares that is $i$ units away from the left boundary of the new staircase grid as the top-right corner square of the new quadrilateral, then that square must be $a-i$ units away from the bottom boundary of the new staircase grid and the number of possible locations for its bottom-left corner square is $(i+1)(a-i+1)$ .

Therefore, $\begin{aligned}Q_{a+1}&=Q_a+\displaystyle \sum_{i=0}^a(i+1)(a-i+1) \\&=Q_a+\displaystyle \sum_{i=0}^a(ai-i^2+a+1) \\&=Q_a+\frac{a^2(a+1)}{2}-\frac{a(a+1)(2a+1)}{6}+a^2+2a+1 \\&=Q_a+\frac{a^3+6a^2+11a+6}{6} \end{aligned}$

Now we have $Q_a=Q_{a-1}+\frac{(a-1)^3+6(a-1)^2+11(a-1)+6}{6} \\ Q_{a-1}=Q_{a-2}+\frac{(a-2)^3+6(a-2)^2+11(a-2)+6}{6} \\ Q_{a-2}=Q_{a-3}+\frac{(a-3)^3+6(a-3)^2+11(a-3)+6}{6} \\\vdots \\ Q_3=Q_2+\frac{2^3+6(2)^2+11(2)+6}{6} \\ Q_2=Q_1+\frac{1^3+6(1)^2+11(1)+6}{6}$

Adding up all of these equations, cancelling out all the like terms and noting that $Q_1=1$ , we have $\begin{aligned} Q_a&=1+\frac{\left[\frac{a(a-1)}{2}\right]^2+a(a-1)(2a-1)+\frac{11a(a-1)}{2}+6(a-1)}{6} \\&=\frac{a}6\left[\frac{a^3-2a^2+a}{4}+2a^2-3a+1+\frac{11a-11}{2}+6\right] \\&=\frac{a}{24}(a^3-2a^2+a+8a^2-12a+28+22a-22) \\&=\frac{a}{24}(a^3+6a^2+11a+6) \\&=\frac{a(a+1)(a+2)(a+3)}{24} \end{aligned}$

Finally, substituting $a=30$ we would get the answer $40920$ .