0
$\begingroup$

I'm trying to come up with a formula to count the number of squares in an $x_1 \times x_2 \times x_3$ grid... and eventually I gave up on figuring out if the points were in a plane and threw a computer at the problem. I generated a bunch of examples and fit a polynomial to the result; however, I want to try and condense the result down (I'm assuming that it can be factored because the 2D result condenses down to the rather nice $x_2(x_2+1)(x_2+2)(2 x_1+1-x_2)/12$). Any ideas on factoring this?

$$(10 x_2+128 x_3+20 x_1 x_2+5 x_2^2-430 x_1 x_3-680 x_2 x_3+740 x_3^2+30 x_1 x_2^2-10 x_2^3+260 x_1 x_2 x_3+45 x_2^2 x_3+705 x_1 x_3^2+1075 x_2 x_3^2-1400 x_3^3+10 x_1 x_2^3-5 x_2^4+30 x_1 x_2^2 x_3-10 x_2^3 x_3-240 x_1 x_2 x_3^2-60 x_2^2 x_3^2-200 x_1 x_3^3-300 x_2 x_3^3+580 x_3^4+10 x_1 x_2^3 x_3-5 x_2^4 x_3+120 x_1 x_2 x_3^3+20 x_2^2 x_3^3-15 x_1 x_3^4-25 x_2 x_3^4-48 x_3^5)/60$$

$\endgroup$
7
  • $\begingroup$ Do we need to consider diagonal squares? For example: in a $3\times 3$ grid, we can connect the mid points of the outer edges to get a square. $\endgroup$ – Aldoggen May 2 at 15:03
  • $\begingroup$ The expression should be correct and it counts the diagonal squares. I'm just wondering about factoring the expression into something prettier $\endgroup$ – user1543042 May 2 at 15:21
  • $\begingroup$ I just spent a good amount of time writing down a solution for the problem without the diagonal squares. Sad times. $\endgroup$ – Aldoggen May 2 at 15:23
  • $\begingroup$ Still would love to see it :-) $\endgroup$ – user1543042 May 2 at 15:29
  • $\begingroup$ Thanks, that means a lot! $\endgroup$ – Aldoggen May 2 at 15:41
1
$\begingroup$

I'm not going to try to factor that polynomial. I'm instead going to solve the initial problem, which is counting the number of squares in a grid. This solution only counts squares whose edges lie on the grid, which means it is not an actual answer to this question. The question also considers diagonal squares, such as the one formed by the o's in following diagram:

• o •
o • o
• o •

Let's start with a two-dimensional grid of size $m\times n$. Call the direction in which the grid has length $n$ the horizontal direction. There are of course $mn$ squares of size 1 in such a grid, but how do we count the larger ones, let's say a square of size $k$? Well, an idea is to consider a square in one corner, and look at how many steps we can move it until it hits an other border. For horizontal movement, a square can move $n-k$ steps. Analogously, for vertical movement we get $m-k$ steps. This means there are $n-k+1$ horizontal positions: one for each step we can take, plus the initial one. There are thus $(m-k+1)(n-k+1)$ squares of size $k$ in our grid. Note that in a grid of size $m\times n$, the maximum size a square can have is $s = \min\{m,n\}$. Denote with $a(m,n)$ the amount of squares in a grid of size $m\times n$. If we sum for all possible values of $k$, i.e. $k\in\{1,\dots,s\}$, we get $$ \begin{aligned} a(m,n) &= \sum_{k=1}^s(m-k+1)(n-k+1) \\ &= \sum_{k=1}^s\left( k^2 - (m+n+2)k + (m+1)(n+1) \right) \\ &\overset{*}{=} \frac{s(s+1)(2s+1)}{6} - (m+n+2)\frac{s(s+1)}{2} + (m+1)(n+1)s. \\ \end{aligned} $$ In the starred equation, I evaluated $\sum_{k=1}^sk^2$ and $\sum_{k=1}^sk$, which have commonly known closed expressions.

Now we can calculate the amount of squares in a three-dimensional grid of size $m\times n\times o$. Let's introduce axes $\mathbf x$, $\mathbf y$ and $\mathbf z$ such that the projection of the grid on the $\mathbf x$-$\mathbf y$-plane has size $m\times n$ and so on. Now comes the fun part, because we can use our two-dimensional solution again! All squares in the grid lie in a plane of the grid (this is an assumption I made in the first paragraph), and every square lies in only one plane. This means we can sum the squares in each plane to get the total amount of squares.

Consider the planes in the grid which are parallel to the $\mathbf x$-$\mathbf y$-plane. These planes have size $m\times n$, and hence each contains $a(m,n)$ squares. Because the third dimension of the grid is $o$, there are $o+1$ of these planes, which means the total number of squares in these planes is $(o+1)a(m,n)$. Analogously, for the planes parallel to the $\mathbf x$-$\mathbf z$-plane, we get $(n+1)a(m,o)$, and for the planes parallel to the $\mathbf y$-$\mathbf z$-plane, we get $(m+1)a(n,o)$ squares, which means the total number of squares is

$$ (o+1)a(m,n) + (n+1)a(m,o) + (m+1)a(n,o). $$

Let me repeat that this is not an answer to the question.

$\endgroup$

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.