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](https://mathoverflow.net/questions/94133/using-polyas-enumeration-theorem-for-explicit-generation-of-instances) it is pointed out that Pólya enumeration is
"not generally a good tool for actually listing").


For what it's worth, [Merriam-Webster](https://www.merriam-webster.com/dictionary/enumerate) 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.



The verbs in combinatorics: Enumerating, counting, listing and all that
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?](https://www.jstor.org/stable/2321713) 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.


