[seqfan] connectedness systems: the conjecture about A072447

[Christian Sievers]

Hello,

the entry of sequence

  A072447  Number of subsets S of the power set P{1,2,...,n} such that:
           {1}, {2},..., {n} are all elements of S; {1,2,...n} is an
           element 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
(let's call it a(n))

has a conjecture in its comment section that suggests it is

           the number of families of subsets of {1, ..., n} that
           contain both the universe and the empty set, are closed
           under intersection and contain no sets of cardinality n-1
(let's call this b(n)).

This conjecture is not true.

The first terms of a(n) are
1, 1, 8, 378, 252000, 18687534984 (last term by my computation, the
current entry says it's 17197930224),
while I found the first terms of b(n) to be
0 [sic!], 1, 8, 378, 241805, 16547569824.

(This sequence is not in the OEIS, and I see no particular reason why
it should be. The condition seems quite arbitrary.)

But it is not necessary to compute these numbers, it is possible to
change the definitions of the sequences so that it is obvious that
a(n)>b(n) for n>=5. It also explains the equality for 2<=n<=4.

The definition of A072447 doesn't talk about the empty set, but the
comments and examples make it clear that it is not allowed as element
of S. We could as well demand that is must be an element of S and get
the same sequence, because the empty set doesn't have nonempty
intersection with any set.

The singleton sets are also irrelevant to the rest of the condition:
a singleton and another set have either empty intersection, or their
union is the other set, so the condition is always satisfied.
So for each fixed set of singletons that we demand to be in S, we get
the same number of sets that satisfy the remaining conditions (unless
n=1 when the condition that the whole set must be in S gets in the
way.) That's why we have the formula a(n > 1) = A326868(n)/2^n.
So we can as well demand that that no singleton is in the set
(for n>1).

So for n>1, we can describe a(n) as

           the number of families of subsets of {1, ..., n} that
           contain both the universe and the empty set, are closed
           under union of nondisjoint sets and contain no singletons.

On the other hand, by applying the duality that replaces sets with
their complement and interchanges unions and intersections, b(n) can
be described as

           the number of families of subsets of {1, ..., n} that
           contain both the universe and the empty set, are closed
           under union and contain no singletons.

The only difference is that a(n) only demands closedness under union
for _nondisjoint_ sets, so clearly b(n)<=a(n).

To find a family that is counted by a(n) but not by b(n), we need to
find a pair of sets
  of size >=2
    (singletons are not allowed and the empty set does nothing)
  that are disjoint
    (else the difference doesn't show up)
  and whose union isn't the whole universe
    (because that is always contained in S).

So we need n>=5 and find that the family
  {{},{1,2},{3,4},{1,2,...,n}}
is counted by a(n) but not by b(n).


Should the conjecture in the OEIS entry be rejected by the numbers, the
simple but lengthy argument (how much can it be shortened?), both, or
is it an option to just delete it?


All the best
Christian