[seqfan] Re: Extension of A005646

Andrew Weimholt andrew.weimholt at gmail.com
Sat Dec 19 19:01:03 CET 2009

On Sat, Dec 19, 2009 at 4:33 AM,  <franktaw at netscape.net> wrote:
> For n odd, you can avoid problems by always having the first part
> bigger than the second; but for even n this doesn't always work.  I
> assume that you are doing, at some point, permutation of the objects to
> see if two classifications are the same (presumably with
> optimizations); I think you have to try flipping any balanced binary
> partitions in that phase as well.  (There are of course optimizations
> to be made here; for example looking at the objects that occur alone,
> put more of these in the first part if possible.)

I represent the binary partitions as numbers with the bit positions
representing the type-specimens. The bit values 0 or 1 indicate
which partition a particular type-specimen belongs to. Each taxonomy
is then a list of numbers. I then permute the bit-positions,
to see if the original list of numbers was the lexigraphically earliest.
If it is, I increment my count, otherwise it is a duplicate of one
that has already been found.

> I would also like to see a triangle with T(n,k) being the number of
> classifications of n objects using k binary partitions.
> This starts:
> 1
> 0 1
> 0 0 1
> 0 0 1 2
> 0 0 0 3 3 (I think)
> 0 0 0 3 17 6 (from Andrew's list)

I'll modify my program to generate this triangle and send the results
a little later today.


More information about the SeqFan mailing list