Suma de 'la primera k' coeficientes binomiales para fijo n

Question

Estoy interesado en la función $\sum_{i=0}^{k} {N \elegir i}$ para fijo $N$ y $0 \leq k \leq$ N. Obviamente es igual a 1 por $k = 0$ y $2^{N}$ para $k =$ N, pero hay otros notables propiedades? Cualquier referencia bibliográfica?

En particular, tiene una forma cerrada o notables algoritmo para el cálculo de forma eficiente?

En caso de que usted es curioso, esta función aparece en la teoría de la información como el número de bits de cadenas de longitud $N$ con Hamming de peso inferior o igual a $k$.

Edit: me he encontrado con un útil límite superior: $(N+1)^{\underline{k}}$ donde el subrayado de $k$ denota la caída de factorial. Combinatoria, esto significa listado de los bits de $N$ que se establecen (en un orden arbitrario) y realizando un seguimiento de un 'hecho' símbolo al final. Mejor de los límites?

Answer 1

Voy a dar dos familias de límites, uno para cuando $k = N/2 + \alpha \sqrt{N}$ y uno para cuando $k$ es fijo.

La secuencia de coeficientes binomiales ${N \elegir 0}, {N \elegir 1}, \ldots, {N \elegir N}$ es simétrica. Así que usted tiene

$\sum_{i=0}^{(N-1)/2} {N \elegir i} = {2^N \over 2} = 2^{N-1}$

cuando $N$ es impar. (Cuando $N$ es incluso algo similar es verdad pero tienes que corregir si se incluye el término ${N \elegir N/2}$ o no.

También, que $f(N,k) = \sum_{i=0}^k {N \elegir i}$. Entonces vas a tener, para la constante real $\alpha$,

$\lim_{N \to \infty} {f(N,\lfloor N/2+\alpha \sqrt{N} \rfloor) \más de 2^N} = g(\alpha)$

para algunos la función $g$. Esta es, esencialmente, una reescritura de un caso especial del teorema del límite central. El peso de Hamming de una palabra elegida uniformemente al azar es una suma de Bernoulli(1/2) de las variables aleatorias.

Fijo $k$ y $N \to \infty$, tenga en cuenta que $${{n \elegir k} + {n \elegir k-1} + {n \elegir k-2} \over {n \elegir k}} = {1 + {k \sobre n-k+1} + {k(k-1) \(n-k+1)(n-k+2)} + \cdots}$$ y podemos obligado el lado derecho de arriba por la serie geométrica $${1 + {k \sobre n-k+1} + \left( {k \sobre n-k+1} \right)^2 + \cdots}$$ lo que equivale a ${n-(k-1) \más de n - (2k-1)}$. Por lo tanto, tenemos $$f(n,k) \le {n \elegir k} {n-(k-1) \más de n-(2k-1)}.$$

Answer 2

Jean Gallier da esta enlazado (Proposición 4.16 en Ch.4 de "Matemáticas Discretas" preprint)

$$f(n,k) < 2^{n-1} \frac{{n \elegir k+1}}{n \elegir n/2}$$

donde $f(N,k)=\sum_{i=0}^k {N\elegir i}$ y $k\le n/2-1$ incluso $n$

Parece ser peor que la de Michael obligado excepto para valores grandes de k

Aquí está una parcela de f(50,k) (círculos azules), Michael Lugo atado (diamantes marrones) y Gallier (magenta plazas)

n = 50;
bisum[k_] := Total[Table[Binomial[n, x], {x, 0, k}]];
bibound[k_] := Binomial (n, k + 1]/Binomial[n, n/2] 2^(n - 1);
lugobound[k_] := Binomial[n, k] (n - (k - 1))/(n - (2 k - 1));
ListPlot[Transpose[{bisum[#], bibound[#], lugobound[#]} & /@ 
 Intervalo[0, n/2 - 1]], PlotRange -> Todos, PlotMarkers -> Automático]

Editar La prueba, la Proposición 3.8.2 de Lovasz "la Matemática Discreta".

Lovasz da otro obligado (Teorema 5.3.2) en términos de exponenciales que parece bastante cerca de la anterior

$$f(n,k)\le 2^{n-1} \exp (\frac{(n-2k-2)^2}{4(1+k-n)}$$ Lovasz obligado es el de arriba.

n = 50;
gallier[k_] := Binomial (n, k + 1]/Binomial[n, n/2] 2^(n - 1);
lovasz[k_] := 2^(n - 1) Exp[(n - 2 k - 2)^2/(4 (1 + k - n))];
ListPlot[Transpose[{gallier[#], lovasz[#]} & /@ Intervalo[0, n/2 - 1]], 
 PlotRange -> Todos, PlotMarkers -> Automático]

Answer 3

Un estándar de la estimación cuando la suma incluye alrededor de la mitad de los términos es el Chernoff obligado, una forma de que da

$$\sum_{k=0}^{(N-a)/2} {N\elegir k} \le 2^N \exp\bigg(\frac{-a^2}{2N}\bigg)$$

Esto no es tan agudo. Es más débil que la serie geométrica obligado Michael Lugo dio. Sin embargo, la forma más simple puede ser útil.

Answer 4

No es útil de forma cerrada para esto. Usted puede escribir como $$2^N - \binom{N}{k+1} {}_2F_{1}(1, k+1-N, k+2; -1)$$ pero que es realmente sólo una reescritura de la suma en una forma diferente.

Answer 5

Ver A008949 "Triángulo de las sumas parciales de los coeficientes binomiales."

$T(n,k) = \sum_{i-0}^k {N\elegir i}$ es el número máximo de las regiones en los cuales $n$ hyperplanes de co-dimensión $1$ divide a $\mathbb R^k$ (el Pastel-Sin-Glas números)

$2 ~T(n-1,k-1)$ es el número de orthants intersección de un genérico lineal subespacio de $\mathbb R^n$ de dimensión $k$. Esto indica la probabilidad de si usted elige $$ independientes de puntos al azar en la unidad de la esfera en $\mathbb R^d$, la probabilidad de que el origen está contenida en el convex hull es de $T(a-1,a-d-1)/2^{- 1}$. De manera complementaria, sin hemisferio contiene todos los puntos. El espacio nulo de la mapa mediante combinaciones lineales de los puntos de $\mathbb R^a \to \mathbb R^d$ genéricamente tiene un núcleo de dimensión $-d$, y este se cruza con el positivo orthant iff $0$ es un casco convexo de los puntos. Por simetría, todos orthants son igualmente probables.