A057150 - OEIS

A057150

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.

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, 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, 410, 840, 420, 82, 15, 2, 1, 0, 0, 0, 14, 531, 2144, 1744, 497, 83, 15, 2, 1

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,9

COMMENTS

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

LINKS

Table of n, a(n) for n=1..78.

EXAMPLE

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

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:

[0 0 1] [0 0 1] [0 0 1] [0 0 1] [0 0 1]

[0 0 1] [0 1 0] [0 1 1] [0 1 1] [1 1 0]

[1 1 1] [1 1 1] [1 0 1] [1 1 0] [1 1 0]

2 of size 4 X 4:

[0 0 0 1] [0 0 0 1]

[0 0 0 1] [0 0 1 0]

[0 0 1 0] [0 1 0 0]

[1 1 0 0] [1 0 0 1]

and 1 of size 5 X 5:

[0 0 0 0 1]

[0 0 0 1 0]

[0 0 1 0 0]

[0 1 0 0 0]

[1 0 0 0 0].

From Gus Wiseman, Nov 14 2018: (Start)

Triangle begins:

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 49 15 2 1

0 0 1 33 131 69 15 2 1

0 0 0 33 248 288 79 15 2 1

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

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

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

{{13}{23}{23}} {{1}{1}{4}{234}}

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

{{1}{3}{24}{34}}

{{1}{3}{4}{234}}

{{1}{4}{24}{34}}

{{1}{4}{4}{234}}

{{2}{4}{12}{34}}

{{3}{4}{12}{34}}

{{4}{4}{12}{34}}

(End)

MATHEMATICA

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

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}];

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[n_, k_] := M[k, k, n] - 2*M[k, k - 1, n] + M[k - 1, k - 1, n];

Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 10 2019, after Andrew Howroyd *)

PROG

(PARI) \\ See A321609 for M.

T(n, k) = M(k, k, n) - 2*M(k, k-1, n) + M(k-1, k-1, n); \\ Andrew Howroyd, Nov 14 2018

CROSSREFS

Row sums give A057151.

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

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

Sequence in context: A034093 A246187 A079508 * A185663 A262125 A360068

Adjacent sequences: A057147 A057148 A057149 * A057151 A057152 A057153

KEYWORD

nonn,tabl

AUTHOR

Vladeta Jovovic, Aug 14 2000

EXTENSIONS

Duplicate seventh row removed by Gus Wiseman, Nov 14 2018

STATUS

approved