24
$\begingroup$

I'll often find myself with some combinatorial problem that's obviously been studied before. For example, "Find the smallest set(s) of positive integers such that every integer from 1 to n is the sum of at most two elements of the set." Without becoming an expert on combinatorics, is there some way of finding out the name such a problem goes by in the literature, say in some sort of catalog? Googling and related tactics don't seem to be very helpful here, as most questions of this sort just consist of the words "set, smallest, such that, ..." repeatedly -- there's generally no unique word or phrase to latch on to. For instance, when I tried to Google the problem above, I got back the subset sum problem (given a set, determine whether some subset sums to zero) and the knapsack problem (given a set of objects with specific weights and values, find the most valuable subset under a given total weight), neither of which have anything to do with what I was actually looking for.

I'm not looking for the name of the problem above in particular (although it wouldn't hurt if anyone knows it), but rather some clean way of looking such things up for myself. Does such a catalog exist?

EDIT: My basic idea here is that a large number of combinatorial problems fall into some basic, MADLIBS-style patterns, for instance:

Choices of $m$ elements of the set ___, (with|without) repetition, (with|without) ordering, satisfying the additional constraint ____.

(Paths|circuits) through a (directed|undirected), (vertex|edge) weighted graph, which visit each (edge|vertex), such that the total weight is (maximal|minimal), and such that _.

An index that listed things in this manner would be helpful to non-experts.

$\endgroup$
3
  • $\begingroup$ You've tried checking the Handbook of Combinatorics? $\endgroup$
    – J. M. ain't a mathematician
    Commented Sep 4, 2011 at 17:32
  • 4
    $\begingroup$ This isn't intended to sound snarky, but the best thing you can do is post such a question to SE. Until computers become really good at understanding English, the next best thing is to ask experts and see what they know. $\endgroup$
    – Austin Mohr
    Commented Sep 4, 2011 at 17:50
  • 1
    $\begingroup$ The Handbook of Combinatorics does not appear to have any index of that sort -- it looks more like a survey text than a catalog. Am I missing something? $\endgroup$
    – Daniel McLaury
    Commented Sep 4, 2011 at 20:43

3 Answers 3

Reset to default
19
$\begingroup$

One way is to calculate the terms for small $n$ (in your example the size of the smallest set with your desired property) and then look these up in the On-Line Encyclopedia of Integer Sequences

$\endgroup$
3
  • 1
    $\begingroup$ I try to use OEIS when possible, but I often find myself running into problems with the law of small numbers. Often a sequence will have some obstruction that only kicks in around, say, n = 15, at which point computing the terms is prohibitively expensive (say, because you're searching 2^15 different sets with an expensive function). $\endgroup$
    – Daniel McLaury
    Commented Sep 4, 2011 at 20:43
  • $\begingroup$ @user3296: It depends on the size of your terms. It may be that if you calculate the first 10 (or whatever is reasonable) you only get a few dozen series. Then reading the notes to those you can pick out the one you want. True, if your terms are all single digits you will have too much to read through. But if you only have one term of order 10^5 you often can find the series you want. $\endgroup$
    – Ross Millikan
    Commented Sep 4, 2011 at 21:17
  • $\begingroup$ Agreed. But, for instance, today I was looking at a problem which generated the sequence 2, 4, 6, 10, 14, 18, 22, 28, 34,..., where the terms after 22 became almost prohibitively expensive to calculate. The structure of this sequence is hard to discern: taking first differences, we have 2, 2, 4, 4, 4, 4, 6, 6, ..., but how many sixes should there be? (As it turns out, I was able to bound the sequence below and prove that it's not in the OEIS, but this illustrates the point.) $\endgroup$
    – Daniel McLaury
    Commented Sep 4, 2011 at 23:12
16
$\begingroup$

There is the twelve-fold way, which is a classification of several of the most common combinatorial problems along the lines you are asking about in your edit. If you have $n$ balls to place into $x$ boxes, you can have the balls labeled or not, the boxes labeled or not, and whether the mapping of balls to boxes has no restrictions (choosing the boxes "with replacement," in some contexts), is injective (no more than one ball per box, or choosing the boxes "without replacement," in some contexts), or is surjective (at least one ball per box). Considering all these possibilities gives the twelve options in the name of the classification.

See also Richard Stanley's Enumerative Combinatorics, Vol. I, where it is discussed in detail.

Added (in response to OP's request for generalization): On p. 88 of Stanley's text (which you can download directly from his site using the link above) he says, "There are many possible generalizations of the Twelvefold Way and its individual entries." He then goes on to discuss one of them. In the notes (p. 107) on the chapter in which the Twelvefold Way appears Stanley also says, "An extension of the Twelvefold Way to a 'Thirtyfold Way' (and suggestion of even more entries) is due to R. Proctor." Tracking down the reference leads to Proctor's article "Let's Expand Rota's Twelvefold Way For Counting Partitions!", which I'm not familiar with but which certainly appears to be the kind of thing you're asking for.

$\endgroup$
2
  • 1
    $\begingroup$ This is exactly the sort of thing I was looking for. Do you know if anyone has extended this on a larger scale? $\endgroup$
    – Daniel McLaury
    Commented Sep 5, 2011 at 3:22
  • $\begingroup$ @user3296: See my new edit. $\endgroup$
    – Mike Spivey
    Commented Sep 5, 2011 at 4:39
7
$\begingroup$

The name that you are not looking for is "The postage stamp problem," C12 in Guy, Unsolved Problems In Number Theory. "A popular form of it concerns the design of a set of integer denominations of postage stamp, $A_k=\lbrace\,a_1,\dots,a_k\,\rbrace$ with $1=a_1\lt a_2\lt\cdots\lt a_k$ to be used on envelopes with room for at most $h$ stamps, so that all integer amounts of postage up to a given bound can be affixed. [...] At first the main interest was in the global problem: given $h$ and $k$, find an extremal basis $A_k'$ with largest possible $h$-range," that is, one which maximizes the smallest integer you can't get. Your problem is the case $h=2$. There is much information about this (and many, many other combinatorial number theory problems) in the book.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .