login
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.
4

%I #33 May 28 2023 08:45:25

%S 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,

%T 720,636,468,272,133,48,16,4,1,1,5,25,95,330,1027,2780,6550,13375,

%U 23700,36403,48405,55800,55800,48405,36403,23700,13375,6550,2780,1027,330,95,25,5,1

%N 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.

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

%H Alois P. Heinz, <a href="/A220886/b220886.txt">Rows n = 0..32, flattened</a>

%e 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).

%e Triangle T(n,k) begins:

%e 1;

%e 1, 1;

%e 1, 2, 4, 2, 1;

%e 1, 3, 9, 20, 27, 27, 20, 9, 3, 1;

%e 1, 4, 16, 48, 133, 272, 468, 636, 720, 636, 468, 272, 133, 48, 16, 4, 1;

%e ...

%p g:= proc(n, i, j) option remember; expand(`if`(j=0, 1, `if`(i<0, 0, add(

%p g(n, i-1, j-k)*x^(i*k)*binomial(binomial(n, i)+k-1, k), k=0..j))))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(g(n$3)):

%p seq(T(n), n=0..5); # _Alois P. Heinz_, Feb 15 2023

%t 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

%t (* Second program: *)

%t 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 T[n_] := CoefficientList[g[n, n, n], x];

%t Table[T[n], {n, 0, 5}] // Flatten (* _Jean-François Alcover_, May 28 2023, after _Alois P. Heinz_ *)

%Y Row sums are A060690.

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

%Y Main diagonal gives A360660.

%Y Cf. A360693.

%K nonn,tabf

%O 0,5

%A _Geoffrey Critzer_, Feb 20 2013