Counting number of mathematical objects and structures

Question

Regarding the numbers of certain mathematical objects and structures, especially sets, relations and functions, I've compiled a list of the counts from various sources:

1. Partitions of a set with $k$ elements ("Bell numbers"): $$(a_k)_{k=0, \dots, 12} = (1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597)$$

2. $k$-subsets on a set with $n$ elements: $$\binom n k$$

3. Mappings from a set $X$ to a set $Y$: $$|Y|^{|X|}$$

4. Permutations on a set $X$ or bijective mappings from $X$ to $Y$ or total orders on a set $X$: $$|X|!$$

5. Injective mappings from a set $X$ to a set $Y$: $$\dfrac {|Y|!} {(|Y| - |X|)!}$$

6. Surjective mappings from a set $X$ to a set $Y$: $$|Y|! \cdot S_{|X|, |Y|}$$

7. Permutations of $n$ elements with $k$ disjoint cycles ("Stirling numbers of the first kind"): $$s_{n,k}$$

8. Paritions of an $n$-elements set into $k$ non-empty subsets ("Stirling numbers of the second kind"): $$S_{n,k}$$

9. Relations on a set $X$: $$2 ^{|X|^2}$$

10. (Ir)reflexive relations on a set $X$: $$2 ^{|X|^2 - |X|}$$

11. Symmetric relations on a set $X$: $$2 ^\frac {|X|^2 + |X|} 2$$

12. Symmetric and reflexive relations on a set $X$: $$2 ^\frac {|X|^2 - |X|} 2$$

13. Antisymmetric relations on a set $X$: $$2^{|X|} \cdot 3 ^\frac {|X|^2 - |X|} 2$$

14. Antisymmetric and (ir)reflexive relations on a set $X$: $$3 ^\frac {|X|^2 - |X|} 2$$

Can you help me review it? Are there any errors? Is something not true for the general case or can something be expressed more concisely?

Answer 1

Let me see.

1. Never heard of those, but try looking at this Wiki page;
2. Absolutely correct;
3. Correct when $X,Y$ are finite, might extend to infinite sets with some transfinite arithmetic, I don't know; e.g., $|\mathbb{Q}|^{|\mathbb{Q}|}$ is not really clear; on the other hand, $2^{|\mathbb{Q}|}=|\mathbb{R}|$, if we want this relation in your 3) to continue holding;
4. Again, what is $|\mathbb{Q}|!$? In the finite case, all works fine;
5. Finite: OK, infinite: what does that mean?
6. I don't know;
7. Same as above;
8. Same as above;
9. Correct, again with the problems on infinite sets.

Cannot comment on the rest.

Update

Found this which seems to confirm 10. Basically the argument is that if one makes a matrix representing $X\times X$, some of its cells form the relation, and being the relation reflexive you are forced to take the diagonal, and the remaining cells are $n^2-n$, and any subset of them may be added to the diagonal to form a reflexive relation.

With a similar argument, a symmetric relation is any subset of the lower triangle of the matrix, which has $\frac{n(n+1)}{2}$ elements, meaning the symmetric relations are $2^{\frac{n(n+1)}{2}}$, where $n=|X|$.

Of course, if the set is infinite, as always, we have a problem. But in the case of 10 we have a bijection between the relations and the parts of something which has the cardinality of the set (if it is infinite, otherwise as we have said above…), so for examples the symmetric relations on $\mathbb{Q}$ ought to be in bijection with $\mathbb{R}$.

Update 2

This confirms your 13 and 14, giving an argument for a proof. In the infinite case, naturally, one can find bijection arguments, perhaps. Using the argument, we are choosing any subset of the diagonal. So we have this choice to make, and this is a choice in the power set of the diagonal which has the same cardinality of $X$. What about the $m_{ij},m_{ji}$ pairs? I venture a guess that the $3^{\dots}$ can be harmlessly turned to $2^{\dots}$. Oh yeah, $3^{\dots}$ is basically the number of functions from $\{1,2,3\}$ to the set whose cardinality is $\dots$, and at least in the countable case this is the same as functions from $\{1,2\}$ (functions from $\{1,2,3\}$ are the same as those from $\{0,1,2\}$, which are real numbers in ternary notation, so they are in bijection with $[0,1]$, as are those from $\{0,1\}$, which is the same as those from $\{1,2\}$).

Update 3

Just noticed I got numbers wrong. 12 is dealt with by tweaking the argument for 11 to take into account that the diagonal is forced to be in the subset, hence the parts you take are those of the strictly lower triangular half, hence the sign change in the exponent.