A220886 Irregular triangular array read by rows: T(n,k) is the number of inequivalent n X n {0,1} matrices modulo permutation of the rows, containing exactly k 1's; n>=0, 0<=k<=n^2.

1, 1, 1, 1, 2, 4, 2, 1, 1, 3, 9, 20, 27, 27, 20, 9, 3, 1, 1, 4, 16, 48, 133, 272, 468, 636, 720, 636, 468, 272, 133, 48, 16, 4, 1, 1, 5, 25, 95, 330, 1027, 2780, 6550, 13375, 23700, 36403, 48405, 55800, 55800, 48405, 36403, 23700, 13375, 6550, 2780, 1027, 330, 95, 25, 5, 1

Offset

0,5

Comments

In other words, two matrices are considered equivalent if one can be obtained from the other by some sequence of interchanges of the rows.

Links

Alois P. Heinz, Rows n = 0..32, flattened

Example

T(2,2) = 4 because we have: {{0,0},{1,1}}; {{0,1},{1,0}}; {{0,1},{0,1}}; {{1,0},{1,0}} (where the first two matrices were arbitrarily selected as class representatives).
Triangle T(n,k) begins:
  1;
  1, 1;
  1, 2,  4,  2,   1;
  1, 3,  9, 20,  27,  27,  20,   9,   3,   1;
  1, 4, 16, 48, 133, 272, 468, 636, 720, 636, 468, 272, 133, 48, 16, 4, 1;
  ...

Maple

g:= proc(n, i, j) option remember; expand(`if`(j=0, 1, `if`(i<0, 0, add(
      g(n, i-1, j-k)*x^(i*k)*binomial(binomial(n, i)+k-1, k), k=0..j))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(g(n$3)):
seq(T(n), n=0..5);  # Alois P. Heinz, Feb 15 2023

Mathematica

nn=100; Table[CoefficientList[Series[CycleIndex[SymmetricGroup[n], s]/.Table[s[i]->(1+x^i)^n, {i, 1, n}], {x, 0, nn}], x], {n, 0, 5}]//Grid
(* Second program: *)
g[n_, i_, j_] := g[n, i, j] = Expand[If[j == 0, 1, If[i < 0, 0, Sum[g[n, i - 1, j - k]*x^(i*k)*Binomial[Binomial[n, i] + k - 1, k], {k, 0, j}]]]];
T[n_] := CoefficientList[g[n, n, n], x];
Table[T[n], {n, 0, 5}] // Flatten (* Jean-François Alcover, May 28 2023, after Alois P. Heinz *)

Crossrefs

Row sums are A060690.

Columns k=0-3 give: A000012, A000027, A000290 (n>=2), A203552 (n>=3).

Main diagonal gives A360660.

Cf. A360693.

Sequence in context: A059317 A322046 A247644 * A256156 A342060 A302828

Adjacent sequences: A220883 A220884 A220885 * A220887 A220888 A220889

Keyword

nonn,tabf

Author

Geoffrey Critzer, Feb 20 2013

Status

approved