A368096 Triangle read by rows where T(n,k) is the number of non-isomorphic set-systems of length k and weight n.

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 1, 0, 1, 5, 8, 3, 1, 0, 1, 8, 18, 13, 3, 1, 0, 1, 9, 32, 37, 15, 3, 1, 0, 1, 13, 55, 96, 59, 16, 3, 1, 0, 1, 14, 91, 209, 196, 74, 16, 3, 1, 0, 1, 19, 138, 449, 573, 313, 82, 16, 3, 1, 0, 1, 20, 206, 863, 1529, 1147, 403, 84, 16, 3, 1

Offset

0,9

Comments

A set-system is a finite set of finite nonempty sets.

Conjecture: Column k = 2 is A101881.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Example

Triangle begins:
   1
   0   1
   0   1   1
   0   1   2   1
   0   1   4   3   1
   0   1   5   8   3   1
   0   1   8  18  13   3   1
   0   1   9  32  37  15   3   1
   0   1  13  55  96  59  16   3   1
   0   1  14  91 209 196  74  16   3   1
   0   1  19 138 449 573 313  82  16   3   1
   ...
Non-isomorphic representatives of the set-systems counted in row n = 5:
  .  {12345}  {1}{1234}  {1}{2}{123}  {1}{2}{3}{12}  {1}{2}{3}{4}{5}
              {1}{2345}  {1}{2}{134}  {1}{2}{3}{14}
              {12}{123}  {1}{2}{345}  {1}{2}{3}{45}
              {12}{134}  {1}{12}{13}
              {12}{345}  {1}{12}{23}
                         {1}{12}{34}
                         {1}{23}{24}
                         {1}{23}{45}

Mathematica

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]& /@ sps[Complement[set, s]]] /@ Cases[Subsets[set], {i, ___}];
mpm[n_]:=Join@@Table[Union[Sort[Sort /@ (#/.x_Integer:>s[[x]])]& /@ sps[Range[n]]], {s, Flatten[MapIndexed[Table[#2, {#1}]&, #]]& /@ IntegerPartitions[n]}];
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i, p[[i]]}, {i, Length[p]}])], {p, Permutations[Union@@m]}]]];
Table[Length[Union[brute /@ Select[mpm[n], UnsameQ@@#&&And@@UnsameQ@@@#&&Length[#]==k&]]], {n, 0, 5}, {k, 0, n}]

Prog

(PARI)
WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t, k)={WeighT(Vec(sum(j=1, #q, my(g=gcd(t, q[j])); g*x^(q[j]/g)) + O(x*x^k), -k))}
G(n)={my(s=0); forpart(q=n, my(p=sum(t=1, n, y^t*subst(x*Ser(K(q, t, n\t))/t, x, x^t))); s+=permcount(q)*exp(p-subst(subst(p, x, x^2), y, y^2))); s/n!}
T(n)={[Vecrev(p) | p <- Vec(G(n))]}
{ my(A=T(10)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Jan 11 2024

Crossrefs

Row sums are A283877, connected case A300913.

For multiset partitions we have A317533.

Counting connected components instead of edges gives A321194.

For set multipartitions we have A334550.

For strict multiset partitions we have A368099.

A000110 counts set-partitions, non-isomorphic A000041.

A003465 counts covering set-systems, unlabeled A055621.

A007716 counts non-isomorphic multiset partitions, connected A007718.

A049311 counts non-isomorphic set multipartitions, connected A056156.

A058891 counts set-systems, unlabeled A000612, connected A323818.

A316980 counts non-isomorphic strict multiset partitions, connected A319557.

A319559 counts non-isomorphic T_0 set-systems, connected A319566.

Cf. A101881, A255903, A302545, A306005, A317532, A317794, A317795, A319560, A321405, A368094, A368095.

Sequence in context: A128307 A349394 A034369 * A055277 A301422 A055340

Adjacent sequences: A368093 A368094 A368095 * A368097 A368098 A368099

Keyword

nonn,tabl

Author

Gus Wiseman, Dec 28 2023

Extensions

Terms a(66) and beyond from Andrew Howroyd, Jan 11 2024

Status

approved