Combinatorics – Enumerating, Counting, and Listing Explained

co.combinatoricsenumerative-combinatoricsterminology

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.

Best Answer

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.

Related Question