Cálculo de Spivak: Pruebas sobre el triángulo de Pascal

Question

El problema 3 del capítulo 2 de Cálculo de Spivak plantea 5 problemas relacionados con el triángulo de Pascal. El primero de ellos te pide que demuestres que $\binom{n+1}{k}$ = $\binom{n}{k-1} + \binom{n}{k}$ que era bastante sencillo.

La segunda tarea era demostrar por inducción que $\binom{n}{k}$ es siempre un número natural. Para ello, adopté el enfoque de la recursión: dada la demostración de la igualdad anterior, cualquier $\binom{n}{k}$ puede descomponerse en $\binom{n-1}{k-1} + \binom{n-1}{k}$ y así sucesivamente, descomponiendo cada valor hasta que cada binomio alcance un $n$ o $k$ valor de $0$ En ese momento se evalúan a 1 y se pueden sumar. $1$ es un número natural, por lo que la suma de cualquier número de $1$ s debe ser, por tanto, un número natural. Esta prueba me parece que carece de formalidad, pero creo que la lógica es apropiada.

La tercera tarea, sin embargo, no sé qué hacer con ella. Dice así: "Dé otra prueba de que $\binom{n}{k}$ es un número natural demostrando que $\binom{n}{k}$ es el número de conjuntos de exactamente $k$ enteros elegidos cada uno de ellos entre $1, \cdots,n$ ." La palabra inducción no se utiliza en el aviso, y puedo ver que esto parece ser cierto a través de las primeras filas del triángulo, pero cómo uno podría demostrar rigurosamente algo como esto, no lo sé. Además, habiendo demostrado que esto es cierto, ¿es el enlace de eso a $\binom{n}{k}$ ¿ser siempre un número natural es sólo el hecho de que no puede haber conjuntos parciales o negativos, y por lo tanto debe ser un número natural?

Answer 1

Por definición ${n\choose k}=\frac{n!}{k!(n-k)!}=\frac{n\cdot (n-1)\cdot\ldots\cdot (n-k+1)}{k!}=\frac{n}{k}\cdot\frac{n-1}{k-1}\cdot\ldots\cdot\frac{n-k+1}{1}$ .

Ahora considere $\{1,\ldots,n\}$ . Hay $n$ para elegir un número entero de este conjunto. Dejemos que este número entero se llame $a_1$ .

Ahora hay $n-1$ posibilidades de elegir un elemento del conjunto $\{1,\ldots,n\}\setminus \{a_1\}$ .

Al iterar este procedimiento obtenemos $n\cdot (n-1)\cdot\ldots\cdot (n-k+1)$ posibilidades de elegir $(a_1,\ldots,a_k)$ de $\{1,\ldots,n\}$ . Ahora bien, observe que hemos contado algunas posibilidades varias veces, por ejemplo $a_1=1,a_2=2$ y $a_1=2,a_2=1$ resultado a los mismos enteros elegidos. Así que tenemos que dividir por el número de posibilidades para ordenar $k$ elementos que es $k!$ (hay $k$ posibilidades para colocar el primer entero, $k-1$ para colocar el segundo, etc.).

Answer 2

Estaba escribiendo algo en la línea de lo que ya ha explicado tan bien @Nightgap :), pero por si acaso y espero que no te importe que no sea realmente una respuesta a tu pregunta específica planteada más arriba, voy a publicar lo que iba a ser un apéndice que tiene un sabor diferente y es bueno saberlo si no lo has visto (lo encontré en la Introducción Concisa a la Teoría de Números de Alan Baker hace eones - ¡un pequeño gran libro!).

Así que dejemos $\lfloor x\rfloor$ sea el mayor número entero $\leq x$ . Dejemos que $p$ sea un primo, entonces hay $\lfloor n/p \rfloor$ elementos del conjunto $\{1,2,...n\}$ divisible por $p$ , $\lfloor n/p^2 \rfloor$ divisible por $p^2$ y así sucesivamente. Esto significa que la mayor potencia $k$ de $p$ tal que $p^k |n!$ está dada por: $$k=\sum_{j=1}^{\infty}\lfloor n/p^j\rfloor \qquad \qquad (1)$$

Esencialmente estás añadiendo a la suma cada vez que subes una potencia prima, así que, por ejemplo, primero recoges todas las potencias unitarias con el término $\lfloor n/p \rfloor$ pero entonces hay que añadir a estos la contribución extra de los múltiplos del cuadrado primo con el $\lfloor n/p^2 \rfloor$ término, luego para los cubos, y así sucesivamente. Así que ahora tenemos una expresión explícita para la potencia máxima de un primo $p^k$ de tal manera que divide $n!$

Ahora bien, ten en cuenta que en general: $$\lfloor x+y \rfloor \geq \lfloor x\rfloor + \lfloor y \rfloor$$ (por ejemplo, si las partes fraccionarias de $x$ y $y$ suman un número entero), por lo tanto: $$ \lfloor n/p^j \rfloor \geq \lfloor (n-k)/p^j \rfloor + \lfloor k/p^j \rfloor \qquad \qquad (2)$$

Pero entonces: $$ {n \choose k}=\frac{n!}{k!(n-k)!}$$ ...debe ser un número natural ya que por (1) y (2) todas las potencias primos en el denominador serán 'absorbidas' por las del numerador. Espero que esto tenga sentido y, aunque no es la forma en que usted respondería a su ejercicio, creo que es una buena perspectiva para tener en los coeficientes binomiales, además de la importante combinatoria. Saludos.

Answer 3

Por comodidad, dejemos que $S_n = \{x_1, x_2, x_3, \dots, x_n\}$ representan un conjunto de $n$ objetos distintos.

Utilicemos $_nC_k$ para representar el número de maneras de seleccionar $k$ objetos de $S_n$ .

Entonces, ¿qué hace $_{n+1}C_k$ ¿se ve así?

Un elemento de esta selección incluirá el objeto $x_{n+1}$ o no lo hará. Ya sabemos que hay $_nC_k$ formas de elegir $k$ objetos de los objetos $x_1, x_2, \dots, x_n$ . Entonces, ¿cómo contamos el número de formas de seleccionar $k$ objetos que contienen $x_{n+1}$ . Fácil; seleccionamos $k-1$ objetos de $S_n$ {hay $_nC_{k-1}$ tales formas} y luego añadir $x_{n+1}$ a la colección.

De ello se desprende que $_nC_{k-1} + _nC_k = _{n+1}C_k$ .