A321661 Number of non-isomorphic multiset partitions of weight n where the nonzero entries of the incidence matrix are all distinct.

1, 1, 1, 4, 4, 7, 22, 25, 40, 58, 186, 204, 347, 478, 734, 2033, 2402, 3814, 5464, 8142, 11058, 30142, 34437, 55940, 77794, 116954, 156465, 229462, 533612, 640544, 994922, 1397896, 2048316, 2778750, 3987432, 5292293, 11921070, 14076550, 21802928, 29917842, 44080285

Offset

0,4

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, whose nonzero entries are all distinct.

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

Links

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

Formula

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

Example

Non-isomorphic representatives of the a(1) = 1 through a(6) = 22 multiset partitions:
  {{1}}  {{11}}  {{111}}    {{1111}}    {{11111}}    {{111111}}
                 {{122}}    {{1222}}    {{11222}}    {{112222}}
                 {{1}{11}}  {{1}{111}}  {{12222}}    {{122222}}
                 {{1}{22}}  {{1}{222}}  {{1}{1111}}  {{122333}}
                                        {{11}{111}}  {{1}{11111}}
                                        {{11}{222}}  {{11}{1111}}
                                        {{1}{2222}}  {{1}{11222}}
                                                     {{11}{1222}}
                                                     {{11}{2222}}
                                                     {{112}{222}}
                                                     {{11}{2333}}
                                                     {{1}{22222}}
                                                     {{122}{222}}
                                                     {{1}{22333}}
                                                     {{122}{333}}
                                                     {{2}{11222}}
                                                     {{22}{1222}}
                                                     {{1}{11}{111}}
                                                     {{1}{11}{222}}
                                                     {{1}{22}{222}}
                                                     {{1}{22}{333}}
                                                     {{2}{11}{222}}

Prog

(PARI) \\ here b(n) is A059849(n).
b(n)={sum(k=0, n, stirling(n, k, 1)*sum(i=0, k, stirling(k, i, 2))^2)}
seq(n)={my(B=vector((sqrtint(8*(n+1))+1)\2, n, b(n-1))); 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

Crossrefs

Cf. A000219, A007716, A008289, A059201, A059849, A114736, A117433, A120733, A321653, A321659, A321660, A321662.

Sequence in context: A336718 A173324 A318243 * A183492 A019159 A019250

Adjacent sequences: A321658 A321659 A321660 * A321662 A321663 A321664

Keyword

nonn

Author

Gus Wiseman, Nov 15 2018

Extensions

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

Status

approved