¿$f (x) = \sum_ {t} {x \choose t}$ {x n \choose k-t} - par o impar?

Question

La siguiente función de estallar en mi investigación: $$f(x)=\sum_{\matriz{0\le t\le k \\ t\equiv_p un}}{x \c}{n-x \elegir k-t}$$

Donde:

1. $n,k$ son números naturales y $k\le$n.
2. $t$ es tomado a través de todos los enteros entre $0$ y $k$ que $t$ es equivalente a $un$ modulo de un primer $p$.
3. $x$ es un número natural entre $0$ y $n$.

Así que la función está determinada por los parámetros $n,k,p,$. Estoy particularmente interesado en el caso de p $=3$ y $a=0$ ($a=1$ es relevante).

Mi principal pregunta es: ¿hay una manera de caracterizar (en lugar de simplemente computing) para que valores de $x$ (dado $n,k,p,$) los valores de $f(x)$ será números impares?

El primer paso parece estar respondiendo a la pregunta de cuando ${\alpha \elegir \beta}$ es impar y cuando es aún. Esta pregunta se la hicieron aquí y recibió una hermosa solución; sin embargo, no veo la manera de aplicar esa solución para "mi" de la función.

Answer 1

Esto sin duda está lejos de ser una respuesta completa, pero espero que sea útil. Voy a tratar de describir mi proceso de pensamiento, de modo que no parece que este salió de la nada.

La experimentación

Me fijo $p=3$ y en un principio se trató de examinar $a=0$ y $a=1$, aprovechando el corolario de Lucas Teorema de la cuestión que enlaza. Utilizar el color negro para "raro" y blanco para, incluso, llegué a tablas como la siguiente para los pequeños $n$. $n=0$ es la parte superior izquierda de la tabla, $n=3$ es la parte superior derecha, $n=31$ es la parte inferior derecha. Dentro de una tabla, cada fila es un valor de $k$ (a partir de $0$) y cada columna tiene un valor de $x$:

($a=0$) ($a=1$)

Tenemos una linda patrones cuando $n$ es uno menos que una potencia de 2$$, especialmente en la parte superior izquierda de las tablas (cuando $x+k\le$ n) y para $a=0$, donde se ve sobre todo como el triángulo de Sierpinski o el Walsh de la matriz. De hecho, tras la inspección, la expresión es un poco raro para $x+k>n$ desde entonces $n-x$ descienda por debajo de $k$, pero $k-t$ sube a $k$. A partir de ahora me centraré sólo en $a=0$ para $x+k\le$ n.

Por ejemplo, la rotación de la imagen para $n=31$ nos da

Esto se ve bonito y sugerente, pero quizás sea un poco amplia. Podemos utilizar hexagonal llena los círculos para ver esto un poco mejor:

Ahora, con el fin de ver un patrón, se puede tratar de relacionar este tema con el $n=15$ caso, que es precisamente la cuarta parte superior de la imagen entera. Pensé que centrarse en los siete aislados 1s (con puntos marrones) que apareció en $n=31$ "en" la gran diferencia de $n=15$. El uso de diferentes colores y algunos de la capa de trabajo en Gimp.

Esta foto es un poco difícil de analizar, pero, básicamente, al alinear las cosas así, el aislado 1s que aparecen de la nada están en los centros de $\pastilla$s con 0 en los vértices de $n=15$. De hecho, los centros de todos los $\pastilla$s (no sólo verticales) parecen seguir una regla simple: se trata de un $1$ si hay cero o dos $\pastilla$-vértices que son $1$ y y $0$ lo contrario. Los pequeños puntos que se encuentran bajo un gran punto a punto (de modo que ellos no son los centros de un $\pastilla de$) comparten el mismo valor.

Por desgracia, esta $\pastilla de$-en-toda-la dirección de la idea es un poco difícil de trabajar, y deja a un problema de recursividad en la parte inferior del triángulo. Si nos alineamos las cosas un poco más natural, obtenemos esto:

Que dejó claro que cada segunda fila de $n=31$ es una fila de $n=16$ pero con cada entrada se duplicó: (1,0,1) se convirtió en (1,1,0,0,1,1), etc.

La recurrencia

Poner estas ideas junto con un poco de ensayo y error me llevó a una recurrencia con la potencia de 2 en $n$ como un parámetro. Pero desde $n=15$ es la parte superior de $n=31$, etc. $n$ es en realidad no se necesita cuando está restringida a ser uno menos que una potencia de 2$$. Si la fila del triángulo de $r$ comienza en $1$, y la columna $c$ va desde $1$ $r$ inclusive, a la paridad de $b_{r,c}$ está dado por la siguiente (me confirmó el patrón de hasta $n=2^8-1$, pero esto es en última instancia una conjetura):

Para hacer la recurrencia de trabajo, establecer $b_{r,c}=0$ para $r<1$ o $c<1$ o $c>r$. A continuación, vamos a $R=\lceil r/2\rceil$ y $C=\lceil c/2\rceil$ Tenemos $b_{1,c}=1$ si $c=1$ y $0$ lo contrario. Entonces, para $r>1$, $b_{r,c}=b_{R,C}$ cuando $r$ es aún y cuando $r$ y $c$ son ambos impares. En el caso restante de $r>1$ donde $r$ es impar y $c$ es par, tenemos $b_{r,c}=f\left(b_{R-1,C} b_{R,C} b_{R,C+1},b_{R+1,C+1}\right)$ donde $f$ es una función que genera $1$ cuando dos o de cuatro de sus argumentos son $0$ y salidas $0$ lo contrario. (Por desgracia, algunos experimentos sugieren que cualquier natural recurrencia dependiendo en la mayoría de los tres términos anteriores no funciona).

Para conectar de nuevo el problema original, $c=x+1$ (por lo que $x=c-1$) y $r=x+k+1$ (por lo que $k=r-c$). Admito que no sé cómo empezar a resolver esta recurrencia, y OEIS no parece arrojar alguna luz sobre esto (aunque me presentó a la apariencia similar Walsh de la matriz). Asimismo, no se han comprobado que esto funciona para todo $n$ que son uno menos que una potencia de 2$$.

Bono

Aquí una foto de la $n=255$: