The verbs in combinatorics: Enumerating, counting, listing and all that

Question

Two closely related, but different tasks in combinatorics are

1. determining the number of elements in some set $A$, and
2. presenting all its elements one by one.

Question: What are some works in combinatorics literature that explicitly consider the naming of these different tasks?

---

As a background, it seems that the terminology is sometimes conflicting and confusing. In particular, enumerating can mean either task. In computer science and algorithms it often refers to task 2. In combinatorics it often refers to task 1, but not always. Pólya enumeration is definitely task 1, not task 2 (indeed in this MO question it is pointed out that Pólya enumeration is "not generally a good tool for actually listing").

For what it's worth, Merriam-Webster duly reports that enumerate has meanings 1. to ascertain the number of: COUNT; 2. to specify one after another: LIST.

Task 1 is also called counting, which seems unambiguous. But I have seen "computing the number of elements without actually counting them"! Here counting seems to mean tallying, that is, keeping a counter and incrementing by one whenever a new object is seen.

Task 2 admits many names, which also may indicate finer variations:

• listing the elements: Presenting a full listing, stored in some form (paper or computer file).
• generating the elements: A method that creates all the elements, one by one, but may not store them. Perhaps each element is examined, and then thrown away.
• visiting: similar to the previous, with a tone of computer science and data structures.
• constructing: similar, but with a more mathematical flavor. It suggests that creating even one object takes some effort, so it is not just "visiting".
• classifying: somewhat unclear, but often means something like generating the objects and counting how many of them have certain properties. But it might mean simply isomorph-free listing (in a sense, "classifying" the objects into isomorphism classes).
• Furthermore, task 2 is often emphasized with modifiers like "full", "explicit", "exhaustive", "actually", "one by one", "brute force" to set it apart from task 1.

Enumerating may also mean a more abstract task where elements are equipped with indices and/or abstractly arranged in a potentially infinite list, but one never actually constructs the list (as in "enumerate all rational numbers").

To clarify my question: I am not asking for examples where the words are just used, as in "In this paper we enumerate all Schluppenburger contrivances of the second kind". I am interested in works that recognize the difference of these tasks and make a conscious effort in defining terminology, and perhaps explicitly comment on the usage.

---

Here are some that I have found:

• Knuth (TAOCP 4B §7.2.1) considers many verbs: run through possibilities, look at permutations, enumerate, count, list, make a list, print, examine, generate, visit. He notes that enumerate may mean either task 1 or 2. He settles for generating and visiting for task 2, when the list is not explicitly stored.

• Cameron (Notes on Counting, p. 1–2) settles with counting for task 1 and generating for task 2. Later in the notes there are scattered instances of enumeration, which mostly seems to be synonymous with counting.

• Ruskey (Combinatorial Generation, 2003, p. iii) discusses the terminology for task 2. He mentions generate and enumerate but notes that both are overloaded with other meanings. For example, generate can mean generate uniformly at random, and enumerate can mean counting. Ruskey also considers listing but settles with generation.

• Kreher & Stinson (Combinatorial Algorithms, 1999, p. 1) defines: Generation, construct all the combinatorial structures of a particular type – – A generation algorithm will list all the objects. Enumeration, compute the number of different structures of a particular type – – each object can be counted as it is generated.

Answer 1

I'm not sure if this is exactly what you're looking for, but the main topic of Herb Wilf's article What is an Answer? is how to answer the question "How many ______ are there?" His basic thesis is that an alleged answer to such a question is satisfactory only if it provides an algorithm whose computational complexity is significantly less than the best known algorithm for listing the elements. More precisely, he introduces the following definitions:

$\mbox{Count$(n)$} = $ the complexity of the algorithm for calculating $f(n)$, whether it be given by a formula, an algorithm, et cetera, and

$\mbox{List$(n)$} = $ the complexity of producing all of the members of the set $S_n$, one at a time, by the speediest known method, and counting them.

Definition 1: We will say that a solution of a counting problem is effective if $$\lim_{n\to\infty} \frac{\mbox{Count}(n)}{\mbox{List}(n)} = 0.$$

So Wilf certainly makes a clear distinction between the two tasks. On the other hand, he does not devote much attention to terminology per se.

On a related but slightly different note, another important combinatorial task is sampling or randomly generating an element. The relation between counting and sampling is the topic of entire books, such as Computational Complexity of Counting and Sampling by István Miklós. In this context, the word counting is pretty consistently used for the task of computing $f(n)$, although this usage is largely de facto, whereas I understand you to be looking for de jure discussions.

Answer 2

If I understand what you are looking for, I think (even though it's a noun) the term combinatorial Gray code can be an answer to your question. A combinatorial Gray code gives a means of listing a particular class of objects in an order which differ by a small amount (e.g. a classical Gray code which list binary strings by a single bit flip, listing subsets of size $k$ in an order which differ by one element, etc.). One reference is A Survey of Combinatorial Gray Codes by Carla Savage and the article begins with:

One of the earliest problems addressed in the area of combinatorial algorithms was that of efficiently generating items in a particular combinatorial class in such a way that each item is generated exactly once. Many practical problems require for their solution the sampling of a random object from a combinatorial class or, worse, an exhaustive search through all objects in the class. Whereas early work in combinatorics focused on counting, by 1960 it was clear that with the aid of a computer it would be feasible to list the objects in combinatorial classes [73]. However, in order for such a listing to be possible, even for objects of moderate size, combinatorial generation methods must be extremely efficient. A common approach has been to try to generate the objects as a list in which successive elements differ only in a small way. The classic example is the binary reflected Gray code [45, 52] which is a scheme for listing all n-bit binary numbers so that successive numbers differ in exactly one bit.

The reference [73] is

D. H. LEHMER, The machine tools of combinatorics, in Applied Combinatorial Mathematics, E. Beckenbach, ed., John Wiley & Sons, New York, 1964, pp. 5–31.

and is probably a example of what you are looking for. However, I can find this article online.

Answer 3

I would say, as a first distinction, enumerating and listing refer to ordinals (ex-numerare = producing an ordered bijection onto $[n]$, like a shepherd at sunset, emitting (ex-mittere) the numbers in order : $1,2,3,\dots$) while counting (cum-putare: putting together to reckon. I do not see etymologically the category of order in it) and measuring refer to cardinals. We may count a bunch of apples of equal size using a scale.

In this sense a generating series $\sum_{k=0}^\infty a_k x^k$ enumerates; the inclusion-exclusion formula for $\big|\big(\cup_{i\in I} X_i\big)^c\big|$ counts. Indeed, the natural setting of it uses additive set functions, measures, probabilities, that are tools to weight sets.