17
$\begingroup$

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.

$\endgroup$
0

12 Answers 12

9
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Nov 23, 2010 at 3:54
  • 2
    $\begingroup$ Knuth gives many examples of ancient lists of permutations, combinations, partitions, etc. $\endgroup$ Nov 24, 2010 at 15:54
  • $\begingroup$ There's the 64 diagrams in the I Ching (mathematically almost trivial but way earlier than the Tale of Genji). $\endgroup$ Feb 7, 2018 at 22:07
7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Good one... nice example. $\endgroup$ Nov 23, 2010 at 8:31
  • 1
    $\begingroup$ . . . and remarkably appropriate name. (Cf. Poynting vector, Penning trap) $\endgroup$ Feb 7, 2018 at 22:07
6
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Do you know whether they used a computer? $\endgroup$ Nov 23, 2010 at 22:54
  • 1
    $\begingroup$ 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 $\endgroup$ Nov 27, 2010 at 18:47
6
$\begingroup$

There are many examples of such combinatorial objects in Indian mathematics, motivated primarily by the study of prosody, music, medicine and architecture. Combinatorics had reached a very high state of development by the middle ages in India.

In 1356 CE, Narayana Pandita, an Indian mathematician enumerated 384 pan-diagonal 4-by-4 magic squares, including rotations and reflections in his book "Ganita Kaumudi". In fact, the 2nd last chapter of this book summarises the state of the art of combinatorics in 1356 India, while the last chapter is a highly original treatise on magic squares and magic figures.

A more curious list is given by Varahamihira in his Brihatsamhita (587 CE) to make perfumes using a combination of 4 substances from total of 16 ingredients given as a magic square.  

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

W. T. 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.

$\endgroup$
3
$\begingroup$
@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},
}
$\endgroup$
5
  • 1
    $\begingroup$ 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.) $\endgroup$ Nov 23, 2010 at 8:30
  • $\begingroup$ 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? $\endgroup$ Nov 23, 2010 at 9:09
  • $\begingroup$ BTW: when will your catalogue be online again? $\endgroup$ Nov 23, 2010 at 9:09
  • $\begingroup$ 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. $\endgroup$ Nov 23, 2010 at 10:41
  • $\begingroup$ 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." $\endgroup$ Nov 23, 2010 at 22:58
3
$\begingroup$

A lot of people counted Latin squares, going back to Euler (1782) and Cayley and Frolov (independently, 1890). Many of those who tried got the wrong answer. A summary is in this paper:

B. D. McKay, A. Meynert and W. Myrvold, Small Latin squares, quasigroups and loops, J. Combin. Designs, 15 (2007) 98-119. A copy with a correction to Theorem 2 is here.

My favourite from the pre-computer age is:

P. N. Saxena, A simplified method of enumerating Latin squares by MacMahon’s differential operators; II. The 7 × 7 Latin squares, J. Indian Soc. Agric. Statistics, 3 (1951) 24–79.

Saxena devoted 55 pages to the most intricate case-by-case calculations but amazingly got the right answer.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Igor Pak
    Nov 23, 2010 at 16:55
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 23, 2010 at 22:52
2
$\begingroup$

Jan de Vries compiled a list of cubic graphs up to 10 vertices in the 19th century. His papers (in Dutch and French) are:

J. de Vries. Over vlakke configuraties waarin elk punt met twee lijnen incident is. Verslagen en Mededeelingen der Koninklijke Akademie voor Wetenschappen, Afdeeling Natuurkunde (3) 6, pages 382–407, 1889.

J. de Vries. Sur les configurations planes dont chaque point supporte deux droites. Rendiconti Circolo Mat. Palermo 5, pages 221–226, 1891.

The first use of the computer for this purpose was in 1966 (Balaban).

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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... $\endgroup$ Nov 24, 2010 at 0:26
  • $\begingroup$ 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. $\endgroup$ Nov 24, 2010 at 4:32
  • $\begingroup$ I've looked at the Lehmer paper, October 1933, pp. 764-767. He counted what I'd call semi-magic squares; the row and column sums are all 34, but there's no condition on the diagonals. $\endgroup$ Feb 7, 2018 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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