# in need of a direct combinatorial/bijective proof

The following are very familiar and basic items, individually.

(1) The number $a(n)$ of rectangles (parallel to axes) in an $n\times n$ square grid.

(2) The number $b(n)$ of cubes (parallel to axes) in an $n\times n\times n$ cube.

However, I could not find a reference to a direct bijective proof for $a(n)=b(n)$. Can you provide such an argument of reference?

• Why do you need such a proof? – Wojowu Dec 8 '16 at 14:39
• One reason: I plan to generalize to higher dimensions, later. – T. Amdeberhan Dec 8 '16 at 14:40
• Do you have a reason to believe a bijective proof will generalize any more easily than any other (say, algebraic) proof? – Wojowu Dec 8 '16 at 14:42
• Not necessarily, but it is more elegant if it can be done depending on the construction. – T. Amdeberhan Dec 8 '16 at 14:49
• I think you can cook up a bijective argument using a proof from here. – Wojowu Dec 8 '16 at 14:53

Let $h$ be the side of the inner cube, and let $(i,j,k)$ be its corner nearest the origin. Then we have $0\le i,j,k < n-h+1 \le n$.
Let us describe our rectangle by the corners $(x_1, y_1)$ and $(x_2, y_2)$ with $x_1<x_2$ and $y_1<y_2$. Then our mapping from $(i,j,k,h)\to (x_1,y_1), (x_2,y_2)$ looks like
$$(i,j,k,h) \to \begin{cases} (i,k),(j,n-h+1) & \text{if i<j} \\ (j,k),(n-h+1,n-h+1) & \text{if i=j}\\ (k,j),(n-h+1,i) & \text{if i>j}. \end{cases}$$
Going the other way we have $$(x_1,y_1),(x_2,y_2)\to \begin{cases} (x_1,x_2,y_1,n-y_2+1) & \text{if x_2 < y_2}\\ (x_1,x_1,y_1,n-y_2+1) & \text{if x_2 = y_2}\\ (x_2,y_1,x_1,n-y_2+1) & \text{if x_2 > y_2} \end{cases}$$