Contar el número de objetos y estructuras matemáticas

Question

En cuanto a los números de ciertos objetos y estructuras matemáticas, especialmente conjuntos, relaciones y funciones, he recopilado una lista de los recuentos de varias fuentes:

1. Particiones de un conjunto con $k$ elementos ("números de Bell"): $$(a_k)_{k=0, \dots, 12} = (1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597)$$

2. $k$ -subsets en un conjunto con $n$ elementos: $$\binom n k$$

3. Mapeos de un conjunto $X$ a un conjunto $Y$ : $$|Y|^{|X|}$$

4. Permutaciones en un conjunto $X$ o mapeos biyectivos de $X$ a $Y$ o el total de pedidos en un conjunto $X$ : $$|X|!$$

5. Mapeos inyectivos de un conjunto $X$ a un conjunto $Y$ : $$\dfrac {|Y|!} {(|Y| - |X|)!}$$

6. Mapeos surjetivos de un conjunto $X$ a un conjunto $Y$ : $$|Y|! \cdot S_{|X|, |Y|}$$

7. Permutaciones de $n$ elementos con $k$ ciclos disjuntos ("números de Stirling del primer tipo"): $$s_{n,k}$$

8. Pariciones de un $n$ -elementos puestos en $k$ subconjuntos no vacíos ("números de Stirling del segundo tipo"): $$S_{n,k}$$

9. Relaciones en un conjunto $X$ : $$2 ^{|X|^2}$$

10. relaciones (ir)reflexivas sobre un conjunto $X$ : $$2 ^{|X|^2 - |X|}$$

11. Relaciones simétricas en un conjunto $X$ : $$2 ^\frac {|X|^2 + |X|} 2$$

12. Relaciones simétricas y reflexivas en un conjunto $X$ : $$2 ^\frac {|X|^2 - |X|} 2$$

13. Relaciones antisimétricas en un conjunto $X$ : $$2^{|X|} \cdot 3 ^\frac {|X|^2 - |X|} 2$$

14. Relaciones antisimétricas e (ir)reflexivas en un conjunto $X$ : $$3 ^\frac {|X|^2 - |X|} 2$$

¿Puede ayudarme a revisarlo? ¿Hay algún error? ¿Hay algo que no sea cierto para el caso general o se puede expresar de forma más concisa?

Answer 1

Déjame ver.

1. Nunca he oído hablar de ellos, pero intenta buscar en esta página Wiki ;
2. Absolutamente correcto;
3. Correcto cuando $X,Y$ son finitas, podrían extenderse a conjuntos infinitos con alguna aritmética transfinita, no lo sé; por ejemplo $|\mathbb{Q}|^{|\mathbb{Q}|}$ no está realmente claro; por otro lado, $2^{|\mathbb{Q}|}=|\mathbb{R}|$ , si queremos que esta relación en su 3) siga manteniéndose;
4. De nuevo, ¿qué es $|\mathbb{Q}|!$ ? En el caso finito, todo funciona bien;
5. Finito: OK, infinito: ¿qué significa eso?
6. No lo sé;
7. Lo mismo que en el caso anterior;
8. Lo mismo que en el caso anterior;
9. Correcto, de nuevo con los problemas sobre conjuntos infinitos.

No puedo comentar el resto.

Actualización

Encontrado este que parece confirmar el 10. Básicamente el argumento es que si uno hace una matriz que represente $X\times X$ , algunas de sus celdas forman la relación, y al ser la relación reflexiva se obliga a tomar la diagonal, y las celdas restantes son $n^2-n$ y cualquier subconjunto de ellas puede añadirse a la diagonal para formar una relación reflexiva.

Con un argumento similar, una relación simétrica es cualquier subconjunto del triángulo inferior de la matriz, que tiene $\frac{n(n+1)}{2}$ elementos, lo que significa que las relaciones simétricas son $2^{\frac{n(n+1)}{2}}$ , donde $n=|X|$ .

Por supuesto, si el conjunto es infinito, como siempre, tenemos un problema. Pero en el caso de 10 tenemos una biyección entre las relaciones y las partes de algo que tiene la cardinalidad del conjunto (si es infinito, si no, como hemos dicho arriba ), así que por ejemplo las relaciones simétricas sobre $\mathbb{Q}$ debe estar en biyección con $\mathbb{R}$ .

Actualización 2

Este confirma tus 13 y 14, dando un argumento para una prueba. En el caso infinito, naturalmente, se pueden encontrar argumentos de biyección, tal vez. Usando el argumento, estamos eligiendo cualquier subconjunto de la diagonal. Así que tenemos que elegir, y esta es una elección en el conjunto de potencias de la diagonal que tiene la misma cardinalidad de $X$ . ¿Qué pasa con el $m_{ij},m_{ji}$ ¿pares? Me aventuro a decir que el $3^{\dots}$ puede convertirse inofensivamente en $2^{\dots}$ . Ah, sí, $3^{\dots}$ es básicamente el número de funciones de $\{1,2,3\}$ al conjunto cuya cardinalidad es $\dots$ y al menos en el caso contable esto es lo mismo que las funciones de $\{1,2\}$ (funciones de $\{1,2,3\}$ son los mismos que los de $\{0,1,2\}$ que son números reales en notación ternaria, por lo que están en biyección con $[0,1]$ , al igual que los de $\{0,1\}$ que es el mismo que el de $\{1,2\}$ ).

Actualización 3

Acabo de darme cuenta de que me he equivocado en los números. El 12 se resuelve retocando el argumento del 11 para tener en cuenta que la diagonal está obligada a estar en el subconjunto, de ahí que las partes que se toman son las del estrictamente mitad triangular inferior, de ahí el cambio de signo en el exponente.