Sequence A005646, Classifications of N Elements
This sequence, Sloane's A005646, counts something called "taxonomies" or "classifications".
Contents :
Concrete Examples
Requirements
Compact Representation
Computing the Sequence
The Inductive Algorithm
Table of All Known Results by N and R
Relation to tree graphs
Footnotes
Appendix A: The 122 classifications for N=7
Here is the formal (and rather terse1) definition given by Wexler [9]:
"A 'classification' is a set of n type-specimens each one of which is corralled on its own by the union of a set of binary partitions, none of which could be omitted without leaving 2 types unseparated."
The sequence begins: 1, 1, 1, 3, 6, 26, 122, 1015, 11847, 208914, 5236991, 184321511, ...
I was the first to compute the terms 208914, 5236991, and 184321511, the last taking 4.5 days on an 8-core Nehalem workstation.
Concrete Example for N=4
You are playing a game like "20 questions", and you are told in advance that the mystery object is an animal, and furthermore that it is either: A frog, a bear, a dove, or a bat. You need to devise a set of yes/no questions that can be used to figure out which animal it is.
Here are three different sets of questions that accomplish this:
|
Each of these examples is a distinct classification for 4 items.
In each case, the set of questions is sufficient to distinguish between the 4 possibilities, and none of the questions is redundant.
- The first example has three questions, each of which gives a Yes for one of the items and a No for the other three, or vice-versa (a "single elimination question" because the item with the unique answer is eliminated by asking the question)
- The second example has one question that is a Yes for two of the items and No for the other two (an "even split" question), plus two questions each of which is a "single elimination question", and for which one of the eliminated items is from the first question's Yes group and the other is from the first question's No group.
- The third example uses two "even split" questions, and exactly one item that is a Yes to both.
Any set of questions that fits one of these three descriptions is a "classification" of 4 items, for the purposes of sequence A005646. You don't need to use the most "efficient" set of questions (which would be the two-question example), just as long as none of the questions is redundant. There are only three distinct ways to do this: three 1-out-of-4 elimination questions, one 2-2 split and two elimination questions, or two even splits.
Each question, which gives a Yes answer for some of the items and a No answer for the others, is a "binary partition" because it "partitions" the items into two groups.
Requirements, Definition of a "Classification"
In all three examples, there is a set of questions that can definitively distinguish which item one is talking about. Furthermore, all the questions are necessary — if any question were removed, the other questions in that set would not be enough.
Equivalent Classifications
Two classification systems are considered equivalent if:
- you rename or reorder the items provided this doesn't change the question answers;
- you re-order the questions;
- you change a question in any way that either gives the same answers for everything or that gives the opposite answer for everything.
To illustrate this last point, the following three questions are interchangeable (provided that we're limiting the possibilities to the 4 animals above):
Is it a bear? (original question)
Does it have big paws? (same answer for all 4 items)
Could you hold it in your hand? (opposite answer for all 4 items)
Here is another example. If we take the third classification above and change the second question to "Does it lay eggs?", we get this:
|
This looks like a different classification system because the pattern of Y's is different. However we can make it the same just by rearranging the columns:
|
Limits: Minimum and Maximum Number of Questions (Partitions)
It is relatively easy to see that one question is enough when N=2, but not for higher N.
For N=3, you need two questions, and that's always enough.
For N=4, as just illustrated, you might need 2 or 3 questions depending on how you choose them.
For N=5, two questions is no longer enough no matter what you do — you must use at least 3. However you might need 4 questions (if each is only sufficient to rule out one possibility).
In general it is fairly easy to see that the number of questions must be at least log2(P) where P is N or the next higher power of 2 when N is not a power of 2; and the number of questions might be as many as N-1. Stated a little more precisely:
ceil(log2(N)) ≤ R ≤ N-1
Here ceil represents the "ceiling function", which returns the next higher integer whenever its argument has a fractional part. So for example, when N=5, log2(N) is about 2.32, and ceil(log2(N)) is 3. Combining this with N-1=4 we get 3≤R≤4, which means the number of rows (questions) is either 3 or 4.
Compact Representation
Since the specific object names and question texts are arbitrary, one can identify each classification system with a rectangular grid of N columns and R rows, where R is the number of questions (partitions). Each cell is blank or contains a *; internally this is represented as 0 or 1 respectively. The rows and columns are simply labeled with numbers starting at 0. For reasons related to the computing algorithm the rightmost row is row 0. Below each pattern is an equivalent representation as a set of hexadecimal digits, attained by interpreting each row as a binary number.
The one classification The one classification for N = 2 : for N = 3 : 1 0 2 1 0 0 * 0 * (1) 1 * (12) The 3 classifications for N = 4 : 3 2 1 0 3 2 1 0 3 2 1 0 0 * 0 * 0 * * 1 * 1 * 1 * * 2 * 2 * * (35) (124) (125)(Notice the three patterns for N=4 have their *'s arranged the same way as the Y's in the original three examples above.)
The 6 classifications for N = 5 : 4 3 2 1 0 4 3 2 1 0 4 3 2 1 0 0 * * 0 * 0 * * 1 * * 1 * * 1 * * 2 * * 2 * * 2 * * (35a) (16a) (359) 4 3 2 1 0 4 3 2 1 0 4 3 2 1 0 0 * 0 * 0 * 1 * 1 * 1 * 2 * 2 * * 2 * 3 * 3 * * 3 * * (1248) (125a) (1249) The 26 classifications for N = 6 :three with 3 rows: 5 4 3 2 1 0 5 4 3 2 1 0 5 4 3 2 1 0 0 * * 0 * * 0 * * * 1 * * 1 * * * 1 * * * 2 * * * 2 * * * 2 * * * (3-c-15) (3-d-15) (7-b-15) seventeen with 4 rows: 5 4 3 2 1 0 5 4 3 2 1 0 5 4 3 2 1 0 5 4 3 2 1 0 5 4 3 2 1 0 5 4 3 2 1 0 0 * * 0 * * 0 * * 0 * * 0 * * 0 * * 1 * * 1 * * 1 * * 1 * * 1 * * 1 * * 2 * * 2 * * 2 * * 2 * * 2 * * 2 * * * 3 * * 3 * * 3 * * * 3 * * 3 * * * 3 * * * (3-5-9-11) (3-5-9-12) (3-5-9-13) (3-5-a-14) (3-5-a-15) (3-5-b-15) 5 4 3 2 1 0 5 4 3 2 1 0 5 4 3 2 1 0 5 4 3 2 1 0 5 4 3 2 1 0 5 4 3 2 1 0 0 * * 0 * 0 * 0 * 0 * 0 * 1 * * 1 * * 1 * * 1 * * 1 * * 1 * * 2 * * 2 * * 2 * * 2 * * 2 * * 2 * * 3 * * * * 3 * * 3 * * 3 * * 3 * * * 3 * * * (3-5-18-f) (1-3-c-14) (1-6-a-12) (1-6-a-14) (1-6-a-13) (1-6-a-15) 5 4 3 2 1 0 5 4 3 2 1 0 5 4 3 2 1 0 5 4 3 2 1 0 5 4 3 2 1 0 0 * 0 * 0 * 0 * 0 * 1 * * 1 * * * 1 * 1 * 1 * 2 * * * 2 * * * 2 * * 2 * * 2 * * * 3 * * * 3 * * * 3 * * 3 * * * 3 * * * (1-6-b-16) (1-7-b-13) (1-2-c-14) (1-2-c-15) (1-2-d-15) six with 5 rows: 5 4 3 2 1 0 5 4 3 2 1 0 5 4 3 2 1 0 5 4 3 2 1 0 5 4 3 2 1 0 5 4 3 2 1 0 0 * 0 * 0 * 0 * 0 * 0 * 1 * 1 * 1 * 1 * 1 * 1 * 2 * * 2 * 2 * 2 * 2 * 2 * 3 * * 3 * * 3 * * 3 * 3 * 3 * 4 * * * 4 * * 4 * * * 4 * * 4 * * * 4 * (1-2-5-a-15) (1-2-4-9-12) (1-2-4-9-16) (1-2-4-8-11) (1-2-4-8-13) (1-2-4-8-10)
The 122 classifications for N=7 are given in appendix A.
Computing the Sequence
To discover the number of classifications for a given N without any other knowledge, one would consider all possible grids that have N columns and a suitable number of rows (ranging from ceil(log2N) to N-1, as described above). Since each grid position has two possible values, the number of combinations increases very quickly. For example, for N=6 with 4 rows, there are 24×6 = 224 = 16777216 possible grids.
Given the above equivalence rules (see "Equivalent Classifications" above), the number of grids can be decreased a bit: it is okay to assume that one column (say the leftmost) is all 0's (corresponding to an item that gives No answers to all questions) — because if not, you can just replace one or more of the questions with a question that gives the opposite answer for everything, thereby making the answer No in the left column.
It is also okay to consider only those grid patterns in which each row, treated as a binary number, is "greater" than the row above it. Another type of ordering could be used, such as arranging the rows by how many Yes answers they have, then by the position of the first Yes within the row. Such a canonical ordering is acceptable because rearranging the rows has no impact on whether a grid is considered to be the "same classification".
For a grid to be a valid classification, the following criteria must be met:
- Each column differs from every other column. (The column represents the answers to all the questions for an item. If two columns were the same, those two items would have the same answers for all the questions, so the set of questions would not be sufficient to distinguish between those two items.)
- Each row is different from every other row. (Similarly, two identical rows would mean there are two questions that are equivalent. Each question must be essential.)
- No row is the same as another row with all values changed to the opposite value. (A question that gives all opposite answers is also equivalent.)
- More generally, every row must be essential, in that if any row were removed, there would end up being two identical columns somewhere. (It is possible to have three questions in which no two are equivalent but any set of two is equivalent to any other set of two. This type of situation is not allowed. All classifications consist of a minumum sufficient set of questions, and no more.)
Equivalent Grids
After a grid is tested to see if it meets these criteria, the job is only partly complete. All valid grids must be compared to each other to see if they are equivalent. Grids are equivalent if you can change one to the other by reordering rows, reordering columns, and possibly replacing one or more rows with its "complement" (opposite value in all positions).
Here are some examples of pairs of patterns that are equivalent:
-oc2 -oc3 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * 1 * * 1 * * 2 * * * 2 * * * 3 * * 3 * * * * * 4 * * 4 * * * * * (1-3-7-18-28) (1-3-7-1F-2F)To transform the first into the second, reverse the order of columns 6, 5, 4 and 3, and then flip the bits in rows 3 and 4.
-oc3 canon 5 4 3 2 1 0 5 4 3 2 1 0 0 * * 0 * * 1 * * 1 * * 2 * * * * 2 * * 3 * * * * 3 * * * * (3-5-f-17) (3-5-18-f)
To transform the first into the second, move columns 5, 4, and 3 so they become columns 4, 3, and 5 respectively, then flip the bits in row 2.
Here is the canonical ordering I use. Two patterns are to be compared to determine which comes "before" the other.
- If the number of columns differs, the one with fewer columns comes first.
otherwise (if both patterns have the same number of columns):
- If the number of rows differs, the one with fewer rows comes first.
otherwise (if both patterns have the same number of columns and rows):
- Compare the bits in the leftmost column, starting from the top and moving down. Find the first bit-position that differs. The pattern with a 0 bit in that bit-position is the pattern that comes first.
otherwise (same number of columns and rows, and leftmost columns are identical):
- Count the number of 1 bits (the bitcount) of each row. Find the first row for which the bitcount differs. The pattern with a lower bitcount in that row is the pattern that comes first.
otherwise (same number of columns and rows, leftmost columns are identical, and the rows' bitcounts are all identical):
- Interpret each row as a binary number with the leftmost 0 or 1 bit as the most-significant bit. Find the first row for which the value differs. The pattern with a lower value in that row is the pattern that comes first.
otherwise (all above conditions are met, and all rows are identical)
- The patterns are identical.
Implementation Benchmarks
Using the technique of generating and testing all possible grids, with minimal optimizations allowed by the validity criteria, the values for N=6 through N=8 took the following amounts of time on a modern Intel processor (Xeon Nehalem) running in a single thread:
N=6: 26 classifications. 0.026 sec
N=7: 122 classifications. 12.36 sec
N=8: 1015 classifications. 7 hours
The calculation time increases so quickly because of the exponentially increasing number of grids. For N=8 there are 256≈7.2×1016 grids of size 8×7 to consider. For N=10 the number of grids would be 290≈1.2×1027, but fortunately there are ways to avoid this (discussed below).
Inductive Algorithm
If all classifications for a given N are known, it is considerably easier to find the classifications for the next higher N. To see this, consider the following proposition:
Proposition. Given any valid classification of N columns (items) and R rows (questions): by deleting any one column, and possibly also one now-redundant row, it is always possible to produce a valid classification of N-1 items and R rows (if just the column was removed), or a valid classification of N-1 items and R-1 rows (if both a column and a row was removed).
Discussion. Let us remove the Nth column. There remain N-1 columns representing N-1 items, and the rows represent the answers to the R questions for those N-1 items. Since those R questions were enough to classify the original set of N items, clearly they are enough to distinguish the N-1 items that now remain.
After removing the one item (column) there may be more questions than are needed. (As discussed earlier, this will always be the case when N-1=R.) If this is the case, a set of R-1 questions will be sufficient, and all R-1 questions will then be essential.
Assertion : In the instance that the R rows are more than is needed,
there will be at most one row that needs to be removed to create a valid
classification. There cannot be two redundant rows (questions).
Proof : Suppose it were true that 2 or more rows need to be
deleted. That would imply that R-2 questions are sufficient to distinguish
between the N-1 items. But we started with the assumption that the
original R rows and N columns represent a valid classification, which
means that all R original rows are needed to distinguish between N items.
That would mean that after distinguishing between the N-1 items with
R-2 questions, you would need to ask two more questions to distinguish
between a member of that set of N-1 items and the single new item —
but clearly only one question is needed to do that ("Q. Is it the
new item?").
Thus, the hypothesis that R-2 rows could form an unambiguous
classification cannot be true.
The original proposition is thereby proven. (For a similar proof regarding another "hard" counting problem, see my A181785 page.)
Since every classification of N items yields a classification of N-1 items by removing a column and possibly a row, it follows that all valid classifications with N items can be found by reversing the process: by starting with all classifications of N-1 items and by considering all possible ways to add an Nth column along with possibly one additional row. After doing this one must still shuffle the rows and columns in different ways and compare, using a canonical ordering method or some other technique, to avoid counting equivalent classifications twice.
In practice, this method dramatically reduces the number of cases that need to be tested. For example, starting with the 26 classifications for N=6, this method creates 33008 seed patterns that need to be tested to discover the 122 classifications for N=7. The algorithm discussed earlier needed to consider 45971150 seed patterns.
Using this method to build on the results for an existing N, to create the N+1 results, means that each N is computable in only slightly more time than that taken for N-1 in the unoptimized version above. My measurements are (again, in a single thread on an Intel Xeon processor):
N=6: 26 classifications. 0.013 sec
N=7: 122 classifications. 0.235 sec
N=8: 1015 classifications. 15.5 sec
N=9: 11847 classifications. 8 hours
Better still, the method can be applied iteratively, starting with a very small N and working up to each higher N one step at a time. The compute times drop dramatically, with an N=10 time of less than 5% of the original N=8 time:
N=6: 26 classifications. 0.010 sec
N=7: 122 classifications. 0.153 sec
N=8: 1015 classifications. 2.14 sec
N=9: 11847 classifications. 48.1 sec
N=10: 208914 classifications. 22.3 min
N=11: 5236991 classifications. 14.9 hours
For larger N, it is useful to split the work up amongst multiple processing threads to compute results in parallel. Each thread performs the entire calculation up to N-1, and then only derives classifications for N from its fraction of those results; the output of the threads is then merged together. On an 8-core Nehalem workstation, using 16 threads that is each running at about 2/3 full clock speed as compared to all of the above times, I measured these times:
N=9: 11847 classifications. 7.5 sec
N=10: 208914 classifications. 2 min 59 sec
N=11: 5236991 classifications. 1 hour 46 min
Of course, it makes sense to parallelize each step rather than just the last. If there are 16 threads, and the results for N-1 are getting calculated 16 times, that is enough to make a big difference in the total time. Here are the results from parallelizing both the N-1 and N steps:
N=9: 11847 classifications. 5.8 sec
N=10: 208914 classifications. 2 min 4 sec
N=11: 5236991 classifications. 1 hour 21.9 min
Table of All Known Results for Each N and R
This table shows the number of classifications broken down by the height and width of the grid (the height is the number of rows, each representing a binary partition or a "question"; the width is the number of columns, each representing an item in the set being classified). Empty positions in the lower-right are not yet known.
Note that for N=1, no questions at all are needed to distinguish which item you're talking about, and any question would be redundant — so the only possible classification is the null set with 0 partitions (R=0).
|
I call this table Franklin's Triangle because an interest in it was first expressed6 by Franklin T. Adams-Watters on the seqfan list.
The sum of the numbers in each row of the triangle is the total number of classifications for N. For example, A005646[6] = 26 = 3 + 17 + 6.
The column sums form the new sequence A171873: 1, 1, 2, 10, 280, 1173468, ... with the next term being greater than 220146725295227. This sequence grows faster than the already-formidable A3047.
Relation to Tree Graphs
The rightmost term in each row of Franklin's Triangle forms sequence A000055, which counts unlabeled free (unrooted) tree (connected acyclic) graphs: 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, 7741, ...
The following diagram illustrates this relationship for N=2 through N=7. The classifications are shown as grids of rows and columns; next to each grid is the corresponding graph. A graph edge corresponds to a row (binary partition or "question"), and each node is one of the columns (objects or "types") in the classification. Each edge connects two subgraphs, and the corresponding question/partition divides the types in the same way that the graph would be divided if that edge were removed. (Removing an edge separates the graph into two subgraphs.)
N = 2 : a b 0 0 * b-----a (1) N = 3 : a b c 1 0 0 * b---a---c 1 * (12) N = 4 : a b c d a b c d c 0 * 0 2 1 0 * 1| 1 * d---b---a---c 1 * b---a---d 2 * * 2 * 2 0 (125) (124) N = 5 : a b c d e a b c d e a b c d e 0 * c 0 * 0 * 1 * 3 |2 1 * 1 * c 2 * b---a---d 2 * * d-b-a-c-e 2 * |2 3 * 0| 1 3 * * 1 3 2 0 3 * * e--b--a--d (1248) e (125a) (1249) 0 3 1 N = 6 : a b c d e f a b c d e f a b c d e f 0 * 0 * d 0 * e 1 * 1 * |2 1 * /1 2 * * f-d-b-a-c-e 2 * f-c-a-b-e 2 * f--c--a--b 3 * * 0 2 4 3 1 3 * * 0 3 4 1 3 * * 0 3 4 \2 4 * * * 4 * * 4 * * * d (1-2-5-a-15) (1-2-4-9-12) (1-2-4-9-16) a b c d e f a b c d e f a b c d e f 0 * c 0 * d e 0 * f edges are 1 * |3 1 * 2\ /1 1 * | 0,1,2,3,4 2 * f-0-b-4-a-2-d 2 * a-4-b 2 * b--a--e (clockwise 3 * |1 3 * 3/ \0 3 * / \ from top) 4 * * e 4 * * * c f 4 * c d (1-2-4-8-11) (1-2-4-8-13) (1-2-4-8-10) N = 7 :a b c d e f g a b c d e f g f a b c d e f g 0 * 0 * 1/ 0 * f 1 * 1 * c 1 * 1| 2 * * f-d-b-a-c-e-g 2 * 4/ 2 * c 3 * * 1 3 5 4 2 0 3 * * e---b---a 3 * * 4| 4 * * * 4 * * 2 5 \3 4 * * e---a---b---d---g 5 * * * 5 * * d 5 * * * 2 5 3 0 (1-2-5-a-15-2a) (1-2-4-9-12-24) \0 (1-2-4-9-12-29) g a b c d e f g a b c d e f g a b c d e f g 0 * 0 * 0 * 1 * e 1 * d 1 * g d 2 * /2 2 * 3| 2 2 * 0\ /3 3 * * g--d--b--a--c 3 * g---c---a---b---e 3 * c--a--b 4 * * * 0 3 5 4 \1 4 * * 0 4 5 |1 4 * * * 1/ 4 5 \2 5 * * * f 5 * * * * f 5 * * * f e (1-2-4-9-16-29) (1-2-4-8-11-2e) (1-2-4-8-13-2c) a b c d e f g a b c d e f g a b c d e f g c d 0 * d 0 * e 0 * 4\ /3 1 * 3| 1 * |2 1 * \ / 2 * g-0-c-4-a-5-b-1-f 2 * g-0-c-4-a-5-b-1-f 2 * g-0-b-5-a-2-e 3 * |2 3 * 3| 3 * |1 4 * * e 4 * * d 4 * f 5 * * 5 * * * 5 * * (1-2-4-8-11-22) (1-2-4-8-11-26) (1-2-4-8-10-21) a b c d e f g a b c d e f g b c 0 * g c 0 * 5\ /4 1 * 0\ 4| 1 * \ / 2 * b-5-a-3-d 2 * g-0-a-3-d 3 * 1/ |2 3 * / \ 4 * f e 4 * 1/ \2 5 * * * 5 * f e (1-2-4-8-10-23) (1-2-4-8-10-20)
A clearer image of the trees themselves (without the labels) can be seen here. Note that these labels are arbitrary and sometimes interchangeable. (For example, in the first N=5 classification, with a graph that looks like a plus sign, the letters b, c, d and e could be in any order around the circle, so long as their labels 3, 2, 1 and 0 (respectively) go with them.)
Some patterns3 can be seen: any row that has only one * in it corresponds to an edge that has just one node at one end and the rest of the tree attached to its other end.
Some higher-level patterns: when the tree is a star graph, the grid is a single diagonal line; when the tree is nonbranching, the grid is an empty triangle plus an equal-sized triangle filled with a checkerboard pattern.
Partial Support for this Connection
Suppose we have a classification with N items and R=N-1 rows. This number of rows is maximal, in that this is the most number of rows you could possibly need for this value of N.
By the induction principle (see the "Inductive Algorithm" description above) we know that we can remove one column and one row to obtain a maximal classification with N-1 items. We can then remove another column and row to get a maximal classification with N-2 items, and so on all the way down to the null classification with 1 item and 0 rows. (In practice, this is what I did to figure out the graph for each grid in the figure above).
While the foregoing supports the connection between classifications and trees, it does not prove the existence of a one-to-one correspondence.2
Footnotes
1 : terse definition : This definition is all I had to go on when I started, and from it I derived all the algorithms used to produce the results given here. The definition, although terse, was complete, accurate, unambiguous, and just barely comprehensible enough. Mathematicians spend an inordinate amount of time and effort making their communication as brief as possible, at the expense of clarity. See Munafo's First Law of Mathematics.
2 : tree correspondence : In late December 2009, I asked for help on this from seqfan and within a couple days, it was proven by Andrew Weimholt and Franklin T. Adams-Watters.
3 : grid patterns : Various patterns seen in the grid representations result from how the grid rows and columns are ordered. The grids in all figures in this article use the arrangement that produces the lowest possible binary string c0r0c1r1...ciri where the ci's count the number of 1-bits in each row and the ri's are the rows themselves. This results from my canonical ordering scheme as described above. Other consistent schemes would yield other types of patterns.
4 : A034190 connection : For the 5th column in the triangle, N≥17, the terms are the same as the last 16 terms in A034190 (or the first 16 terms of that sequence, in reverse order). Note that the last 8 terms in the 4th column are found in A034189, and if you're into graph theory, you might enjoy looking for a homeomorphism5 between the subject of this article and the problems described by A034189, A034190, and/or A039754. Andrew Weimholt has explained it in terms of 2-coloring vertices of an R-dimensional hypercube.
5 : homeomorphism : A fancy word (which I am deliberately misusing) for a common experience in academic work: Show me how to solve a complex problem, and I'll show you how to solve another problem that is actually identical to the first but seems completely different because my jargon and illustrations are completely different! This is one of the reasons why OEIS is so useful.
6 : Franklin's Triangle : Here was the original message:
Date: Sat, 19 Dec 2009 07:33:26 -0500 From: "Franklin T. Adams-Watters" <frank...(at)...> Subject: [seqfan] Re: Extension of A005646 To: seqfan@list.seqfan.eu [...] 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) Franklin T. Adams-Watters
Compare this little triangle to the current version. From these humble beginnings came the A000055 and A039754 conjectures, and all the rest.
7 : A000055 connection : See this section.
References
[8] P. J. Wexler, On the number of taxonomies; or the odds on 'structuralism', American Anthropologist 73 (1971), p. 1258.
[9] P. J. Wexler and D. H. Fremlin, The number of classifications of up to seven classificands, Classification Society Bulletin 4 (No. 3, 1979), pp. 2-4.
[10] Neil J.A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press (1995), ISBN 0-12-558630-2.
[11] Franklin T. Adams-Watters, personal communication, December 2009.
[12] Andrew Weimholt, personal communication, December 2009.
See Also
I have pages about Fibonacci-like sequences, classical sequences, and many more from OEIS that I have worked on.
See also my numbers and large numbers pages.
Appendix A: Taxonomies for N=7
Here are the 122 classifications for N=7. They are grouped by the number of rows, as in the illustrations of N=2 through N=6 above. There is one 3-row classification, 36 with 4 rows, 74 with 5 rows and 11 with 6 rows.
The 122 classifications for N = 7 :one with 3 rows: 6 5 4 3 2 1 0 0 * * * 1 * * * 2 * * * (7-19-2a) 36 with 4 rows: 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * * 0 * * 0 * * 0 * * 0 * * 1 * * 1 * * 1 * * 1 * * 1 * * * 1 * * * 2 * * 2 * * 2 * * * 2 * * * 2 * * * 2 * * * 3 * * * 3 * * 3 * * * 3 * * * 3 * * * 3 * * * * (1-6-18-2a) (3-5-18-28) (3-5-1a-2c) (3-c-15-31) (3-d-15-29) (3-d-32-17) 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * * 0 * * 0 * * 0 * * 0 * * 1 * * 1 * * 1 * * * 1 * * 1 * * * 1 * * * 2 * * * 2 * * 2 * * * 2 * * * 2 * * * 2 * * * 3 * * * 3 * * * 3 * * * 3 * * * 3 * * * 3 * * * * (1-6-19-2a) (3-5-18-29) (3-7-19-29) (3-c-15-32) (3-d-15-2a) (3-d-34-1b) 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * * 0 * * 0 * * 0 * * 0 * * * 1 * * 1 * * 1 * * 1 * * 1 * * * 1 * * * 2 * * * 2 * * 2 * * * 2 * * 2 * * * 2 * * * 3 * * * 3 * * * 3 * * * 3 * * * 3 * * * 3 * * * (1-6-1a-2a) (3-5-18-2a) (3-c-13-25) (3-c-30-15) (3-d-15-2c) (7-b-13-25) 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * * 0 * * 0 * * 0 * * 0 * * * 1 * * 1 * * 1 * * 1 * * 1 * * * 1 * * * 2 * * * 2 * * * 2 * * * 2 * * * 2 * * * 2 * * * 3 * * * 3 * * * 3 * * * 3 * * * * 3 * * * 3 * * * (1-6-1a-2c) (3-5-19-29) (3-c-15-25) (3-c-31-17) (3-d-15-38) (7-b-15-29) 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * * 0 * * 0 * * 0 * * 0 * * * 1 * * * 1 * * 1 * * 1 * * * 1 * * * 1 * * * 2 * * * 2 * * * 2 * * * 2 * * * 2 * * * 2 * * * 3 * * * 3 * * * 3 * * * 3 * * * 3 * * * 3 * * * (1-7-1a-2a) (3-5-19-2a) (3-c-15-26) (3-d-15-25) (3-d-16-2c) (7-b-15-2a) 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * * 0 * * 0 * * 0 * * 0 * * * 1 * * * 1 * * 1 * * 1 * * * 1 * * * 1 * * * 2 * * * 2 * * * 2 * * * 2 * * * 2 * * * 2 * * * 3 * * * 3 * * * 3 * * * 3 * * * 3 * * * 3 * * * * (1-e-16-2a) (3-5-1a-2a) (3-c-15-2a) (3-d-15-26) (3-d-1c-34) (7-b-31-1e) 74 with 5 rows: 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * 0 * 0 * 0 * 0 * * 1 * 1 * * 1 * 1 * * 1 * * 1 * * 2 * 2 * * 2 * * 2 * * * 2 * * 2 * * 3 * * 3 * * * 3 * * 3 * * * 3 * * 3 * * 4 * * 4 * * * 4 * * * 4 * * * 4 * * 4 * * * (1-2-4-18-28) (1-6-a-13-26) (1-2-c-14-38) (1-6-b-16-29) (1-3-c-14-24) (3-5-9-12-25) 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * 0 * 0 * 0 * 0 * * 1 * 1 * * 1 * 1 * * 1 * * 1 * * 2 * 2 * * 2 * * 2 * * * 2 * * 2 * * 3 * * 3 * * * 3 * * * 3 * * * 3 * * 3 * * 4 * * * 4 * * * 4 * * * 4 * * * 4 * * 4 * * * (1-2-4-18-29) (1-6-a-13-2c) (1-2-c-15-26) (1-6-b-16-34) (1-3-c-14-28) (3-5-9-12-2c) 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * 0 * 0 * 0 * 0 * * 1 * 1 * * 1 * 1 * * 1 * * 1 * * 2 * 2 * * 2 * * 2 * * * 2 * * 2 * * 3 * * * 3 * * * 3 * * * 3 * * * 3 * * 3 * * 4 * * * 4 * * * 4 * * * 4 * * * 4 * * * 4 * * * (1-2-4-19-29) (1-6-a-13-31) (1-2-c-15-2a) (1-6-b-19-29) (1-3-c-14-2c) (3-5-9-12-32) 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * 0 * 0 * 0 * 0 * * 1 * 1 * * 1 * 1 * * 1 * * 1 * * 2 * 2 * * 2 * * 2 * * 2 * * 2 * * 3 * * * 3 * * 3 * * * 3 * * * 3 * * 3 * * * 4 * * * 4 * * * 4 * * * 4 * * * 4 * * * 4 * * * (1-2-4-19-2a) (1-6-a-14-23) (1-2-c-15-2c) (1-6-18-23-29) (1-3-c-14-38) (3-5-9-13-25) 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * 0 * 0 * 0 * 0 * * 1 * 1 * * 1 * 1 * * * 1 * * 1 * * 2 * * 2 * * 2 * * 2 * * * 2 * * 2 * * 3 * * 3 * * 3 * * * 3 * * * 3 * * * 3 * * * 4 * * 4 * * 4 * * * 4 * * * 4 * * * 4 * * * (1-2-5-18-28) (1-6-a-14-28) (1-2-c-15-31) (1-7-b-13-23) (1-3-c-1c-34) (3-5-9-13-2c) 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * 0 * 0 * 0 * 0 * * 1 * 1 * * 1 * 1 * * * 1 * * 1 * * 2 * * 2 * * 2 * * 2 * * * 2 * * * 2 * * 3 * * 3 * * 3 * * * 3 * * * 3 * * * 3 * * * 4 * * * 4 * * * 4 * * * 4 * * * 4 * * * 4 * * * (1-2-5-18-2a) (1-6-a-14-29) (1-2-c-1c-34) (1-7-b-13-2c) (1-3-1c-2c-34) (3-5-9-13-32) 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * 0 * 0 * 0 * 0 * * 1 * 1 * * 1 * 1 * * * 1 * * 1 * * 2 * * 2 * * 2 * * * 2 * * * 2 * * 2 * * 3 * * * 3 * * 3 * * * 3 * * * 3 * * 3 * * 4 * * * 4 * * * 4 * * * 4 * * * * 4 * * 4 * * * (1-2-5-1a-2a) (1-6-a-14-2a) (1-2-d-15-25) (1-7-b-34-17) (1-6-a-12-22) (3-5-a-14-2a) 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * 0 * 0 * * 0 * 0 * * 1 * 1 * * 1 * 1 * * 1 * * 1 * * 2 * * 2 * * 2 * * * 2 * * 2 * * 2 * * 3 * * 3 * * * 3 * * * 3 * * 3 * * 3 * * * 4 * * * 4 * * * 4 * * * 4 * * 4 * * * 4 * * * (1-2-c-14-23) (1-6-a-15-2a) (1-2-d-15-2a) (3-5-9-11-21) (1-6-a-12-23) (3-5-a-15-2a) 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * 0 * 0 * * 0 * 0 * * 1 * 1 * * 1 * 1 * * 1 * * 1 * * 2 * * 2 * * 2 * * * 2 * * 2 * * 2 * * 3 * * 3 * * * 3 * * * 3 * * 3 * * 3 * * * 4 * * 4 * * * 4 * * * 4 * * 4 * * 4 * * * (1-2-c-14-24) (1-6-a-15-31) (1-2-d-15-38) (3-5-9-11-22) (1-6-a-12-24) (3-5-a-15-34) 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * 0 * 0 * * 0 * 0 * * 1 * 1 * * 1 * 1 * * 1 * * 1 * * 2 * * 2 * * 2 * * * 2 * * 2 * * 2 * * * 3 * * 3 * * * 3 * * * 3 * * 3 * * 3 * * * 4 * * * 4 * * * 4 * * * * 4 * * * 4 * * * 4 * * * (1-2-c-14-25) (1-6-a-16-2a) (1-2-d-32-17) (3-5-9-11-23) (1-6-a-12-25) (3-5-b-15-2a) 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * 0 * 0 * * 0 * 0 * * 1 * 1 * * 1 * 1 * * 1 * * 1 * * 2 * * 2 * * 2 * * * 2 * * 2 * * 2 * * 3 * * 3 * * * 3 * * * 3 * * 3 * * 3 * * * 4 * * 4 * * * 4 * * * 4 * * * 4 * * * 4 * * * * (1-2-c-14-28) (1-6-a-16-34) (1-2-1c-2c-34) (3-5-9-11-26) (1-6-a-12-26) (3-5-18-38-f) 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * 0 * 0 * * 0 * 0 * * 1 * 1 * * 1 * * 1 * * 1 * * 1 * * 2 * * 2 * * 2 * * 2 * * 2 * * 2 * * * 3 * * 3 * * 3 * * 3 * * 3 * * 3 * * * * 4 * * * 4 * * * * 4 * * * 4 * * 4 * * * 4 * * * * (1-2-c-14-29) (1-6-a-30-1e) (1-3-c-14-23) (3-5-9-12-24) (1-6-a-12-2c) (3-5-38-f-17) 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * 1 * 1 * * 2 * * 2 * * 3 * * 3 * * * 4 * * * 4 * * * * (1-2-c-14-2c) (1-6-a-31-1e) 11 with 6 rows: 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * 0 * 0 * 0 * 0 * 1 * 1 * 1 * 1 * 1 * 1 * 2 * 2 * 2 * 2 * 2 * 2 * * 3 * 3 * 3 * 3 * * 3 * 3 * * 4 * 4 * * * 4 * 4 * * 4 * * 4 * * * 5 * 5 * * * 5 * * * 5 * * * 5 * * * 5 * * * (1-2-4-8-10-20) (1-2-4-8-13-2c) (1-2-4-8-10-23) (1-2-4-9-12-29) (1-2-4-8-11-26) (1-2-5-a-15-2a) 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 6 5 4 3 2 1 0 0 * 0 * 0 * 0 * 0 * 1 * 1 * 1 * 1 * 1 * 2 * 2 * 2 * 2 * 2 * 3 * 3 * * 3 * 3 * * 3 * 4 * 4 * * 4 * * 4 * * * 4 * * 5 * * 5 * * 5 * * 5 * * * 5 * * * (1-2-4-8-10-21) (1-2-4-9-12-24) (1-2-4-8-11-22) (1-2-4-9-16-29) (1-2-4-8-11-31)
This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2022 Mar 28.
s.30