>>500 >>504氏とは微妙に違うアプローチ。
左下隅を原点(0,0)とし、以下普通にx座標とy座標を取る。
n段積まれている状態では、領域の一番右上側に並ぶ頂点は、すべて
x≧1、y≧1、x+y=n+1を満たすことになる。

今、n-1段積まれている状態にn段目を追加したとき、作れる長方形の
数がいくつ「増えるか」を考える（つまり、漸化式を作る方針）。

この設定で、右上に(x,n+1-x)という座標を取ったとき(1≦x≦n)、
左下のx座標は0〜x-1のx通り、y座標は0〜n-xのn+1-x通りあるので、
左下のバリエーションは x*(n+1-x) だけあることになる。

よって、第n段追加によって増加する長方形の個数は
Σ[x=1,n](x*(n+1-x)) = (n+1)・(1/2)n・(n+1) - (1/6)n(n+1)(2n+1)
=(1/6)n(n+1)(n+2) 個となる。

n段積んだときの長方形の個数をS_nで表せば、
　S_1=1
　S_n=S_[n-1]+(1/6)n(n+1)(n+2)
あとはこの漸化式を解けばいい。真っ向勝負するとうんざりだが、
じつはちょっと知られた関係として、S_n=(1/24)n(n+1)(n+2)(n+3)でおけ。

S_n-S_[n-1]=(1/24){n(n+1)(n+2)(n+3)-(n-1)n(n+1)(n+2)}
=(1/24)n(n+1)(n+2)((n+3)-(n-1))=(1/6)n(n+1)(n+2)
n=1のときもこれでよい。（ここ、強引なんだが書いちゃったので）