A321662 Number of non-isomorphic multiset partitions of weight n whose incidence matrix has all distinct entries.

1, 1, 1, 3, 3, 5, 13, 15, 23, 33, 49, 59, 83, 101, 133, 281, 321, 477, 655, 941, 1249, 1795, 2241, 3039, 3867, 5047, 6257, 8063, 11459, 13891, 18165, 23149, 29975, 37885, 49197, 61829, 89877, 109165, 145673, 185671, 246131, 310325, 408799, 514485, 668017, 871383

Offset: 0

Author

Gus Wiseman, Nov 15 2018

Keywords

• nonn

Comments

The incidence matrix of a multiset partition has entry (i, j) equal to the multiplicity of vertex i in part j.

Also the number of positive integer matrices up to row and column permutations with sum of elements equal to n and no zero rows or columns, with all different entries.

The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

Examples

			Non-isomorphic representatives of the a(3) = 3 through a(7) = 15 multiset partitions:
  {{111}}    {{1111}}    {{11111}}    {{111111}}      {{1111111}}
  {{122}}    {{1222}}    {{11222}}    {{112222}}      {{1112222}}
  {{1}{11}}  {{1}{111}}  {{12222}}    {{122222}}      {{1122222}}
                         {{1}{1111}}  {{122333}}      {{1222222}}
                         {{11}{111}}  {{1}{11111}}    {{1223333}}
                                      {{11}{1111}}    {{1}{111111}}
                                      {{1}{11222}}    {{11}{11111}}
                                      {{11}{1222}}    {{111}{1111}}
                                      {{112}{222}}    {{1}{112222}}
                                      {{122}{222}}    {{11}{12222}}
                                      {{2}{11222}}    {{112}{2222}}
                                      {{22}{1222}}    {{122}{2222}}
                                      {{1}{11}{111}}  {{2}{112222}}
                                                      {{22}{12222}}
                                                      {{1}{11}{1111}}
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1000

Crossrefs

Cf. A000219, A007716, A008289, A059201, A114736, A117433, A120733, A121860, A321653, A321659, A321660, A321661.

Programs

Mathematica

(* b = A121860 *) b[n_] := Sum[n!/(d! (n/d)!), {d, Divisors[n]}];
(* c = A008289 *) c[n_, k_] := c[n, k] = If[n < k || k < 1, 0, If[n == 1, 1, c[n - k, k] + c[n - k, k - 1]]];
a[n_] := If[n == 0, 1, Sum[ (b[k] + b[k + 1] - 2) c[n, k], {k, 1, n}]];
a /@ Range[0, 45] (* Jean-François Alcover, Sep 14 2019 *)

PARI

\\ here b(n) is A121860(n).
b(n)={sumdiv(n, d, n!/(d!*(n/d)!))}
seq(n)={my(B=vector((sqrtint(8*(n+1))+1)\2, n, if(n==1, 1, b(n-1)+b(n)-2))); apply(p->sum(i=0, poldegree(p), B[i+1]*polcoef(p, i)), Vec(prod(k=1, n, 1 + x^k*y + O(x*x^n))))} \\ Andrew Howroyd, Nov 16 2018

Formula

a(n) = Sum_{k>=1} (A121860(k) + A121860(k+1) - 2)*A008289(n,k) for n > 0. - Andrew Howroyd, Nov 17 2018

Extensions

Terms a(11) and beyond from Andrew Howroyd, Nov 16 2018