9
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ Why do you need such a proof? $\endgroup$
    – Wojowu
    Dec 8, 2016 at 14:39
  • $\begingroup$ One reason: I plan to generalize to higher dimensions, later. $\endgroup$ Dec 8, 2016 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, 2016 at 14:42
  • $\begingroup$ Not necessarily, but it is more elegant if it can be done depending on the construction. $\endgroup$ Dec 8, 2016 at 14:49
  • 2
    $\begingroup$ I think you can cook up a bijective argument using a proof from here. $\endgroup$
    – Wojowu
    Dec 8, 2016 at 14:53

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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