enteros que son sumas de coeficientes binomiales:$\sum_i {n \choose k_i}$

Question

Deje $n$ ser un número entero. Para $S$ un subconjunto de $\{0,\dots,n\}$, definir $$m(S) = \sum_{k \in S} {n \choose k}.$$ Deje $M_n$ el conjunto de los enteros de la forma $m(S)$ para todos los conjuntos de $S \subset \{0,\dots,n\}$. Obviamente $M_n \subset \{0,\dots,2^n\}$ e de $n=1,2,3$ esta inclusión es una igualdad. Para $n \geq 4$ sin embargo, esta inclusión no es una igualdad, como por ejemplo $n-1$ no está en $M_n$.

¿Qué se puede decir acerca de la $M_n$? Hay una forma sencilla de reconocer si un número menor que $2^n$ es de $M_n$? Podemos calcular o estimar la proporción $|M_n|/(2^n+1)$ de los elementos de $\{0,\dots,2^n\}$ que están en $M_n$?

Hago esta pregunta principalmente por curiosidad, pero los elementos de la forma $m(S)$ aparecido recientemente en el papel en el que estoy trabajando.

Answer 1

Como Gerry notas, es en la OEIS si también permitimos el vacío suma de $0$. Como ya he comentado, la descripción parece un poco apagado.

Los condes (a $n=30$) en efecto, parecen estar cerca del límite superior de $3^{(n+1)/2}$ (por extraño $n$) o $2\ 3^{(n-2)/2}$ (para$n$, incluso). El límite se obtiene por $n=9$ y rara vez va más por debajo de la mitad de eso. Los condes $M_n$ para $n=18,19,20$ se $21345, 22005, 64917$, por lo que los ratios de 1.0309 y, a continuación, 2.95. En general prime $n$ resulta en un aumento relativamente pequeño aunque $n=19$ es mucho más espectacular de lo $23$ o $29.$ En el caso de $n=19$ sólo tenemos acerca de $30\%$ del límite superior.

Las cuentas son siempre impar (incluyendo $1$ para $n=0$) con la excepción de $M_1=2$. Esto es debido a que (como se observa) los posible valores vienen en pares $m,2^n-m$, salvo que el valor alcanzable $2^{n-1}$ es impar. ($n=0,1$ son especiales)

Los valores de mod $3$ son

$2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 2, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1$

Supongo que el elevado número de múltiplos de $3$ puede ser explicado por la observación de que si se puede llegar a una suma de $m$ sin hacer uso de $\binom{n}{1}$ o $\binom{n}{n-1}$, entonces también podemos obtener el $m+1$ e $m+2$. A menudo, los valores de $m$ del primer tipo se extiende lo suficiente como que los distintos valores son superiores a $2$ de diferencia (por ejemplo, cuando se $n \gt 2$ es el primer y todas estas sumas son múltiplos de $n$). Una excepción es $n=10.$ No tenemos $250=\binom{10}{1}+\binom{10}{3}+\binom{10}{7}$ e $252=\binom{10}{5}$ entre otros.