A242093 Number A(n,k) of inequivalent n X k binary matrices, where equivalence means permutations of rows or columns or the symbol set; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 5, 2, 1, 1, 3, 8, 8, 3, 1, 1, 3, 14, 18, 14, 3, 1, 1, 4, 20, 47, 47, 20, 4, 1, 1, 4, 30, 95, 173, 95, 30, 4, 1, 1, 5, 40, 200, 545, 545, 200, 40, 5, 1, 1, 5, 55, 367, 1682, 2812, 1682, 367, 55, 5, 1, 1, 6, 70, 674, 4745, 14386, 14386, 4745, 674, 70, 6, 1

Offset

0,8

Links

Alois P. Heinz, Antidiagonals n = 0..35, flattened

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

Example

A(1,4) = 3: [0 0 0 0], [1 0 0 0], [1 1 0 0].
A(1,5) = 3: [0 0 0 0 0], [1 0 0 0 0], [1 1 0 0 0].
A(2,2) = 5:
  [0 0]  [1 0]  [1 1]  [1 0]  [1 0]
  [0 0], [0 0], [0 0], [1 0], [0 1].
A(3,2) = 8:
  [0 0]  [1 0]  [1 1]  [1 0]  [1 0]  [1 0]  [1 0]  [1 1]
  [0 0], [0 0], [0 0], [1 0], [0 1], [1 0], [0 1], [1 0].
  [0 0]  [0 0]  [0 0]  [0 0]  [0 0]  [1 0]  [1 0]  [0 0]
Square array A(n,k) begins:
  1, 1,  1,   1,    1,     1,       1,        1, ...
  1, 1,  2,   2,    3,     3,       4,        4, ...
  1, 2,  5,   8,   14,    20,      30,       40, ...
  1, 2,  8,  18,   47,    95,     200,      367, ...
  1, 3, 14,  47,  173,   545,    1682,     4745, ...
  1, 3, 20,  95,  545,  2812,   14386,    68379, ...
  1, 4, 30, 200, 1682, 14386,  126446,  1072086, ...
  1, 4, 40, 367, 4745, 68379, 1072086, 16821330, ...

Maple

with(numtheory):
b:= proc(n, i) option remember; `if`(n=0, {0}, `if`(i<1, {},
      {seq(map(p-> p+j*x^i, b(n-i*j, i-1) )[], j=0..n/i)}))
    end:
g:= proc(n, k) option remember; add(add(add(mul(mul(add(d*
      coeff(u, x, d), d=divisors(ilcm(i, j)))^(igcd(i, j)*
      coeff(s, x, i)*coeff(t, x, j)), j=1..degree(t)),
      i=1..degree(s))/mul(i^coeff(u, x, i)*coeff(u, x, i)!,
      i=1..degree(u))/mul(i^coeff(t, x, i)*coeff(t, x, i)!,
      i=1..degree(t))/mul(i^coeff(s, x, i)*coeff(s, x, i)!,
      i=1..degree(s)), u=b(2$2)), t=b(n$2)), s=b(k$2))
    end:
A:= (n, k)-> g(sort([n, k])[]):
seq(seq(A(n, d-n), n=0..d), d=0..12);

Mathematica

b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i < 1, {}, Flatten[Table[Map[ Function[p, p + j*x^i], b[n - i*j, i - 1]], {j, 0, n/i}]]]];
g[n_, k_] := g[n, k] = Sum[Sum[Sum[Product[Product[With[{gc = GCD[i, j]* Coefficient[s, x, i]*Coefficient[t, x, j]}, If[gc == 0, 1, Sum[d* Coefficient[u, x, d], {d, Divisors[LCM[i, j]]}]^gc]], {j, 1, Exponent[t, x]}],
{i, Exponent[s, x]}]/Product[i^Coefficient[u, x, i]*Coefficient[u, x, i]!,
{i, Exponent[u, x]}]/Product[i^Coefficient[t, x, i]*Coefficient[t, x, i]!,
{i, Exponent[t, x]}]/Product[i^Coefficient[s, x, i]*Coefficient[s, x, i]!,
{i, Exponent[s, x]}], {u, b[2, 2]}], {t, b[n, n]}], {s, b[k, k]}];
A[n_, k_] := g @@ Sort[{n, k}];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Apr 25 2016, adapted from Maple, updated Jan 01 2021 *)

Crossrefs

Columns (or rows) k=0-10 give: A000012, A008619, A006918(n+1), A246148, A246149, A246150, A246151, A246152, A246153, A246154, A246155.

Main diagonal gives A091059.

Cf. A028657, A241956, A242095.

Sequence in context: A131373 A245185 A034853 * A391819 A350910 A390207

Adjacent sequences: A242090 A242091 A242092 * A242094 A242095 A242096

Keyword

nonn,tabl

Author

Alois P. Heinz, Aug 14 2014

Status

approved