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?

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

Following @wojowu's suggestion, we have:

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} $$

It is easy to see that these are inverse.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.