|
|
A330056
|
|
Number of set-systems with n vertices and no singletons or endpoints.
|
|
7
|
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
A set-system is a finite set of finite nonempty set of positive integers. A singleton is an edge of size 1. An endpoint is a vertex appearing only once (degree 1).
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{k=0..n} Sum_{j=0..floor(k/2)} Sum_{i=0..k-2*j} (-1)^k * binomial(n,k) * 2^(2^(n-k)-(n-k)-1) * binomial(k,i) * AS2(k-i, j) * (2^(n-k)-1)^i * 2^(j*(n-k)) where AS2(n,k) are the associated Stirling numbers of the 2nd kind (A008299). - Andrew Howroyd, Jan 16 2023
|
|
EXAMPLE
|
The a(3) = 6 set-systems:
{}
{{1,2},{1,3},{2,3}}
{{1,2},{1,3},{1,2,3}}
{{1,2},{2,3},{1,2,3}}
{{1,3},{2,3},{1,2,3}}
{{1,2},{1,3},{2,3},{1,2,3}}
|
|
MATHEMATICA
|
Table[Length[Select[Subsets[Subsets[Range[n], {2, n}]], Min@@Length/@Split[Sort[Join@@#]]>1&]], {n, 0, 4}]
|
|
PROG
|
(PARI) \\ Here AS2(n, k) is A008299 (associated Stirling of 2nd kind)
AS2(n, k) = {sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) )}
a(n) = {sum(k=0, n, (-1)^k*binomial(n, k)*2^(2^(n-k)-(n-k)-1) * sum(j=0, k\2, sum(i=0, k-2*j, binomial(k, i) * AS2(k-i, j) * (2^(n-k)-1)^i * 2^(j*(n-k)) )))} \\ Andrew Howroyd, Jan 16 2023
|
|
CROSSREFS
|
The version for non-isomorphic set-systems is A330055 (by weight).
Set-systems with no singletons are A016031.
Set-systems with no endpoints are A330059.
Non-isomorphic set-systems with no singletons are A306005 (by weight).
Non-isomorphic set-systems with no endpoints are A330054, (by weight).
Non-isomorphic set-systems counted by vertices are A000612.
Non-isomorphic set-systems counted by weight are A283877.
Cf. A007716, A055621, A008299, A302545, A317533, A317794, A319559, A320665, A321405, A330052, A330058.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|