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

1, 1, 4, 8, 39, 122, 950, 5042, 45594, 366243, 3858148, 39916802, 494852628, 6227020802, 88543569808, 1308012219556, 21086562956045, 355687428096002, 6427672041650478, 121645100408832002, 2437655776358606198, 51091307191310604724, 1125098543553717372868, 25852016738884976640002, 620752122372339473623314, 15511210044577707470250243

Offset: 0

Author

Gus Wiseman, Nov 18 2018

Keywords

• nonn

Comments

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.

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

Examples

			The a(3) = 8 semi-magic rectangles:
  [1 1 1]
.
  [1] [1 0 0] [1 0 0] [0 1 0] [0 1 0] [0 0 1] [0 0 1]
  [1] [0 1 0] [0 0 1] [1 0 0] [0 0 1] [1 0 0] [0 1 0]
  [1] [0 0 1] [0 1 0] [0 0 1] [1 0 0] [0 1 0] [1 0 0]
		

Links

• Max Alekseyev, Table of n, a(n) for n = 0..71
• Wikipedia, Magic square

Crossrefs

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

Cf. A321718, A321719, A321720, A321721, A321722, A321723, A321724, A321725.

Programs

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[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}]

Formula

a(p) = p! + 2 for p prime. a(n) >= n! + 2 for n > 1. - Chai Wah Wu, Jan 13 2019

Extensions

a(7) from Chai Wah Wu, Jan 13 2019

a(8)-a(13) from Chai Wah Wu, Jan 14 2019

a(14)-a(15) from Chai Wah Wu, Jan 15 2019

a(16)-a(19) from Chai Wah Wu, Jan 16 2019

Terms a(20) onward from Max Alekseyev, Dec 04 2024