login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A072446 Number of subsets S of the power set P{1,2,...,n} such that: {1}, {2},..., {n} are all elements of S; if X and Y are elements of S and X and Y have a nonempty intersection, then the union of X and Y is an element of S. 15
1, 2, 12, 420, 254076, 17199454920 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

From Gus Wiseman, Jul 31 2019: (Start)

If we define a connectedness system to be a set of finite nonempty sets (edges) that is closed under taking the union of any two overlapping edges, then a(n) is the number of connectedness systems on n vertices without singleton edges. The BII-numbers of these set-systems are given by A326873. The a(3) = 12 connectedness systems without singletons are:

  {}

  {{1,2}}

  {{1,3}}

  {{2,3}}

  {{1,2,3}}

  {{1,2},{1,2,3}}

  {{1,3},{1,2,3}}

  {{2,3},{1,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}}

(End)

LINKS

Table of n, a(n) for n=1..6.

Wim van Dam, Sub Power Set Sequences

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

FORMULA

a(n) = A326866(n)/2^n. - Gus Wiseman, Jul 31 2019

EXAMPLE

a(3)=12 because of the 12 sets:

{{1}, {2}, {3}};

{{1}, {2}, {3}, {1, 2}};

{{1}, {2}, {3}, {1, 3}};

{{1}, {2}, {3}, {2, 3}};

{{1}, {2}, {3}, {1, 2, 3}};

{{1}, {2}, {3}, {1, 2}, {1, 2, 3}};

{{1}, {2}, {3}, {1, 3}, {1, 2, 3}};

{{1}, {2}, {3}, {2, 3}, {1, 2, 3}};

{{1}, {2}, {3}, {1, 2}, {1, 3}, {1, 2, 3}};

{{1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}};

{{1}, {2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}};

{{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

MATHEMATICA

Table[Length[Select[Subsets[Subsets[Range[n], {2, n}]], SubsetQ[#, Union@@@Select[Tuples[#, 2], Intersection@@#!={}&]]&]], {n, 0, 3}] (* Gus Wiseman, Jul 31 2019 *)

CROSSREFS

The unlabeled case is A072444.

Exponential transform of A072447 (the connected case).

The case with singletons is A326866.

Binomial transform of A326877 (the covering case).

Cf. A102896, A306445, A326872, A326873.

Sequence in context: A051009 A324616 A060942 * A220113 A015181 A012378

Adjacent sequences:  A072443 A072444 A072445 * A072447 A072448 A072449

KEYWORD

nonn

AUTHOR

Wim van Dam (vandam(AT)cs.berkeley.edu), Jun 18 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 25 16:42 EST 2020. Contains 331245 sequences. (Running on oeis4.)