|
|
A283877
|
|
Number of non-isomorphic set-systems of weight n.
|
|
174
|
|
|
1, 1, 2, 4, 9, 18, 44, 98, 244, 605, 1595, 4273, 12048, 34790, 104480, 322954, 1031556, 3389413, 11464454, 39820812, 141962355, 518663683, 1940341269, 7424565391, 29033121685, 115921101414, 472219204088, 1961177127371, 8298334192288, 35751364047676, 156736154469354
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
A set-system is a finite set of finite nonempty sets. The weight of a set-system is the sum of cardinalities of its elements.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
Non-isomorphic representatives of the a(4)=9 set-systems are:
((1234)),
((1)(234)), ((3)(123)), ((12)(34)), ((13)(23)),
((1)(2)(12)), ((1)(2)(34)), ((1)(3)(23)),
((1)(2)(3)(4)).
|
|
PROG
|
(PARI) \\ SetTypes function referenced by other sequences.
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}
V(n, w)={sumdiv(gcd(n, w), d, moebius(d)*binomial(n/d, w/d))/n}
S(n)={my(v=vector(n)); for(w=0, n, fordiv(gcd(n, w), d, v[n/d] += x^w*V(n/d, w/d))); v}
SetTypes(ptyp, fx)={
my(lim=sum(i=1, #ptyp, ptyp[i]), u=vector(lim, i, O(x*x^(lim\i)))); u[1] += 1;
for(i=1, #ptyp, my(s=S(ptyp[i]), v=vector(#u)); for(j=1, #u, for(k=1, #s, my(g=lcm(j, k)); if(g<=#v, v[g]+=u[j]*s[k]*j*k/g))); u=v);
u[1]-=1; Vec(sum(i=1, #u, subst(fx(u[i]), x, x^i)) + O(x*x^lim), -lim); }
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*WeighT(SetTypes(p, q->q))[n]); s/n!} \\ Andrew Howroyd, Sep 01 2019
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(0) = 1 prepended and terms a(11) and beyond from Andrew Howroyd, Sep 01 2019
|
|
STATUS
|
approved
|
|
|
|