[seqfan] Re: connectedness systems: the conjecture about A072447

[Neil Sloane]

Christian, Thank you for that comment!   I think the best way to handle
this is to change the definition to what you suggest, and to add a text
file containing your email (slightly edited) as a comment.  I will try this
right now - could you check in an hour or so to make sure it looks OK?
Best regards
Neil

Neil J. A. Sloane, Chairman, OEIS Foundation.
Also Visiting Scientist, Math. Dept., Rutgers University,
Email: njasloane at gmail.com



On Fri, Oct 20, 2023 at 11:08 AM Christian Sievers <seqfan at duvers.de> wrote:

> 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
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>