¿Por qué es ${2n \choose n}/2 $ impar si y sólo si $n=2^k$?

Question

Si tenemos en cuenta los números de ${2n \choose n}/2 $ $n$ pequeño:

[ 1, 1 ][ 2, 3 ][ 3, 10 ][ 4, 35 ][ 5, 126 ][ 6, 462 ][ 7, 1716 ][ 8, 6435 ] [ 9, 24310 ][ 10, 92378 ][ 11, 352716 ][ 12, 1352078 ][ 13, 5200300 ] [ 14, 20058300 ][ 15, 77558760 ][ 16, 300540195 ]

se observa que el ${2n \choose n}/2 $ es impar si y sólo si $n$ es una potencia de $2$.

Podemos comprobar fácilmente con un equipo que es cierto para $n \le 2^{10}$, por lo que podemos esperar es cierto en general.

Pregunta: ¿Cuál es la prueba?

Answer 1

Vamos que definir el $2$-ádico de altura como $$\nu_2(n)=\max\{h\in\mathbb{N}: 2^h\mid n\}.\tag{1}$$ Legendre del teoremada $$ \nu_2(n!)=\sum_{k\geq 1}\left\lfloor\frac{n}{2^k}\right\rfloor \tag{2} $$ de ahí se sigue que: $$ \nu_2\binom{2n}{n}=\nu_2\left(\frac{(2n)!}{n!^2}\right)=\sum_{k\geq 1}\left(\left\lfloor\frac{2n}{2^k}\right\rfloor-2\left\lfloor\frac{n}{2^k}\right\rfloor\right)=\sum_{k\geq 1}f_k(n). \tag{3}$$ Podemos observar que la $f_1(n)$ es igual a $1$ si $n$ es impar y $0$ lo contrario.
En general, $f_k(n)$ depende de la estructura de la representación binaria de $n$.
A partir de eso, no es difícil demostrar la dada conjetura - ya que es el que da ese $\nu_2\binom{2n}{n}$ es igual a uno si hay una sola $1$ en la representación binaria de $n$.

Answer 2

Por Kummer del teorema, el número de factores primos $p$ en un coeficiente binomial $\binom {a+b}a=\binom {a+b}b$ es el número de carreras que surgen cuando la adición de $a+b$ representan como números en base$~p$. Tomando $p=2$$a=b=n$, es fácil de ver que conseguir un equipaje (y por lo tanto un factor de$~2$) para cada uno de los bits '$1$' en la representación binaria de $n$; usted consigue uno llevar, precisamente, cuando la representación tiene un único bit '$1$', que es al $n$ es una potencia de $2$.

Answer 3

[Me encantaría ver una combinatoria argumento.]

Más generalmente, si $d$ es el mayor entero tal que $2^d$ divide $\binom{2n}{n}$, $d$ es el número de no-cero dígitos binarios de $n$.

No hay una fórmula general para la máxima potencia de un primer $p$ que divide $m!$:

$$\sum_{k=1}^{\infty}\left\lfloor\frac{m}{p^k}\right\rfloor$$

Por lo que el número de facultades de $2$ que dividen $\binom{2n}{n}=\frac{(2n)!}{n!n!}$ es:

$$\sum_{k=1}^{\infty} \left(\left\lfloor\frac{n}{2^{k-1}}\right\rfloor -2\left\lfloor\frac{n}{2^k}\right\rfloor\right)$$

Cada término es positivo, debido a $\lfloor 2x\rfloor - 2\lfloor x\rfloor\geq 0$.

Al $2^{k-1}\leq n<2^k$, obtenemos un plazo de $1$ de esta suma.

Al $n=2^{k-1}$ este es el único no-cero término de esta suma.

Ahora, si $\frac{n}{2^{k-1}}$ es un número entero impar, entonces el $k$el plazo es de nuevo $1$. La única manera de que la suma de los ser $1$ es si estos dos términos son los mismos.

Lo que en realidad se puede mostrar es que el $k$th término de esta suma es $(k-1)$th dígito binario de $n$.

---

Debe haber algún argumento combinatorio. Podemos ver que $\binom{2n}{n}$ es divisible por $2$ combinatoria mediante el complemento de la función de la $n$-subconjuntos de a $\{1,2,\dots,2n\}$. Hay otra acción de la orden de $2$ podemos encontrar que los viajes con este si $n$ no es una potencia de $2$?

Answer 4

Podemos empezar con $\nu_2(2^k!)=2^k-1$. Esto da inmediatamente el resultado $n=2^k$ porque $\nu_2(\binom{2n}{n})=\nu_2(2n!)-2\nu_2(n!)$.

Luego observamos que $n$ puede ser escrito como $n=\sum\limits_{i=0} 2^i$ y entonces el $\nu_2(n!)=\sum\limits_{i\in I} \nu_2(2^i!)$.

El resultado sigue trivial.