Deje $n$ ser un entero positivo y $p$ un primo, ¿cómo puedo demostrar que el mayor poder de $p$ que divide $\binom{2n}{n}$ es exactamente el número de $k\geq1$ tal que $\lfloor 2n/p^k\rfloor$ es impar?
Respuestas
¿Demasiados anuncios?
larryb82
Puntos
158
SUGERENCIA:
Esta es una útil aproximación general a las preguntas relativas a la divisibilidad de la factoriales y binomios. Cuál es la potencia máxima de $p$ que divide $n!$? Bien $p, 2p, 3p,...$ y a todos los múltiplos de a $n$ brecha $n!$, así que al menos $ \left\lfloor \frac{n}{p} \right\rfloor $. Pero eso no fue recuento $2$ competencias para cada plaza, $p^2, 2p^2...$. Así que tenemos que añadir otro $\left\lfloor \frac{n}{p^2} \right\rfloor$. Y ahora necesitamos a cuenta de los cubos y así sucesivamente, por lo que el mayor poder de $p$ que divide $n!$ $$ \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor. $$
Ahora, desde la $ \binom{2n}{n} = \frac{(2n)!}{(n!)^2} $, el más alto poder de $p$ a dividir que es dado por: $$ \sum_{k=1}\left( \left\lfloor \frac{2n}{p^k} \right\rfloor - 2\left\lfloor \frac{n}{p^k}\right\rfloor \right) $$
Investigar el término general en los casos y deducir su resultado.
Edit: Thijs, su reciente edición terminó siendo esencialmente mi post.
Vamos a escribir este coeficiente binomial un poco más
$$\binom{2n}{n} = \frac{2n \cdot (2n-1) \cdot \ldots \cdot (n+1)}{n \cdot (n-1) \cdot \ldots \cdot 1}$$
Encima tenemos todos los números entre el$n + 1$$2n$, mientras que los de abajo tenemos todos los números de$1$$n$. Ahora supongamos $\lfloor 2n/p\rfloor = 2m + 1$. Entonces hay exactamente $m + 1$ números entre el $(n+1)$ $2n$ que son divisibles por $p$, e $m$ números entre el $1$ $n$ divisible por $p$. Así que esto le da a ese $p \ | \ \binom{2n}{n}$, y de hecho esto le da exactamente un factor de $p$. Alternativamente, si $\lfloor 2n/p\rfloor = 2m$, a continuación, los factores por encima y por debajo de cancelar, sin dar restantes factor de $p$.
De igual manera, supongamos $\lfloor 2n/p^2\rfloor = 2m + 1$. A continuación, obtenemos un factor adicional $p^2$ arriba, en comparación a por debajo de la barra. Sin embargo, ya hemos contado el único de los factores de $p$ cuando se comprueba la paridad de $\lfloor 2n/p\rfloor$, por lo que solo tenemos un factor adicional $p$. Usted puede seguir este para mayor $k$, hasta que en algún punto de $p^k > 2n$ $\lfloor 2n/p^k\rfloor = 0$ todos los $k$.
Si desea más de una intuición para esto, considere por ejemplo,$\binom{132}{66}$$p = 5$. A continuación,$\lfloor 132/5\rfloor = 26$, por lo tanto por encima como por debajo llegamos $13$ números divisibles por $5$. Estas son las $70, 75, \ldots, 130$ por encima y $5, 10, \ldots, 65$ por debajo. De modo que estos factores $p$ cancelar. Desde $\lfloor 132/25\rfloor = 5$ obtenemos $3$ números ($75, 100, 125$) por encima y $2$ números ( $25, 50$ ), por debajo contribuyendo otro $p$ a la del producto. Finalmente, $125$ otro factor que contribuye $p$ el número, por lo $\binom{132}{66} = 5^2 q$,$5 \not| \ \ q$.
Edit: quizás podrías hacer la de arriba un poco más riguroso y más corto por explicar exactamente cómo muchos factores $p$ están en el producto $2n \cdot (2n-1) \cdot \ldots \cdot (n+1)$, y de cómo muchos de los factores de $p$ hay en el producto $n \cdot (n-1) \cdot \ldots \cdot 1$. El número de factores de $p$ en el producto $(2n)!$ es simplemente:
$$\lfloor \frac{2n}{p} \rfloor + \lfloor \frac{2n}{p^2} \rfloor + \ldots + \lfloor \frac{2n}{p^k} \rfloor + \ldots$$
El número de factores en $n!$ es exactamente
$$\lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + \ldots + \lfloor \frac{n}{p^k} \rfloor + \ldots$$
Por lo que el número de factores en $\binom{2n}{n}$ es
$$\left(\lfloor \frac{2n}{p} \rfloor + \lfloor \frac{2n}{p^2} \rfloor + \ldots + \lfloor \frac{2n}{p^k} \rfloor + \ldots\right) - 2\left(\lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + \ldots + \lfloor \frac{n}{p^k} \rfloor + \ldots\right)$$
Puede completar la prueba señalando que
$$\lfloor \frac{2n}{p^k} \rfloor - 2 \lfloor \frac{n}{p^k} \rfloor = \begin{cases} 1 & \text{if } \lfloor 2n/p^k \rfloor \text{ odd} \\ 0 & \text{if } \lfloor 2n/p^k \rfloor \text{ even} \end{cases}$$
