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

Author

Geoffrey Critzer, Feb 20 2013

Keywords

• nonn
• tabf

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.

Examples

			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;
  ...
		

Links

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

Crossrefs

Row sums are A060690.

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

Main diagonal gives A360660.

Cf. A360693.

Programs

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 *)