# How many ways to partition $n=a.b$ into $a$ equal sized parts with equal sums?

In connection with determining the number of ways of arranging $n$ copies of each of the $n$ integers 1 upto $n$ in an $n$ by $n$ pandiagonal magic square, i.e. such that the sum of the integers in each row, column and 'broken' diagonal is the same, the following sub-problem arises.

Given two integers $a$ and $b$, whose product is $n$,how many ways are there to divide the $n$ integers 1 upto $n$ into $a$ groups of $b$ integers in such a way that the sum of the $b$ integers in each of the $a$ groups is the same? Obviously: if $n$ is prime, then $a=1$ or $b=1$; if $a=1$, then $b=n$ and there is only one way; if $b=1$, then $a=n$ and there are no ways.

Also if $a=2$, then the problem is equivalent to the number of ways of dividing a $b$ by $b$ chess board into two equal areas using a 'diagonal' line descending from the top left corner to the bottom right corner, following the edges of the chess squares, and proceeding either to the right or down (never to the left or up). The answer for this special case is known.

I have not yet found any mathematician who knows whether or not there is a general solution. Having an answer would enable me to extend a proof for a sub set of pandiagonal squares, those that are most-perfect. See Ollerenshaw and Brée, Most-perfect pandiagonal magic squares, or a review of same at journals.cambridge.org/article_S0013091500020381.

-
One should be able to find an estimate probabilistically, no? –  Will Sawin Oct 23 '11 at 18:25
David, your edit changing "$b=2$" to "$a=2$" is fine, but you should also change "$n$ by $n$" to "$b$ by $b$" (see Brendan McKay's comment to Zack Wolske's answer below). I would make the change myself, but I don't have the clout to edit. –  Barry Cipra Oct 24 '11 at 16:14

When $b=2$, the problem asks to partition $(1,\ldots, 2a)$ into sets of size $2$ such that each set has the same sum. This can only be done one way: $(1, 2a), (2, 2a-1)$, etc. The largest element must be paired with the smallest element, otherwise the sum of its set will be strictly larger than the sum of the set containing $1$. I don't understand the chessboard argument, but it counts a lot more than one. Are the sets then ordered? So there are $a!$ ways to do it?
When $a \equiv 2 (mod 4)$ and $b$ is odd, there are no solutions. The sum of numbers from $1$ up to $ab$ is $\frac{(ab)(ab+1)}{2}$, which is odd, so it cannot be split into an even number of sets with the same integer sum. Same is true for $a \equiv 4 (\mod 8)$, $a \equiv 8 (\mod 16)$, etc. by considering the largest power of two which divides the sum. So there are no solutions for a even, b odd.
I think the chessboard paths are actually for $a=2$, not $b=2$. The two subsets are encoded by which steps are vertical, and the sums of the subsets are related to the areas of the two fragments. Poster should edit. –  Brendan McKay Oct 23 '11 at 22:13
That won't work either. If $a=2$ and $b=3$, there is no way to partition $(1,2,3,4,5,6)$ into two sets of equal size and equal sum (both sums would have to be $10.5$), but there are plenty of ways to travel across a $6$ by $6$ chessboard and cut it into two pieces of $18$ squares each. Perhaps it is $a=2$, and an $\frac{n}{2}$ by $(n+1)$ chessboard. –  Zack Wolske Oct 23 '11 at 22:32
Try $a=2$ and a $b\times b$ chessboard. Odd $b$ has no solutions, even $b$ does. –  Brendan McKay Oct 24 '11 at 2:10