

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 on math.stackexchange.com below.
It is also the number of n X n binary matrices that can be completed to the allones 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

Andrew Howroyd, Table of n, a(n) for n = 0..100
Math Stack Exchange, Spanning forests of bipartite graphs and distinct row/column sums of binary matrices
Lars Nagel & Tim Süß, Computing the Probability for Data Loss in TwoDimensional Parity RAIDs, 2017 13th European Dependable Computing Conference (EDCC), 5865.
Stones, Rebecca J., Computing the number of hedge spanning forests in complete bipartite graphs, Discrete Mathematics & Theoretical Computer Science, vol. 16, no. 1, pp. 313326, 2014.


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

Main diagonal of A328887.
Cf. A048163 gives the number of row/column sums that uniquely identify a matrix.
Sequence in context: A015200 A331344 A030642 * A175563 A231443 A068391
Adjacent sequences: A297074 A297075 A297076 * A297078 A297079 A297080


KEYWORD

nonn


AUTHOR

Peter Kagey, Dec 25 2017


EXTENSIONS

Terms a(6) and beyond from Andrew Howroyd, Oct 29 2019


STATUS

approved



