[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