|
|
A297077
|
|
Number of distinct row and column sums for n X n (0, 1)-matrices.
|
|
3
|
|
|
1, 2, 15, 328, 16145, 1475856, 219682183, 48658878080, 15047189968833, 6199170628499200, 3283463201858585471, 2174417430787021427712, 1760550428764505109190225, 1711145965399957937819322368, 1966168979042910307305159432375, 2636533865690624357354875499216896
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
a(n) is bounded above by 2^(n^2) and bounded below by A048163(n + 1).
Also the number of acyclic edge sets of the complete bipartite graph K_{n,n}. See proof by David E. Speyer at the Mathematics Stack Exchange link below.
It is also the number of n X n binary matrices that can be completed to the all-ones matrix by repeatedly changing an element from a zero to a one if that element is the only zero in its row or column. (Proof idea: Every acyclic edge set can be reduced to the empty set by removing one leaf edge at a time.) This can be interpreted as the number of ways of turning off storage nodes in an n X n array so that data remains restorable in the "full scheme" RAID (Redundant Array of Inexpensive Disks) design described by Nagel, Süß.- Jair Taylor, Jul 29 2019
|
|
LINKS
|
|
|
EXAMPLE
|
For n = 3, both of the following 3 X 3 (0,1)-matrices have identical row and column sums:
[1 0 1] [1 1 0]
[0 1 0] and [0 1 0]
[0 1 0] [0 0 1]
have row sums of [2 1 1] and column sums of [1 2 1].
So ([2 1 1], [1 2 1]) is one of the 328 possible row/column sums for a 3 X 3 matrix.
|
|
MATHEMATICA
|
{1}~Join~Array[Length@ Union@ Map[Total /@ {Transpose@ #, #} &, Tuples[{0, 1}, {#, #}]] &, 4] (* Michael De Vlieger, Jan 11 2018 *)
|
|
CROSSREFS
|
Cf. A048163 gives the number of row/column sums that uniquely identify a matrix.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|