La prueba de que una combinación es un número entero

Question

A partir de su definición una combinación $(^n_k)$ es el número de subconjuntos distintos de tamaño k de un conjunto de n elementos.

Esto es claramente un número entero, sin embargo tenía curiosidad por saber por qué la ecuación

$ \frac {n!}{k!(n-k)!}$ siempre evalúa a un número entero.

Hasta ahora me lo imaginaba:

$n!$ es claramente divisible por $k!$ y $(n-k)!$ individualmente, pero no pude dar el salto para probar que eso $n!$ es divisible por su producto.

Answer 1

Bueno, una forma no combinatoria es inducir en $n$ utilizando el triángulo de Pascal; es decir, utilizando el hecho de que ${n \choose k} = {n-1 \choose k - 1} + {n-1 \choose k}$ (fácil de verificar directamente) y que cada ${n - 1 \choose 0}$ es sólo $1$ .

Answer 2

Ver mi publicar aquí para una sencilla prueba puramente aritmética de que todo coeficiente binomial es un número entero. La prueba muestra cómo reescribir cualquier fracción de coeficiente binomial como un producto de fracciones cuyos denominadores son todos coprimos a cualquier primo dado $\rm\:p.\,$ Esto implica que ningún primo divide el denominador (cuando se escribe en términos mínimos), por lo que la fracción es un número entero.

La propiedad clave que se encuentra en el corazón de esta prueba es que, entre todos los productos de $\rm\, n\,$ enteros consecutivos, $\rm\ n!\ $ tiene la menor potencia posible de $\rm\,p\,$ dividiéndolo - para cada primo $\rm\,p.\,$ Así, $\rm\ n!\ $ divide cada producto de $\rm\:n\:$ enteros consecutivos, ya que tiene una potencia menor de cada divisor primo. Por lo tanto, $$\rm\displaystyle\quad\quad {m \choose n}\ =\ \frac{m!/(m-n)!}{n!}\ =\ \frac{m\:(m-1)\:\cdots\:(m-n+1)}{\!\!n\:(n-1)\ \cdots\:\phantom{m-n}1\phantom{+1}}\ \in\ \mathbb Z$$

Answer 3

Según este , la mayor potencia de un número primo, $p, $ que divide $N!$ es $$s_p(N!) = \left \lfloor \frac{N}{p} \right \rfloor + \left \lfloor \frac{N}{p^2} \right \rfloor + \left \lfloor \frac{N}{p^3} \right \rfloor + \cdots$$

Desde $\dbinom{N}{M} = \dfrac{N!}{M! (N-M)!}\,, $ la pregunta entonces es, ¿es $s_p(M!) + s_p((N-M)!) \le s_p(N!)$ ?

Claramente $\left \lfloor x \right \rfloor + \left \lfloor y \right \rfloor \le x + y. $ Desde $\left \lfloor x+y \right \rfloor$ es el mayor número entero menor o igual que $x + y, $ se deduce que $\left \lfloor x \right \rfloor + \left \lfloor y \right \rfloor \le \left \lfloor x+y \right \rfloor,$

Por lo tanto, $$\left \lfloor \dfrac{M}{p^{\,i}} \right \rfloor + \left \lfloor \dfrac{N-M}{p^{\,i}} \right \rfloor \le \left \lfloor \dfrac{N}{p^{\,i}} \right \rfloor$$

para todos $i$ . Sumando, obtenemos $s_p(M!) + s_p((N-M)!) \le s_p(N!)$

De ello se desprende que $\dbinom{N}{M}$ es un número entero.

Answer 4

Otra forma de pensar en ello es la combinatoria, que es, por supuesto, la motivación.

Dejemos que $1\le k\le n$ . Considere el conjunto $S$ de todas las secuencias de $k$ números distintos entre $\{1,\dots,n\}$ . El tamaño de $S$ es $n\cdot (n-1)\cdots (n-k+1)=\frac{n!}{(n-k)!}$ . Digamos que dos secuencias en $S$ son equivalentes si el conjunto de elementos subyacente es el mismo. Entonces cada clase de equivalencia tiene exactamente $k!$ ya que cualquier elección de $k$ elementos admite $k!$ permutaciones. Así que el conjunto $S$ puede dividirse en conjuntos, cada uno de los cuales tiene un tamaño $k!$ . Así que $|S|$ es divisible por $k!$ .

Answer 5

Así es como me imagino que se justifica que un coeficiente binomial (bc) sea siempre un entero. Un bc es de la forma n!/((k!(n-k)!) . Primero consideremos sólo n!/(n-k)! que se reduce a los términos n,(n-1), : : : (n-k+2),(n-k+1) en el numerador. Si n = 14 y k =5, por ejemplo, quedaría 14!/9! = 14,13,12,11,10 en el numerador. Ahora introducimos el término restante del denominador, k!, por lo que tenemos 14,13,12,11,10 /5,4,3,2,1 para nuestra bc. Recordando cómo se crea una secuencia de enteros consecutivos (o invocando el principio de buen orden), podemos decir que cualquier número entero k aparecerá al menos una vez en cada secuencia de k enteros consecutivos, y como hay k enteros en el numerador, al menos uno será divisible a su vez por cada entero del denominador. Observa en mi ejemplo que tanto el 4 como el 3 dividen al 12. Espero que esto te sirva de ayuda, pero probablemente ya lo tengas muy claro. Bill