login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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

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 Two-Dimensional Parity RAIDs, 2017 13th European Dependable Computing Conference (EDCC), 58-65.

Stones, Rebecca J., Computing the number of h-edge spanning forests in complete bipartite graphs, Discrete Mathematics & Theoretical Computer Science, vol. 16, no. 1, pp. 313-326, 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 30 18:12 EDT 2020. Contains 337440 sequences. (Running on oeis4.)