2
$\begingroup$

Let's say I'm faced with the problem of counting the number of elements in a set A. This set is extremely difficult to count, but maybe I could set a bijection with another known and well studied set (such as the ones that can be computed using Catalan numbers or Euler numbers).

Of course at first I could only do this by trial and error since it's very difficult to see a bijection immediately. So, which sets are the most common ones I could try?

For example, consider the problem of finding the number of lists that have N elements where every element is a number between 1 and K inclusive, and for every element i greater than 1, i-1 appears before the last occurrence of i in the list. The cardinality of this set can be found using Euler numbers.

So the question is, what are the most common sets that I should try to biject to first?

$\endgroup$
4
  • 2
    $\begingroup$ I'd suggest those sets whose cardinality matches the cardinalities of the things you're counting. For instance, if you're counting the number of ways to pick 2 things from $n$ items, the Catalan numbers won't help much. Often computing the first 5 or 10 examples and then looking at the handbook of integer sequences to find something that matches can be useful. Far better than arriving with a hammer and looking around to see if there are any nails. $\endgroup$
    – John Hughes
    Jul 25, 2016 at 23:43
  • $\begingroup$ If you took a poll of all mathematicians and asked them which set did you most recently construct a bijection to, for the sake of being a bijection, I bet the winner would be $\Bbb N$ or $\Bbb Z$. $\endgroup$
    – Gregory Grant
    Jul 25, 2016 at 23:44
  • $\begingroup$ For countably infinite sets, usually $\mathbb{N}$ is the best choice, other times it is easier to use the set of finite words over a countable alphabet. For cardinality of the reals, you can use $\mathbb{R}$, but generally $\mathbb{N}^\mathbb{N}$ or $2^\mathbb{N}$ are easier to use. And really, you don't need to find an actual bijection, it's enough if you find an injection both ways, by the Cantor-Schröder-Bernstein theorem. $\endgroup$
    – Anon
    Jul 25, 2016 at 23:58
  • 1
    $\begingroup$ @JohnHughes : Probably you should make your comment an answer, and maybe mention OEIS along the way. $\qquad$ $\endgroup$
    – Michael Hardy
    Jul 26, 2016 at 0:01

1 Answer 1

Reset to default
1
$\begingroup$

At Michael Hardy's suggestion, I'm posting this as an answer:

I'd suggest those sets whose cardinality matches the cardinalities of the things you're counting. :)

For instance, if you're counting the number of ways to pick 2 things from $n$ items, the Catalan numbers won't help much. Often computing the first 5 or 10 examples and then looking at the handbook of integer sequences (or OEIS, for those who live in an era of the internet rather than books!) to find something that matches can be useful. Either is far better than arriving with a hammer and looking around to see if there are any nails.

Of course, as Gregory Grant notes, the naturals, the integers, and (per McFry) the reals, often represented as infinite sequences of naturals or as infinite binary sequences, can be useful. I can't recall ever writing down a bijection with anything whose cardinality is greater than that of the reals, but that may reflect the areas of mathematics that interest me (and the fact that I'm now a computer scientist, at least by title).

$\endgroup$

You must log in to answer this question.

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