|
%I #34 Aug 12 2022 09:18:17
%S 1,2,15,328,16145,1475856,219682183,48658878080,15047189968833,
%T 6199170628499200,3283463201858585471,2174417430787021427712,
%U 1760550428764505109190225,1711145965399957937819322368,1966168979042910307305159432375,2636533865690624357354875499216896
%N Number of distinct row and column sums for n X n (0, 1)-matrices.
%C a(n) is bounded above by 2^(n^2) and bounded below by A048163(n + 1).
%C 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.
%C 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
%H Andrew Howroyd, <a href="/A297077/b297077.txt">Table of n, a(n) for n = 0..100</a>
%H Mathematics Stack Exchange, <a href="https://math.stackexchange.com/questions/3235160/spanning-forests-of-bipartite-graphs-and-distinct-row-column-sums-of-binary-matr"> Spanning forests of bipartite graphs and distinct row/column sums of binary matrices</a>
%H Lars Nagel & Tim Süß, <a href="https://doi.org/10.1109/EDCC.2017.14">Computing the Probability for Data Loss in Two-Dimensional Parity RAIDs</a>, 2017 13th European Dependable Computing Conference (EDCC), 58-65.
%H Rebecca J. Stones, <a href="https://doi.org/10.46298/dmtcs.1248">Computing the number of h-edge spanning forests in complete bipartite graphs</a>, Discrete Mathematics & Theoretical Computer Science, vol. 16, no. 1, pp. 313-326, 2014.
%e For n = 3, both of the following 3 X 3 (0,1)-matrices have identical row and column sums:
%e [1 0 1] [1 1 0]
%e [0 1 0] and [0 1 0]
%e [0 1 0] [0 0 1]
%e have row sums of [2 1 1] and column sums of [1 2 1].
%e So ([2 1 1], [1 2 1]) is one of the 328 possible row/column sums for a 3 X 3 matrix.
%t {1}~Join~Array[Length@ Union@ Map[Total /@ {Transpose@ #, #} &, Tuples[{0, 1}, {#, #}]] &, 4] (* _Michael De Vlieger_, Jan 11 2018 *)
%Y Main diagonal of A328887.
%Y Cf. A048163 gives the number of row/column sums that uniquely identify a matrix.
%K nonn
%O 0,2
%A _Peter Kagey_, Dec 25 2017
%E Terms a(6) and beyond from _Andrew Howroyd_, Oct 29 2019
| 