[Unsolved] How many "magic squares" (combinatorial)?

[hxthanh]

A "magic square" is an $n\times n$ table includes $n^2$ non-negative integers satisfying conditions sum on each row and each column are equal and equal to $r$.
Define $S_3(r)$ is number of all $3\times 3$ magic square with row sum is $r$

Prove that:
$\displaystyle S_3(r)={r+2\choose 4}+{r+3\choose 4}+{r+4\choose 4}$

p/s: (sorry, if my thread wrong place)

 

[chisigma]

Re: [Unsolved] How many "magic square" (combinatorial)?

A "magic square" is an $n\times n$ table includes $n^2$ non-negative integers satisfying conditions sum on each row and each column are equal and equal to $r$.
Define $S_3(r)$ is number of all $3\times 3$ magic square with row sum is $r$

Prove that:
$\displaystyle S_3(r)={r+2\choose 4}+{r+3\choose 4}+{r+4\choose 4}$

p/s: (sorry, if my thread wrong place)

Only for clarification purpose: the $\displaystyle n^{2}$ numbers are $\displaystyle 1,2,...,n^{2}$ or a set of $n^{2}$ distinct nonnegative numbers with sum r?...

For example the following magic square with n=3...

$8\ 1\ 6$

$3\ 5\ 7$

$4\ 9\ 2$

... use the set 1,2,...,9 but in that case r is not an independent parameter because is...

$\displaystyle r = \frac{n\ (n^{2}+1)}{2} = 15$

Kind regards

$\chi$ $\sigma$

 

[topsquark]

Re: [Unsolved] How many "magic square" (combinatorial)?

A "magic square" is an $n\times n$ table includes $n^2$ non-negative integers satisfying conditions sum on each row and each column are equal and equal to $r$.
Define $S_3(r)$ is number of all $3\times 3$ magic square with row sum is $r$

Prove that:
$\displaystyle S_3(r)={r+2\choose 4}+{r+3\choose 4}+{r+4\choose 4}$

p/s: (sorry, if my thread wrong place)

The solution to 4 x 4 squares would be a lot more of a challenge. (Nerd)

Spoiler

There are only four 3 x 3 magic squares, with entries < 10 and r = 15, and they are rotations of one of them. ie.
[math]\left ( \begin{array}{ccc} 8 & 1 & 6 \\ 3 & 5 & 7 \\ 4 & 9 & 2 \end{array} \right )[/math], [math]\left ( \begin{array}{ccc} 4 & 3 & 8 \\ 9 & 5 & 1 \\ 2 & 7 & 6 \end{array} \right )[/math], [math]\left ( \begin{array}{ccc} 2 & 9 & 4 \\ 7 & 5 & 3 \\ 6 & 1 & 8 \end{array} \right )[/math], [math]\left ( \begin{array}{ccc} 6 & 7 & 2 \\ 1 & 5 & 9 \\ 8 & 3 & 4 \end{array} \right )[/math]

You can play with this for higher numbers than 1 - 9, but you will still only have the four rotated solutions. Thus, for valid values of r, [math]S_3(r) = 4[/math].

-Dan

Addendum:

Spoiler

You can also have "reflections" of the original square. Such as
[math]\left ( \begin{array}{ccc} 6 & 1 & 8 \\ 7 & 5 & 3 \\ 2 & 9 & 4 \end{array} \right )[/math]
and the like, so we get 8 more squares for a total of 12 overall.

Did I miss any more?

-Dan

 

[hxthanh]

Re: [Unsolved] How many "magic square" (combinatorial)?

$n^2$ non-negative integers is not necessarily different!

$\displaystyle S_3(0)={0+2\choose 4}+{0+3\choose 4}+{0+4\choose 4}=1$
$$\begin{matrix}0&0&0\\0&0&0\\0&0&0\end{matrix}$$
$\displaystyle S_3(1)={1+2\choose 4}+{1+3\choose 4}+{1+4\choose 4}=6$

$\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix} \quad \begin{bmatrix}1&0&0\\0&0&1\\0&1&0\end{bmatrix} \quad \begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix} \quad \begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix} \quad \begin{bmatrix}0&0&1\\0&1&0\\1&0&0\end{bmatrix} \quad \begin{bmatrix}0&0&1\\1&0&0\\0&1&0\end{bmatrix}$

$S_3(2)=21$

etc...

I tried transform magic square to follow
$$\begin{array}{|c|c|}\hline a&r-a-b&b\\ \hline r-a-c&a+b+c+d-r&r-b-d\\ \hline c&r-c-d&d\\ \hline\end{array}$$

 

[topsquark]

Re: [Unsolved] How many "magic square" (combinatorial)?

$n^2$ non-negative integers is not necessarily different!

$\displaystyle S_3(0)={0+2\choose 4}+{0+3\choose 4}+{0+4\choose 4}=1$
$$\begin{matrix}0&0&0\\0&0&0\\0&0&0\end{matrix}$$
$\displaystyle S_3(1)={1+2\choose 4}+{1+3\choose 4}+{1+4\choose 4}=6$

$\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix} \quad \begin{bmatrix}1&0&0\\0&0&1\\0&1&0\end{bmatrix} \quad \begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix} \quad \begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix} \quad \begin{bmatrix}0&0&1\\0&1&0\\1&0&0\end{bmatrix} \quad \begin{bmatrix}0&0&1\\1&0&0\\0&1&0\end{bmatrix}$

$S_3(2)=21$

etc...

I tried transform magic square to follow
$$\begin{array}{|c|c|}\hline a&r-a-b&b\\ \hline r-a-c&a+b+c+d-r&r-b-d\\ \hline c&r-c-d&d\\ \hline\end{array}$$

Okay. I have never seen magic squares with repeated numbers in them, so I guess my solutions would not be called "general."

-Dan

 

[chisigma]

Re: [Unsolved] How many "magic square" (combinatorial)?

$n^2$ non-negative integers is not necessarily different!

$\displaystyle S_3(0)={0+2\choose 4}+{0+3\choose 4}+{0+4\choose 4}=1$
$$\begin{matrix}0&0&0\\0&0&0\\0&0&0\end{matrix}$$
$\displaystyle S_3(1)={1+2\choose 4}+{1+3\choose 4}+{1+4\choose 4}=6$

$\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix} \quad \begin{bmatrix}1&0&0\\0&0&1\\0&1&0\end{bmatrix} \quad \begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix} \quad \begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix} \quad \begin{bmatrix}0&0&1\\0&1&0\\1&0&0\end{bmatrix} \quad \begin{bmatrix}0&0&1\\1&0&0\\0&1&0\end{bmatrix}$

$S_3(2)=21$

etc...

I tried transform magic square to follow
$$\begin{array}{|c|c|}\hline a&r-a-b&b\\ \hline r-a-c&a+b+c+d-r&r-b-d\\ \hline c&r-c-d&d\\ \hline\end{array}$$

Ok!... if we accept [because there are different definitions of 'magic square'...] that a 'magic square' is a n x n matrix with the sum of the elemnts of all rows and colums is the same number k, then, indicating $M_{n} (k)$ an n x n magic square with 'magic number' k, the following basic statement should hold...

$\displaystyle A_{n} (k) + B_{n} (1) = C_{n} (k+1)\ (1)$

... i.e. a magic square with magic number k+1 is the sum of a magic square with magic number k and a magic square with magic number 1. Now You have found that $\displaystyle S_{3} (0)=1$ and $\displaystyle S_{3} (1) = 6$... all right!...

Now $\displaystyle S_{3} (2)$ can be obtained computing the possible distict sum of all the magic square magic number 1 that is $\displaystyle S_{3} (2) = 6 + 5 + 4 + 3 + 2 + 1 = 21$. The behaviour for k > 2 will be analysed in next post...

Kind regards

$\chi$ $\sigma$

 

[hxthanh]

Re: [Unsolved] How many "magic square" (combinatorial)?

A "magic square" is an $n\times n$ table includes $n^2$ non-negative integers satisfying conditions sum on each row and each column are equal and equal to $r$.
Define $S_3(r)$ is number of all $3\times 3$ magic square with row sum is $r$

Prove that:
$\displaystyle S_3(r)={r+2\choose 4}+{r+3\choose 4}+{r+4\choose 4}$

MY SOLUTION

Spoiler

First, we creating 2 rows into square by 2 equations $a_1+a_2+a_3=b_1+b_2+b_3=n$
Number of solutions of both equations as ${n+2\choose 2}$
Therefor, number of squares as ${n+2\choose 2}^2$ including type non-magic squares.

For each square created above, we seeking inappropriate condition:
$\begin{array}{|c|c|c|} \hline\\ a & b & n-a-b \\ \hline c & d & n- c-d\\ \hline n- a-c & n- b-d & a+b+c+d-n \\ \hline \end{array}$

We get condition is $a+b+c+d < n \Leftrightarrow a+b+c+d+e=n, \quad (0<e\le n)\quad (*)$
Number of solutions $(*)$ as ${n+3\choose 4}$
Similarly for the terms of 3th-row.

Result: Number of magic-square as
${n+2\choose 2}^2 -3 {n+3\choose 4}={n+4\choose 4} + {n+3\choose 4} + {n+2\choose 4} \quad \square$