login
Number of non-normal (0,1) semi-magic rectangles with sum of all entries equal to n.
14

%I #28 Jan 16 2019 19:42:44

%S 1,1,4,8,39,122,950,5042,45594,366243,3858148,39916802,494852628,

%T 6227020802,88543569808,1308012219556,21086562956045,355687428096002,

%U 6427672041650478,121645100408832002

%N Number of non-normal (0,1) semi-magic rectangles with sum of all entries equal to n.

%C A non-normal semi-magic rectangle is a nonnegative integer matrix with row sums and column sums all equal to d, for some d|n.

%C Rectangles must be of size k X m where k and m are divisors of n and k*m >= n. This implies that a(p) = p! + 2 for p prime since the only allowable rectangles are of sizes 1 X 1, 1 X p, p X 1 and p X p. There are no 1 X 1 rectangle that satisfies the condition. The 1 X p and p X 1 rectangles are [1....1] and its transpose, the p X p rectangle are necessarily permutation matrices and there are p! permutation matrices of size p X p. It also shows that a(n) >= n! + 2 for n > 1. - _Chai Wah Wu_, Jan 13 2019

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Magic_square">Magic square</a>

%F a(p) = p! + 2 for p prime. a(n) >= n! + 2 for n > 1. - _Chai Wah Wu_, Jan 13 2019

%e The a(3) = 8 semi-magic rectangles:

%e [1 1 1]

%e .

%e [1] [1 0 0] [1 0 0] [0 1 0] [0 1 0] [0 0 1] [0 0 1]

%e [1] [0 1 0] [0 0 1] [1 0 0] [0 0 1] [1 0 0] [0 1 0]

%e [1] [0 0 1] [0 1 0] [0 0 1] [1 0 0] [0 1 0] [1 0 0]

%t prs2mat[prs_]:=Table[Count[prs,{i,j}],{i,Union[First/@prs]},{j,Union[Last/@prs]}];

%t multsubs[set_,k_]:=If[k==0,{{}},Join@@Table[Prepend[#,set[[i]]]&/@multsubs[Drop[set,i-1],k-1],{i,Length[set]}]];

%t Table[Length[Select[Subsets[Tuples[Range[n],2],{n}],And[Union[First/@#]==Range[Max@@First/@#],Union[Last/@#]==Range[Max@@Last/@#],SameQ@@Total/@prs2mat[#],SameQ@@Total/@Transpose[prs2mat[#]]]&]],{n,5}]

%Y Cf. A006052, A007016, A068313, A101370, A120733, A271103, A319056.

%Y Cf. A321718, A321719, A321720, A321721, A321722, A321723, A321724, A321724.

%K nonn,more

%O 0,3

%A _Gus Wiseman_, Nov 18 2018

%E a(7) from _Chai Wah Wu_, Jan 13 2019

%E a(8)-a(13) from _Chai Wah Wu_, Jan 14 2019

%E a(14)-a(15) from _Chai Wah Wu_, Jan 15 2019

%E a(16)-a(19) from _Chai Wah Wu_, Jan 16 2019