[seqfan] Re: connectedness systems: the conjecture about A072447
Neil Sloane
njasloane at gmail.com
Sun Oct 22 21:57:05 CEST 2023
Dear Christian, I apologize for uploading the wrong file. I have now
replaced it with the correct file, just so you can see what I wrote.
I certainly don't insist that this is the way to proceed. I was just
trying to do what you suggested. Obviously I misread your message.
May I suggest that you take over the editing of this sequence, and make any
changes that you think are appropriate?
If you think the best way to proceed is to have two (or even three)
sequences, then please go ahead and propose them.
Send me an email when you have made the changes. (I am in the middle of
several urgent projects, with deadlines coming up, so I have less time than
usual for monitoring the submissions.)
Best regards
Neil
Neil J. A. Sloane, Chairman, OEIS Foundation.
Also Visiting Scientist, Math. Dept., Rutgers University,
Email: njasloane at gmail.com
On Sat, Oct 21, 2023 at 10:29 PM Christian Sievers <seqfan at duvers.de> wrote:
> 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/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
More information about the SeqFan
mailing list