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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .