Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

A lot of effort in discrete maths / combinatorics is expended in the construction of lists, catalogues or census [sic] of combinatorial objects such as groups, graphs, designs etc. These catalogues are now a fundamental part of computer algebra systems.

Obviously nowadays most of this is done by computer, but a surprisingly large amount of this work predates (electronic) computers - for example, G.A. Miller worked on creating lists of "substitution groups" (permutation groups) in the late 1800s and early 1900s, while Ronald Foster created the "Foster Census" of cubic symmetric graphs in the 1930s.

I'd like to know some more examples of famous "cataloguers" of mathematical (well, particularly combinatorial) objects predating electronic computers.

share|improve this question
3  
Since the question is asking for a list of examples, I think it should be big-list and CW. –  Alex B. Nov 23 '10 at 4:58
    
Added big-list. –  David Roberts Nov 23 '10 at 5:34
    
Yes, this would be Community Wiki. –  Denis Serre Nov 23 '10 at 6:34
    
I guess, only the moderators (or the author) can make it CW. –  André Henriques Nov 23 '10 at 8:44
    
gordon-royle, please make this CW. –  Todd Trimble Nov 23 '10 at 18:18

9 Answers 9

Donald Knuth has lots of interesting information on the history of the generation of basic combinatorial objects such as partitions and permutations in Section 7.2.1.7 of The Art of Computer Programming, vol. 4, Fascicle 4. The enumeration of the 318 6-element posets up to isomorphism appears in the 1972 Ph.D. thesis of John A. Wright.

Update. Diagrams depicting the 52 partitions of a 5-element set were used as chapter headings for all but the first and last chapter of certain editions of The Tale of Genji by Lady Murasaki (c. 978-c. 1031 CE), beginning in the seventeenth century. See http://en.wikipedia.org/wiki/File:Genji_chapter_symbols_groupings_of_5_elements.svg.

share|improve this answer
    
The latter is a good example of the things I am looking for. The former is more about the process of generating, say, permutations efficiently in that (I don't think) anybody would actually sit down and list all the permutations as an end in itself. On the other hand, a list of all the posets is a non-trivial listing that could be used to search for examples, test conjectures etc. –  Gordon Royle Nov 23 '10 at 3:54
    
Knuth gives many examples of ancient lists of permutations, combinations, partitions, etc. –  Richard Stanley Nov 24 '10 at 15:54

Hall, Jr., Marshall; Senior, James K. (1964), The Groups of Order $2^n$ (n ≤ 6), Macmillan, LCCN 64-16861, MR168631.

This is a catalog of the 340 groups of order dividing 64 with detailed tables of defining relations, constants, and lattice presentations of each group. It is extremely large (A2 size?), and hence often lurks in an odd place in libraries looking battered and sorry for itself.

share|improve this answer
    
Do you know whether they used a computer? –  Gerry Myerson Nov 23 '10 at 22:54
1  
I am fairly sure they did not, but I don't have the book to hand. For the study of groups of order p^5, p^6 and p^7, where computers are used, see the work of Eamonn O'Brien math.auckland.ac.nz/~obrien/recent_work.htm The Atlas of Finite Simple groups is a comprehensive catalogue, again computer constructed, see brauer.maths.qmul.ac.uk/Atlas/v3 –  Ursula Martin Nov 27 '10 at 18:47
@book {MR0357292,
    AUTHOR = {Sloane, N. J. A.},
     TITLE = {A handbook of integer sequences},
 PUBLISHER = {Academic Press [A subsidiary of Harcourt Brace Jovanovich,
              Publishers], New York-London},
      YEAR = {1973},
     PAGES = {xiii+206},
   MRCLASS = {10A40 (05AXX 65A05)},
  MRNUMBER = {0357292 (50 \#9760)},
}

It is a predecessor of the online encyclopedia of integer sequences, of course. As intermediate step, there is the sequel

@book {MR1327059,
    AUTHOR = {Sloane, N. J. A. and Plouffe, Simon},
     TITLE = {The encyclopedia of integer sequences},
      NOTE = {With a separately available computer disk},
 PUBLISHER = {Academic Press Inc.},
   ADDRESS = {San Diego, CA},
      YEAR = {1995},
     PAGES = {xiv+587},
      ISBN = {0-12-558630-2},
   MRCLASS = {11-00 (05A10 11B83 11Y55)},
  MRNUMBER = {1327059 (96a:11001)},
MRREVIEWER = {P{\'e}ter Kiss},
}
share|improve this answer
    
I'm more interested in lists of "things" rather than lists of numbers. I know that the original EIS had many sequences that counted actual things, but many of these are theoretical formulas and not done by "constructing the objects and then counting them". (The current OEIS has been ruined for me by the people who insist on submitting hundreds of sequences that just don't count anything at all but just happen to be artificially defined sequences of numbers.) –  Gordon Royle Nov 23 '10 at 8:30
    
Yes, I should have marked my answer as "slightly off topic", but I think it's still important to know that the oeis started as a printed catalogue. Hm, maybe the keyword:nice could help you? –  Martin Rubey Nov 23 '10 at 9:09
    
BTW: when will your catalogue be online again? –  Martin Rubey Nov 23 '10 at 9:09
    
Yes, the OEIS started as a printed catalogue, but 1973 can hardly be said to predate electronic computers. I imagine that much of the catalogueing (sp?) was done by machine. –  Gerry Myerson Nov 23 '10 at 10:41
    
From the acknowledgments: "The table was produced by first recording the sequences on punched cards, and (except when the sequence was generated by the author) comparing a listing of the cards with the original tables. These cards were then stored on magnetic tape, and the table has been typeset automatically from this tape." –  Gerry Myerson Nov 23 '10 at 22:58

MacMahon computed the number of partitions of $n$ for $n\le200$, roughly 100 years ago (sorry, don't have the exact citation).

share|improve this answer
    
I doubt MacMahon ever published this table. In his "Ramanujan: twelve lectures", Hardy writes: "Macmahon was a practiced and enthusiastic computer, and made us a table of $p(n)$ up to $n=200$".bit.ly/eyixDR Somehow $p(200)=3,972,999,029,388$ became so popular, it became part of the folklore and was even printed in the NYTimes.nyti.ms/eFRlQt –  Igor Pak Nov 23 '10 at 16:55
    
According to Hardy and Wright, 6th ed., p. 391, "MacMahon's table is printed in Proc London Math Soc (2) 17 (1918) 114-5, and has subsequently been extended to 600 (Gupta, ibid, 39 (1935) 142-9, and 42 (1937) 546-9), and to 1000 (Gupta, Gwyther, and Miller, Roy Soc Math Tables 4 (Cambridge 1958))." Whether that last work made use of an electronic computer, I do not know. –  Gerry Myerson Nov 23 '10 at 22:52

Frenicle de Bessy is credited with enumerating the 880 magic squares of order 4 in 1693. I don't know whether he actually listed them all. The reference, as given at MathWorld, is Frénicle de Bessy, B. "Des quarrez ou tables magiques. Avec table generale des quarrez magiques de quatre de costé." In Divers Ouvrages de Mathématique et de Physique, par Messieurs de l'Académie Royale des Sciences (Ed. P. de la Hire). Paris: De l'imprimerie Royale par Jean Anisson, pp. 423-507, 1693. Reprinted as Mem. de l'Acad. Roy. des Sciences 5 (pour 1666-1699), 209-354, 1729.

share|improve this answer
    
D.N Lehmer published "A complete census of $4\times4$4×4 magic squares" in Bulletin Am. Math Soc in 1933 but did not get anything like 880... he got 468 "normalized" squares... –  Gordon Royle Nov 24 '10 at 0:26
    
880 is accepted as the number of 4-by-4 magic squares. See, e.g., oeis.org/A006052 and the references cited there. A modern enumeration is in Berlekamp, Conway, Guy, Winning Ways, pp 778-783. I don't know what Lehmer was counting. –  Gerry Myerson Nov 24 '10 at 4:32

Tutte had a series of papers that may qualify:

MR0130841 (24 #A695) Tutte, W. T. A census of planar triangulations. Canad. J. Math. 14 1962 21–38.

MR0137657 (25 #1108) Tutte, W. T. A census of Hamiltonian polygons. Canad. J. Math. 14 1962 402–417.

MR0142470 (26 #39) Tutte, W. T. A census of slicings. Canad. J. Math. 14 1962 708–722.

MR0146823 (26 #4343) Tutte, W. T. A census of planar maps. Canad. J. Math. 15 1963 249–271.

In Figure 8 of the last paper, he illustrates the rooted bicubic maps with $2n$ vertices for $n\le4$, according to the review by G. de B. Robinson.

share|improve this answer

Pre-computer lists of knots (from a mathematical point of view) go back to Listing, 1847, followed by the work of Tait, Kirkman, and Little (I don't have the exact dates, but late 19th century, I suppose). Also M G Haseman (early 20th century, I think).

EDIT: I found a few references: J.-B. Listing, Vorstudien zur topologie, Goettinger Studien 1 (1847) 811–875.

M. Haseman, On knots, with a census of the amphicheirals with twelve crossings, Trans. Roy. Soc. Edinburgh 52 (1918) 235–255.

share|improve this answer
    
Good one... nice example. –  Gordon Royle Nov 23 '10 at 8:31

Catalogs of prime numbers and of factorizations of composites long predate electronic computers. The following information is taken from Table 85 on page 218 of Albert H Beiler, Recreations in the Theory of Numbers, Dover, 1964.

Lists of primes. Up to 97, L Pisano, 1202. 750, P Cataldi, 1603. 10,000, F van Schooten, 1657. 100,999, J G Kruger, 1746. 102,000, J H Lambert, 1770. 400,000, A F Marci, 1772. 10,000,000, D N Lehmer, 1914.

Factor tables. Up to 100, Pisano, 1202. 800, Cataldi, 1603. 24,000, J H Rahn, 1659. 100,000, T Brancker, 1668. 2,856,000, A Felkel, 1785. 3,000,000, J C Burckhardt, 1814-1817. 7,000,000 to 9,000,000, Z Dase and H Rosenberg, 1862-3. 100,000,000, J P Kulik, 1867. 3,000,000 to 6,000,000, J Glaisher, 1879-83. 10,000,000, D N Lehmer, 1909.

Not clear to me what purpose the factor tables of Glaisher and Lehmer served, when Kulik had already gone much farther, but I'm sure there's some explanation.

Also, I'm guessing Beiler got his information from Dickson's History.

share|improve this answer

Ernst Schroeder's 1870 paper "Vier combinatorische Probleme" discusses four closely related combinatorial structures.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.