[seqfan] Re: Help wanted on A005646 connection to A000055

William Keith wjk26 at drexel.edu
Tue Dec 29 17:42:47 CET 2009

On Dec 29, 2009, at 6:21 AM, franktaw at netscape.net wrote:

> Looking at your web site, it appears that the size 6 line graph is
> mislabeled.  It should be f-d-b-a-c-e, not f-e-d-c-b-a.
> It feels like I can almost prove this, but the final result eludes me.
> It will suffice to prove that there must always (for R = N-1 > 0)  be
> one classification that distinguishes a single point.

I.e., any set of N-1 "questions" will have at least one item given a 
unique set of answers to the questions?  As long as all the questions 
are, in Rob's terminology, essential, this will be the case.

An equivalent definition of "essential" is that the number of sets of 
different answers given by all the items is different if one removes 
any question.  The first question will distinguish them into two such 
sets.  List them, A and B.  The next question must divide at least one 
of the two subsets, say wlog A, into C and D.  It might divide B as 
well, if it was efficient, but this need not be the case -- all items 
in B might yield the same response, so there would be only three sets 
of different answers yielded so far.  Regardless, we now have three or 
four subsets (if we have that many items).  The next question must 
divide at least one of these subsets, possibly two noncontiguous ones, 
but either way it will introduce a new divider.  (The first question 
adds one divider; each new question will introduce at least one and can 
introduce up to a number of dividers equal to the number of 
multi-element subsets that remain.)  Of course, by the Pigeonhole 
Principle there are only N-2 such dividers that can be placed before 
the next one classifies everything.  *Any* set of N-1 essential 
questions will be a complete classification.

William Keith

More information about the SeqFan mailing list