login
Triangle read by rows: T(n,k) = number of k X k binary matrices with n ones, with no zero rows or columns, up to row and column permutation.
12

%I #21 Sep 10 2019 09:11:41

%S 1,0,1,0,1,1,0,1,2,1,0,0,5,2,1,0,0,4,11,2,1,0,0,3,21,14,2,1,0,0,1,34,

%T 49,15,2,1,0,0,1,33,131,69,15,2,1,0,0,0,33,248,288,79,15,2,1,0,0,0,19,

%U 410,840,420,82,15,2,1,0,0,0,14,531,2144,1744,497,83,15,2,1

%N Triangle read by rows: T(n,k) = number of k X k binary matrices with n ones, with no zero rows or columns, up to row and column permutation.

%C Also the number of non-isomorphic set multipartitions (multisets of sets) of weight n with k parts and k vertices. - _Gus Wiseman_, Nov 14 2018

%e [1], [0,1], [0,1,1], [0,1,2,1], [0,0,5,2,1], [0,0,4,11,2,1], ...;

%e There are 8 square binary matrices with 5 ones, with no zero rows or columns, up to row and column permutation: 5 of size 3 X 3:

%e [0 0 1] [0 0 1] [0 0 1] [0 0 1] [0 0 1]

%e [0 0 1] [0 1 0] [0 1 1] [0 1 1] [1 1 0]

%e [1 1 1] [1 1 1] [1 0 1] [1 1 0] [1 1 0]

%e 2 of size 4 X 4:

%e [0 0 0 1] [0 0 0 1]

%e [0 0 0 1] [0 0 1 0]

%e [0 0 1 0] [0 1 0 0]

%e [1 1 0 0] [1 0 0 1]

%e and 1 of size 5 X 5:

%e [0 0 0 0 1]

%e [0 0 0 1 0]

%e [0 0 1 0 0]

%e [0 1 0 0 0]

%e [1 0 0 0 0].

%e From _Gus Wiseman_, Nov 14 2018: (Start)

%e Triangle begins:

%e 1

%e 0 1

%e 0 1 1

%e 0 1 2 1

%e 0 0 5 2 1

%e 0 0 4 11 2 1

%e 0 0 3 21 14 2 1

%e 0 0 1 34 49 15 2 1

%e 0 0 1 33 131 69 15 2 1

%e 0 0 0 33 248 288 79 15 2 1

%e Non-isomorphic representatives of the multiset partitions counted in row 6 {0,0,4,11,2,1} are:

%e {{12}{13}{23}} {{1}{1}{1}{234}} {{1}{2}{3}{3}{45}} {{1}{2}{3}{4}{5}{6}}

%e {{1}{23}{123}} {{1}{1}{24}{34}} {{1}{2}{3}{5}{45}}

%e {{13}{23}{23}} {{1}{1}{4}{234}}

%e {{3}{23}{123}} {{1}{2}{34}{34}}

%e {{1}{3}{24}{34}}

%e {{1}{3}{4}{234}}

%e {{1}{4}{24}{34}}

%e {{1}{4}{4}{234}}

%e {{2}{4}{12}{34}}

%e {{3}{4}{12}{34}}

%e {{4}{4}{12}{34}}

%e (End)

%t permcount[v_List] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];

%t c[p_List, q_List, k_] := SeriesCoefficient[Product[Product[(1 + O[x]^(k + 1) + x^LCM[p[[i]], q[[j]]])^GCD[p[[i]], q[[j]]], {j, 1, Length[q]}], {i, 1, Length[p]}], {x, 0, k}];

%t M[m_, n_, k_] := M[m, n, k] = Module[{s = 0}, Do[Do[s += permcount[p]* permcount[q]*c[p, q, k], {q, IntegerPartitions[n]}], {p, IntegerPartitions[m]}]; s/(m!*n!)];

%t T[n_, k_] := M[k, k, n] - 2*M[k, k - 1, n] + M[k - 1, k - 1, n];

%t Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Sep 10 2019, after _Andrew Howroyd_ *)

%o (PARI) \\ See A321609 for M.

%o T(n,k) = M(k,k,n) - 2*M(k,k-1,n) + M(k-1,k-1,n); \\ _Andrew Howroyd_, Nov 14 2018

%Y Row sums give A057151.

%Y Cf. A049311, A056037, A056079, A056080, A057149, A057151, A057152.

%Y Cf. A007716, A048291, A054976, A101370, A104601, A104602, A120732, A120733, A135588, A319616, A321609, A321615.

%K nonn,tabl

%O 1,9

%A _Vladeta Jovovic_, Aug 14 2000

%E Duplicate seventh row removed by _Gus Wiseman_, Nov 14 2018