login
A321719
Number of non-normal semi-magic squares with sum of entries equal to n.
25
1, 1, 3, 7, 28, 121, 746, 5041, 40608, 362936, 3635017, 39916801, 479206146, 6227020801, 87187426839, 1307674521272, 20923334906117, 355687428096001, 6402415241245577, 121645100408832001, 2432905938909013343, 51090942176372298027, 1124001180562929946213
OFFSET
0,3
COMMENTS
A non-normal semi-magic square is a nonnegative integer matrix with row sums and column sums all equal to d, for some d|n.
Squares must be of size k X k where k is a divisor of n. This implies that a(p) = p! + 1 for p prime since the only allowable squares are of sizes 1 X 1 and p X p. The 1 X 1 square is [p], the p X p squares are necessarily permutation matrices and there are p! permutation matrices of size p X p. Also, a(n) >= n! + 1 for n > 1. - Chai Wah Wu, Jan 13 2019
FORMULA
a(p) = p! + 1 for p prime and a(n) >= n! + 1 for n > 1 (see comment above). - Chai Wah Wu, Jan 13 2019
a(n) = Sum_{d|n} A257493(d, n/d) for n > 0. - Andrew Howroyd, Apr 11 2020
EXAMPLE
The a(3) = 7 semi-magic squares:
[3]
.
[1 0 0] [1 0 0] [0 1 0] [0 1 0] [0 0 1] [0 0 1]
[0 1 0] [0 0 1] [1 0 0] [0 0 1] [1 0 0] [0 1 0]
[0 0 1] [0 1 0] [0 0 1] [1 0 0] [0 1 0] [1 0 0]
MATHEMATICA
prs2mat[prs_]:=Table[Count[prs, {i, j}], {i, Union[First/@prs]}, {j, Union[Last/@prs]}];
multsubs[set_, k_]:=If[k==0, {{}}, Join@@Table[Prepend[#, set[[i]]]&/@multsubs[Drop[set, i-1], k-1], {i, Length[set]}]];
Table[Length[Select[multsubs[Tuples[Range[n], 2], n], And[Union[First/@#]==Range[Max@@First/@#]==Union[Last/@#], SameQ@@Total/@prs2mat[#], SameQ@@Total/@Transpose[prs2mat[#]]]&]], {n, 5}]
KEYWORD
nonn
AUTHOR
Gus Wiseman, Nov 18 2018
EXTENSIONS
a(7) from Chai Wah Wu, Jan 13 2019
a(6) corrected and a(8)-a(15) added by Chai Wah Wu, Jan 14 2019
a(16)-a(19) from Chai Wah Wu, Jan 16 2019
Terms a(20) and beyond from Andrew Howroyd, Apr 11 2020
STATUS
approved