A002724 Number of inequivalent n X n binary matrices, where equivalence means permutations of rows or columns.
1, 2, 7, 36, 317, 5624, 251610, 33642660, 14685630688, 21467043671008, 105735224248507784, 1764356230257807614296, 100455994644460412263071692, 19674097197480928600253198363072, 13363679231028322645152300040033513414, 31735555932041230032311939400670284689732948
Offset: 0
References
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 0..26 from Alois P. Heinz)
- Manuel Kauers and Jakob Moosbauer, Good pivots for small sparse matrices, arXiv:2006.01623 [cs.SC], 2020.
- A. Kerber, Experimentelle Mathematik, Séminaire Lotharingien de Combinatoire. Institut de Recherche Math. Avancée, Université Louis Pasteur, Strasbourg, Actes 19 (1988), 77-83. [Annotated scanned copy]
- Mathematics Stack Exchange, How many n-by-m binary matrices are there up to row and column permutations
- B. Misek, On the number of classes of strongly equivalent incidence matrices, (Czech with English summary) Casopis Pest. Mat. 89 1964 211-218.
- Marko Riedel, Maple code with two different algorithms
- M. Zivkovic, Classification of small (0,1) matrices, arXiv:math/0511636 [math.CO], 2005.
- Index entries for sequences related to binary matrices
- Index to number of inequivalent matrices modulo permutation of rows and columns
Crossrefs
Programs
-
Maple
# See Marko Riedel link.
-
Mathematica
b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i < 1, {}, Union[Flatten[Table[ Function[{p}, p + j*x^i] /@ b[n - i*j, i - 1], {j, 0, n/i}]]]]]; g[n_, k_] := g[n, k] = Sum[Sum[2^Sum[Sum[GCD[i, j]*Coefficient[s, x, i]* Coefficient[t, x, j], {j, 1, Exponent[t, x]}], {i, 1, Exponent[s, x]}]/ Product[i^Coefficient[s, x, i]*Coefficient[s, x, i]!, {i, 1, Exponent[s, x]}]/Product[i^Coefficient[t, x, i]*Coefficient[t, x, i]!, {i, 1, Exponent[t, x]}], {t, b[n + k, n + k]}], {s, b[n, n]}]; A[n_, k_] := g[Min[n, k], Abs[n - k]]; Table[A[n, n], {n, 0, 15}] (* Jean-François Alcover, Aug 10 2018, after Alois P. Heinz *) -
PARI
a(n) = A(n,n) \\ A defined in A028657. - Andrew Howroyd, Mar 01 2023
Formula
a(n) = Sum_{1*s_1+2*s_2+...=n, 1*t_1+2*t_2+...=n} (fixA[s_1, s_2, ...;t_1, t_2, ...]/(1^s_1*s_1!*2^s_2*s_2!*...*1^t_1*t_1!*2^t_2*t_2!*...)) where fixA[...] = 2^Sum_{i, j>=1} (gcd(i, j)*s_i*t_j). - Christian G. Bower, Dec 18 2003
a(n) = A028657(2*n, n). - Max Alekseyev, Jun 24 2023
Extensions
More terms from Vladeta Jovovic, Feb 04 2000
a(15) from Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 24 2008
Comments