$C(n,p)$ ¿impar o impar?

Question

¿Podemos determinar si un coeficiente binomial $C(n,p)$ es par o impar, sin calcular su valor? ( $p\lt n$ , $p$ y $n$ son enteros positivos)

Answer 1

Hay un hermoso resultado de Kummer que dice que si $q$ es un primo, entonces la mayor potencia de $q$ que divide $\binom{m+n}{n}$ , $m$ y $n$ no negativo, es el número de cargas cuando $m$ y $n$ se añaden en la base $q$ .

Como corolario, obtenemos el Teorema de Lucas mencionado por Michael Lugo: obtenemos un acarreo en la suma si y sólo si hay un $k$ de manera que el $k$ dígito de $m+n$ en la base $q$ es menor que el $k$ dígito de la base $q$ ampliación de $n$ Así que $\binom{m+n}{n}$ es divisible por $q$ si y sólo si existe un $k$ de manera que el $k$ dígito de la base $q$ ampliación de $m+n$ es menor que el $k$ dígito de la base $q$ ampliación de $n$ .

Así, para determinar si $\binom{n}{p}$ es impar, sólo hay que saber si hay al menos un carry al añadir $p$ y $n-p$ en la base $2$ se obtiene una carga exactamente cuando el $k$ dígito binario de ambos $n-p$ y $p$ es $1$ .

Así que escribe $p$ y $n-p$ en binario, un dígito a la vez (desde el menos significativo al más significativo), hasta conseguir que ambos sean $1$ o escribir $p$ y $n$ un dígito binario a la vez, hasta obtener un $1$ en $p$ y un $0$ en $n$ . Si esto sucede, $\binom{n}{p}$ es par; en caso contrario, es impar.

El documento de Andrew Granville Propiedades aritméticas de los coeficientes binomiales está lleno de cosas interesantes sobre los coeficientes binomiales y su divisibilidad. La prueba del Teorema de Kummer se puede encontrar allí . También hay otros formatos disponibles .

Answer 2

Sí.

Sólo necesitamos saber cuántas potencias de dos aparecen en la factorización de primos de C(n,p). El número de potencias de dos que aparecen en la factorización prima de $n!$ es $\lfloor n/2 \rfloor + \lfloor n/4 \rfloor + \lfloor n/8 \rfloor + \cdots$ -- contar todos los múltiplos de dos, de cuatro, de ocho, etc. Esto resulta ser $n$ menos el número de unos en la expansión binaria de $n$ .

Resulta que esto se reduce a lo siguiente C(n,p) es impar si y sólo si cada bit de la expansión binaria de $p$ es menor o igual que el bit correspondiente de la expansión binaria de $n$ . Esto se debe a Lucas.

Answer 3

Ya comenté con un enlace de Wikipedia más arriba, pero sólo quiero añadir que si se ejecuta la recurrencia del triángulo de Pascal $\bmod 2$ lo que se obtiene es una secuencia de aproximaciones a la Triángulo de Sierpinski . Así que el resultado que se desprende del teorema de Lucas es un algoritmo explícito no recursivo para trazar el triángulo de Sierpinski.

También quiero aprovechar esta oportunidad para mencionar un artículo que discute las generalizaciones de este problema, y que es bastante entretenido de leer y quizás tiene uno de los títulos más extraños de cualquier artículo de matemáticas: Granville's El cerebro de Zaphod Beeblebrox y la quinta y novena fila del triángulo de Pascal .

Answer 4

Motivado por una pregunta duplicada que se ha hecho hoy, me gustaría ofrecer un enfoque alternativo al problema.

Dejemos que $C_n^r$ sea el conjunto de subconjuntos de $\{1,\ldots,n\}$ que tienen cardenal $r$ . Definir la función $\sigma:C_n^r\to C_n^r$ dado por $$k\in\sigma(A)\Leftrightarrow n-k\in A$$ Dejemos que $S_n^r$ sea el conjunto de los puntos fijos de $\sigma$ y $T_n^r=C_n^r-S_n^r$ . Está claro que $f\circ f=id$ . Así, $|T_n^r|$ es par y $|C_n^r|$ y $|S_n^r|$ tienen la misma paridad.

Estudiemos la paridad de $|S_n^r|$ . Representar cada elemento de $A\in S_n^r$ con una palabra binaria de longitud $n$ cuyo $k$ es el dígito $1$ si $k\in A$ y $0$ de lo contrario. Así, los elementos de $S_n^r$ son las palabras simétricas. Para cada una de estas palabras simétricas:

• Si $n$ es impar Hay un dígito central. Si $r$ es impar debe ser $1$ Si no es así $0$ . En cualquier caso, la palabra está determinada por la $\lfloor n/2\rfloor$ primeros dígitos y $\lfloor r/2\rfloor$ de estos dígitos son $1$ 's. Por lo tanto, $$|S_n^r|=\binom{\lfloor n/2\rfloor}{\lfloor r/2\rfloor}$$

• Si $n$ es incluso , $r$ debe ser uniforme y debe haber $r/2$ de $1$ de cada lado. Entonces

$$|S_n^r|=\left\{ \begin{array}{cl} \binom{\lfloor n/2\rfloor}{\lfloor r/2\rfloor}&\text{ if $r$ is even}\\ 0&\text{ otherwise} \end{array} \right.$$

Así, tenemos un método que permite obtener la paridad de $\binom nr$ en un máximo de $\log_2 r$ pasos.

Ejemplo : $$\binom{1000}{376}\equiv\binom{500}{188}\equiv\binom{250}{94}\equiv\binom{125}{47}\equiv\binom{62}{23}\equiv 0\pmod 2$$

Answer 5

Me sorprende que nadie haya mencionado esto.

Aquí hay un gráfico de la paridad de ${n\choose p}$ para $n,p\le256$ . El negro es impar.

Se obtiene un patrón que es exactamente el Triángulo de Sierpinski . El análisis de este patrón conduce naturalmente a una forma de calcular directamente la paridad de ${n\choose p}$ .