Prueba de que $n \in \mathbb{N}$ por analogía combinatoria?

Question

(Descargo de responsabilidad: soy un estudiante de secundaria, y mi mayor conocimiento de las matemáticas es algo de cálculo elemental. Puede que esta no sea la terminología correcta).

Hace un tiempo, vi el siguiente problema: demostrar, para números naturales $a$ , $b$ , $c$ , $d$ con $a \geq b + c + d$ que $\frac{a!}{b!c!d!}$ es un número natural.

Tuve una idea genial sobre esto cuando me di cuenta de que la expresión $\frac{a!}{b!c!d!}$ realmente da la respuesta a un problema combinatorio. En concreto, es el número de permutaciones únicas de $a$ objetos cuando $b$ son de un mismo tipo (indistinguibles entre sí), $c$ son de otro tipo, y $d$ son de otro tipo. Obviamente, no se puede tener un número no natural de permutaciones, por lo que éste debe ser siempre un número natural.

¿Es éste un método de prueba válido? ¿Se puede establecer que una expresión es siempre un número natural asignándole un significado combinatorio?

Answer 1

Sí: ha descubierto una forma de prueba combinatoria Un tipo de prueba elegante y a menudo muy informativa que se utiliza con mucha frecuencia en combinatoria. Sin embargo, su argumento necesita un poco de reparación. Dejemos que $e=a-(b+c+d)$ ; entonces el coeficiente multinomial

$$\binom{a}{b,c,d,e}=\frac{a!}{b!\,c!\,d!\,e!}$$

es el número de permutaciones distinguibles de $a$ objetos consistentes en $b$ objetos indistinguibles de un mismo tipo, $c$ objetos indistinguibles de otro tipo, $d$ objetos indistinguibles de un tercer tipo, y $e$ objetos indistinguibles de un cuarto tipo. Se trata claramente de un número entero no negativo, ya que cuenta una colección discreta de entidades, y

$$\frac{a!}{b!\,c!\,d!}=\binom{a}{b,c,d,e}\cdot e!$$

es, por tanto, también un número entero no negativo.

Como alternativa, puede tomar el $e$ los elementos restantes sean distinguibles entre sí y de los otros tres tipos, en cuyo caso $\frac{a!}{b!\,c!\,d!}$ es efectivamente el número de permutaciones distinguibles del $a$ objetos, y no necesitas el paso intermedio. Si esto es lo que tenías en mente, ¡la única reparación necesaria es hacer esto un poco más claro!

Answer 2

Sí, es una forma perfectamente válida de demostrar que el valor de una expresión es siempre un número natural. Por cierto, este es un argumento para tener $0\in\Bbb N$ (un punto que, desgraciadamente, sigue suscitando controversia), porque demostrar que un número cuenta los elementos de un conjunto finito no implica demostrar que el conjunto es no vacío. Yo incluso consideraría que éste es el enfoque más natural para demostrar que una expresión toma valores numéricos naturales, aunque por supuesto no funciona en todos los casos.

El enfoque más realista es mostrar por separado que una expresión siempre toma valores enteros (en el caso que nos ocupa, se podría hacer contando los factores primos en el numerador y el denominador) y que no puede tomar valores negativos. Dependiendo de la situación, esto puede ser sencillo, tedioso o prácticamente imposible. Hay resultados y conjeturas famosas sobre ciertos tipos de expresiones que siempre toman valores de números naturales cuando ninguno de estos métodos parece funcionar. Se conocen casos en los que se ha encontrado una prueba de esta propiedad realizando una construcción (muy abstracta) y mostrando que define un espacio vectorial cuyo dimensión ¡está dada por la expresión sin haber construido un conjunto con ese número de elementos!

Answer 3

Puedes notar que $\mathfrak{S}_b \times \mathfrak{S}_c \times \mathfrak{S}_d$ es un subgrupo de $\mathfrak{S}_a$ si $a \geq b+c+d$ dividiendo el conjunto $\{1,\dots,a\}$ en tres subconjuntos de longitud $b$ , $c$ y $d$ .