|
|
A321717
|
|
Number of non-normal (0,1) semi-magic rectangles with sum of all entries equal to n.
|
|
14
|
|
|
1, 1, 4, 8, 39, 122, 950, 5042, 45594, 366243, 3858148, 39916802, 494852628, 6227020802, 88543569808, 1308012219556, 21086562956045, 355687428096002, 6427672041650478, 121645100408832002
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
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
|
|
LINKS
|
|
|
FORMULA
|
a(p) = p! + 2 for p prime. a(n) >= n! + 2 for n > 1. - Chai Wah Wu, Jan 13 2019
|
|
EXAMPLE
|
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]
|
|
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}]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|