|
|
A321662
|
|
Number of non-isomorphic multiset partitions of weight n whose incidence matrix has all distinct entries.
|
|
6
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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, 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.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
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}}
|
|
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}]];
|
|
PROG
|
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
|
|
CROSSREFS
|
Cf. A000219, A007716, A008289, A059201, A114736, A117433, A120733, A121860, A321653, A321659, A321660, A321661.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|