Cuando se $\binom{2n}{n}\cdot \frac{1}{2n}$ un número entero?

Question

En una reciente pregunta aquí, preguntando sobre el número de collares de $n$ blanco y $n$ cuentas negro (reformulado en términos de las manzanas y las naranjas), uno de los ingenuos y de las respuestas incorrectas fue que, como no se $\binom{2n}{n}$ formas de organizar las cuentas en línea recta, dividiendo por $2n$ a cuenta de la simetría del círculo corregir el recuento.

En el caso de que $p$ es un claro no es igual a dos, es claro ver que $\dfrac{(2p)!}{p!p!2p}$ tiene un factor de $p$ exactamente dos veces en el numerador sin embargo, tres veces en el denominador y por lo tanto no es aún un número entero.

Mi pregunta:

Para qué valores de a $n$ $\binom{2n}{n}\frac{1}{2n}$ ser un número entero?

Una pregunta similar se le preguntó aquí para el caso más general de al $\frac{1}{n}\binom{n}{k}$ es un número entero, generando unos gráficos muy buenos, y algunos casos especiales se mencionaron como al $\gcd(n,k)=1$, sin embargo, que no será el caso en el caso especial en que me pregunto (desde $\gcd(2n,n)=n\neq 1$ todos los $n>1$). De hecho, cuando se mira la hermosa imagen hecha por @BrunoJoyal, uno se percata de una línea negra en el centro de la imagen, que corresponden a las posiciones me interesa.

Wolfram nos da el comienzo de una secuencia $1,6,15,28,42,45,66,77,91,\dots$, Con la excepción de $42$ $77$ estos números son los primeros hexagonal números, pero que el patrón se rompe con $120$ no está en la secuencia.

Una lista más larga de los comentarios de @BanachTarski: There are 89 such numbers in the first 1000 natural numbers 1, 6, 15, 28, 42, 45, 66, 77, 91, 110, 126, 140, 153, 156, 170, 187, 190, 204, 209, 210, 220, 228, 231, 238, 266, 276, 299, 308, 312, 315, 322, 325, 330, 345, 378, 414, 420, 429, 435, 440, 442, 450, 459, 460, 468, 476, 483, 493, 496, 510, 527, 551, 558, 561, 570, 580, 589, 600, 609, 620, 651, 665, 682, 684, 696, 703, 740, 744, 748, 770, 777, 806, 812, 814, 851, 861, 868, 888, 902, 920, 924, 936, 943, 946, 950, 962, 966, 988, 989

Hay algo en especial que nos puede decir acerca de las $n$ por que este es el caso? (Por la imposición de la condición adicional en $k$ $n$ en la generalización de la cuestión, más patrones esperemos que emerge)

Answer 1

Supongamos que $p$ es un primer dividiendo $2n$. A continuación, introducir la notación $2n=2c_pp^{k_p}$ donde $c_p$ es el coprime coeficiente de $p^{k_p}$ en la factorización de $n$.

El poder de la $p$ dividiendo $(2n)!$ es $$\left\lfloor\frac{2n}{p}\right\rfloor +\left\lfloor\frac{2n}{p^2}\right\rfloor +\left\lfloor\frac{2n}{p^3}\right\rfloor +\cdots =2c_pp^{k_p-1} +\left\lfloor2c_pp^{k_p-2}\right\rfloor +\left\lfloor2c_pp^{k_p-3}\right\rfloor +\cdots$$ y del mismo modo el poder de $p$ dividiendo $(n!)^2$ es $$2\left(c_pp^{k_p-1} +\left\lfloor c_pp^{k_p-2}\right\rfloor +\left\lfloor c_pp^{k_p-3}\right\rfloor +\cdots\right) =2c_pp^{k_p-1} +2\left\lfloor c_pp^{k_p-2}\right\rfloor +2\left\lfloor c_pp^{k_p-3}\right\rfloor +\cdots$$ De modo que la potencia de $p$ dividiendo $\binom{2n}{n}$ es la diferencia: $$\left(\left\lfloor2c_pp^{k_p-2}\right\rfloor-2\left\lfloor c_pp^{k_p-2}\right\rfloor\right) +\left(\left\lfloor2c_pp^{k_p-3}\right\rfloor-2\left\lfloor c_pp^{k_p-3}\right\rfloor\right) +\cdots$$

Note that for $k_p$ large enough that $k_p-i$ is nonnegative, terms within parentheses are equal integers and contribute net zero. So this power is $$\left(\left\lfloor\frac{2c_p}{p}\right\rfloor-2\left\lfloor\frac{c_p}{p}\right\rfloor\right) +\left(\left\lfloor\frac{2c_p}{p^2}\right\rfloor-2\left\lfloor\frac{c_p}{p^2}\right\rfloor\right) +\cdots$$

These two-term expressions inside the parentheses are each either $0$ or $1$. They are $1$ precisely when $2c_p$ is between an odd multiple of $p^i$ and the next (even) multiple.

Now for $2n$ a dividir esto, debemos tener $$k_p\leq\left(\left\lfloor\frac{2c_p}{p}\right\rfloor-2\left\lfloor\frac{c_p}{p}\right\rfloor\right) +\left(\left\lfloor\frac{2c_p}{p^2}\right\rfloor-2\left\lfloor\frac{c_p}{p^2}\right\rfloor\right) +\cdots$$ when $p\neq2$ y $$\begin{align} k_2+1&\leq\left(\left\lfloor\frac{2c_2}{2}\right\rfloor-2\left\lfloor\frac{c_2}{2}\right\rfloor\right) +\left(\left\lfloor\frac{2c_2}{2^2}\right\rfloor-2\left\lfloor\frac{c_2}{2^2}\right\rfloor\right) +\cdots\\ \implies k_2&\leq\left(\left\lfloor\frac{2c_2}{2^2}\right\rfloor-2\left\lfloor\frac{c_2}{2^2}\right\rfloor\right) +\left(\left\lfloor\frac{2c_2}{2^3}\right\rfloor-2\left\lfloor\frac{c_2}{2^3}\right\rfloor\right) +\cdots\end{align}$$

Conversely if these inequalities hold for all $p$ dividing $n$ then $2n$ divides $\binom{2n}{n}$. So this rephrases the question into a question about what the relationship is between the powers of primes dividing $n$ and the coprime coefficients of those primes:

So $2n$ divides $\binom{2n}{n}$ if and only if

$k_2\leq\left(\left\lfloor\frac{2c_2}{2^2}\right\rfloor-2\left\lfloor\frac{c_2}{2^2}\right\rfloor\right) +\left(\left\lfloor\frac{2c_2}{2^3}\right\rfloor-2\left\lfloor\frac{c_2}{2^3}\right\rfloor\right) +\cdots$ and for all $p\neq2$, $k_p\leq\left(\left\lfloor\frac{2c_p}{p}\right\rfloor-2\left\lfloor\frac{c_p}{p}\right\rfloor\right) +\left(\left\lfloor\frac{2c_p}{p^2}\right\rfloor-2\left\lfloor\frac{c_p}{p^2}\right\rfloor\right) +\cdots$.

Some consequences:

• if a prime $p$ dividing $n$ is larger than twice its coprime coefficient, then $2n$ will not divide $\binom{2n}{n}$, because the right-hand side of the inequality will be $0$. This excludes numbers like $n=10,44,303$, etc.
• con la pequeña excepción de $3\cdot5$, un producto de dos números primos nunca va a aparecer en esta secuencia, debido a que $1=k_p \not\leq\left(\left\lfloor\frac{2(p+2)}{p}\right\rfloor-2\left\lfloor\frac{p+2}{p}\right\rfloor\right)=(2-2)=0$.
• más generalmente, $n=pq$ es en la secuencia, si y sólo si $2p$ está justo encima de una extraña múltiples de $q$ $2q$ está justo encima de una extraña múltiples de $p$. Esto incluye a $n$ como $7\cdot11$, pero excluye $n$ como $13\cdot19$.
• todo perfecto números en la secuencia (nota: estos son un tipo especial de hexagonal número, se analiza a continuación).

---

Se han observado muchos hexagonal números en la secuencia. Que no es exactamente una sorpresa teniendo en cuenta estas desigualdades. El $m$th hexagonal número es $n=m(2m-1)$. Tenga en cuenta que $m$ $(2m-1)$ son coprime. Para los pequeños $m$, $2m-1$ es el primer poder más de la mitad del tiempo, y es justo por debajo de un múltiplo de su coprime coeficiente. Esto hace que muchos de los primeros números hexagonales pasado el obstáculo de la satisfacción de la desigualdad por su mayor primer factor de potencia.

Para tal $m$ (donde $2m-1$ es una fuente primaria de energía) para los más pequeños de $p$ dividiendo $m$, su coprime coeficiente de es$\frac{m}{p^{k_p}}(2m-1)=2p^{k_p}\left(\frac{m}{p^{k_p}}\right)^2-\frac{m}{p^{k_p}}$, por lo que será justo debajo de un múltiplo de $p^i$ mientras $\frac{m}{p^{k_p}}<p^i$. Con pequeño $m$, e $p^{k_p}$ la mayor potencia principal factor de $m$, esta última condiciones es automático, compensación de otro obstáculo para la membresía en la secuencia.

Para los más pequeños primos divisores de $m$ (si hay alguna), se trata de si es o no $\frac{m}{p^{k_p}}$ está justo al norte de un múltiplo de $p^i$ o de un extraño múltiples. Hay al menos un 50/50 de tiro, pero recuerda que muchos de los primeros números hexagonales incluso no tiene un tercer factor principal. Así que estos son todos los argumentos de por qué muchos de los primeros hexagonal números en la secuencia.

Nada de lo dicho hasta el momento direcciones hexagonal números donde $2m-1$ no es primo. Algunos hexagonal números todavía no la desigualdad, como se señaló con $120$. Con ese número: $$1=k_3\not\leq\left(\left\lfloor\frac{80}{3}\right\rfloor-2\left\lfloor \frac{40}{3}\right\rfloor\right)+\left(\left\lfloor\frac{80}{9}\right\rfloor-2\left\lfloor\frac{40}{9}\right\rfloor\right)+\left(\left\lfloor\frac{80}{27}\right\rfloor-2\left\lfloor\frac{40}{27}\right\rfloor\right)=(26-26)+(8-8)+(2-2)=0$$ just barely fails. Here the issue boils down to $81$ (a power of $3$) being ever so slightly larger than $80$ (twice $3$'s coefficient. So the left term in the parentheses pairs never gets a chance to beat out the right term.

Here is a table investigating early hexagonal numbers. The above paragraphs "guarantee" that $n=m(2m-1)$ is part of this sequence when $2m-1$ and $m$ are prime powers.

m 2m-1 n 2m-1 prime power? factorization n in sequence 2 3 6 yes pq guaranteed 3 5 15 yes pq guaranteed 4 7 28 yes p^2q guaranteed 5 9 45 yes p^2q guaranteed 6 11 66 yes pqr yes 7 13 91 yes pq guaranteed 8 15 120 no p^3qr no 9 17 153 yes p^2q guaranteed 10 19 190 yes pqr yes 11 21 231 no pqr yes 12 23 276 yes p^2qr yes 13 25 325 yes p^2q guaranteed 14 27 378 yes pq^3r yes 15 29 435 yes pqr yes 16 31 496 yes p^4q guaranteed 17 33 561 no pqr yes 18 35 630 no pq^2rs no 19 37 703 yes pq guaranteed

Note that the two failures have high exponent ($5$) and that there are just as many successes which also have exponent $5$.

Resumen de los pensamientos en hexagonals: la factorización de números hexagonales les da una protuberancia en general enteros para ser parte de esta secuencia. No estoy seguro de que el golpe va a sobrevivir en grandes números hexagonales, ya que tendrá una más amplia gama de primer factores de potencia.

Answer 2

Sólo para el propósito de responder a "¿para qué valores de" parte, tomemos nota de $$K_n=\binom{2n}{n}\cdot \frac{1}{2n}$$

$$K_n=\frac{1}{2n} \cdot \frac{2n \cdot (2n-1)\cdot ... \cdot (n+1)}{1 \cdot 2 \cdot ... \cdot n}=$$ $$\frac{2n-1}{n^2} \cdot \frac{(2n-2)\cdot ... \cdot (n+1) \cdot n}{1 \cdot 2 \cdot ... \cdot (n-1)}=\frac{2n-1}{n^2} \cdot \binom{2(n-1)}{n-1}$$

Desde este punto de vista: $$K_n \in \mathbb{N} \Leftrightarrow n^2 \mid \binom{2(n-1)}{n-1}$$ debido a $\gcd(n^2, 2n-1)=1$

Esto nos lleva a otra observación: $$2n-2 \equiv -2 \pmod{n}$$ $$2n-3 \equiv -3 \pmod{n}$$ $$...$$ $$n+1=2n-(n-1) \equiv -(n-1) \pmod{n}$$ Así que: $$(2n-2)\cdot ... \cdot (n+1) \equiv (-1)^{n-2} (n-1)! \pmod{n}$$

O $$(2n-2)\cdot ... \cdot (n+1)=n \cdot Q + (-1)^{n-2} (n-1)!$$ Y $$K_n=\frac{2n-1}{n^2} \cdot \binom{2(n-1)}{n-1}=\frac{2n-1}{n}\cdot \left ( \frac{n \cdot Q}{(n-1)!} +(-1)^{n-2} \right )$$

La única vez que esto no es cierto es que, cuando: $$K_n \in \mathbb{N} \Leftrightarrow (n-1)! \equiv 0 \pmod{n}$$

E. g. $K_6 \in \mathbb{N}$ porque $5! \equiv 0 \pmod{6}$

$K_{15} \in \mathbb{N}$ porque $14! \equiv 0 \pmod{15}$

...

Es obvio que $n$ puede no ser la mejor, ya que, según Wilson, el teorema tendríamos $$(n-1)! \equiv -1 \pmod{n}$$

Answer 3

Un poco largo para un comentario, pero no es una respuesta...

Necesarias, pero insuficientes, la condición es que el número de "$1$"s en la representación binaria de $n$ debe superar la potencia de $2$$2n$. Ver la OEIS: 1-secuencia de conteo ("a(n) es también el mayor entero tal que 2^(n) divide binomial(2n, n)").

Así, por $n=4$, el número de $1$s en su representación binaria es $1$, pero $2\cdot4 = 2^3$, lo $2n$ no divide $\binom{2n}{n}$. Con pequeños experimentos numéricos, esto parece que matar a cerca de la mitad de los números enteros.

Lamentablemente, no sé similar caracterización de cualquier otro de los números primos.