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

[Christian Sievers]

Hello!

On Sat, Oct 21, 2023 at 03:36:04PM -0400, Neil Sloane wrote:
> 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

I'm not sure that is the best way to proceed.
It would introduce a third style of definition for these type of
sequences. In my other mail I suggested to change them all to
"Number of ... connectedness systems ...".

This formulation was not meant as a suggestion for the definition,
it was only given for the comparision with the conjecture to refute
(I guess that is the word I wanted when I wrote "reject") it.

I also don't like that it needs a special case for n=1.

OTOH, the crossref section of A326868 calls this sequence "[t]he case
without singletons".

> file containing your email (slightly edited) as a comment.  I will try this

The linked text file contains something completely different.


All the best
Christian


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