A241956 Number of inequivalent m X n binary matrices, where equivalence means permutations of rows or columns. Presented in diagonal order, with (m,n)=(1,1), (1,2), (2,1), (1,3), (2,2), (3,1), ... .

2, 3, 3, 4, 7, 4, 5, 13, 13, 5, 6, 22, 36, 22, 6, 7, 34, 87, 87, 34, 7, 8, 50, 190, 317, 190, 50, 8, 9, 70, 386, 1053, 1053, 386, 70, 9, 10, 95, 734, 3250, 5624, 3250, 734, 95, 10, 11, 125, 1324, 9343, 28576, 28576, 9343, 1324, 125, 11

Offset

1,1

Comments

Same as A028657 without first row and column.

Links

Alois P. Heinz, Antidiagonals m = 1..45, flattened

Adalbert Kerber, Applied Finite Group Actions, second edition, Springer-Verlag, (1999). See table under Corollary 2.3.1 on page 68.

Various authors, How many n-by-m binary matrices are there up to row and column permutations

Index to number of inequivalent matrices modulo permutation of rows and columns

Example

The array begins:
  2  3    4     5      6        7         8           9 ...
  3  7   13    22     34       50        70          95 ...
  4 13   36    87    190      386       734        1324 ...
  5 22   87   317   1053     3250      9343       25207 ...
  6 34  190  1053   5624    28576    136758      613894 ...
  7 50  386  3250  28576   251610   2141733    17256831 ...
  8 70  734  9343 136758  2141733  33642660   508147108 ...
  9 95 1324 25207 613894 17256831 508147108 14685630688 ...
  (cf. A028657).

Maple

b:= proc(n, i) b(n, i):= `if`(n=0, [[]], `if`(i<1, [], [seq(map(
      p->`if`(j=0, p, [p[], [i, j]]), b(n-i*j, i-1))[], j=0..n/i)]))
    end:
g:= proc(n, k) option remember; add(add(2^add(add(i[2]*j[2]*
      igcd(i[1], j[1]), j=t), i=s) /mul(i[1]^i[2]*i[2]!, i=s)
      /mul(i[1]^i[2]*i[2]!, i=t), t=b(n+k$2)), s=b(n$2))
    end:
A:= (m, n)-> g(min(m, n), abs(m-n)):
seq(seq(A(m, 1+d-m), m=1..d), d=1..12); # Alois P. Heinz, Aug 13 2014

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 - k + 1, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Dec 09 2019, after Alois P. Heinz in A028657 *)

Crossrefs

Cf. A002724.

Sequence in context: A185738 A239361 A266362 * A227125 A248944 A267245

Adjacent sequences: A241953 A241954 A241955 * A241957 A241958 A241959

Keyword

nonn,tabl

Author

Don Knuth, Aug 09 2014

Status

approved