Reorganización de sumas alternas de productos de coeficientes binomiales

Question

Reorganización de sumas alternas de productos de coeficientes binomiales

suma
Matemáticas
combinatoria
particiones enteras
exclusión inclusión
coeficientes binomiales

Christopher Dearlove

la suma

\sum_{k = 0}^{⌊ \frac{pag}{s} ⌋} (- 1)^{k} (\binom{norte}{k}) (\binom{pag - k s + norte - 1}{norte - 1}); norte > 0, s > 0 y 0 \leq pag \leq norte s,

$\sum_{k=0}^{\lfloor\frac{p}{s}\rfloor}(-1)^k {n\choose k}{p-ks+n-1\choose n-1}\quad;n > 0, s > 0 \text{ and } 0\le p\le ns,$ con

(\binom{n}{k})

${n\choose k}$ que denota el coeficiente binomial, tiene la limitación de que implementado números enteros de tamaño fijo, hay casos en los que los términos individuales superan el tamaño del número entero aunque el resultado no lo haga. (Incluso suponiendo un cálculo ideal de coeficientes binomiales). ¿Hay alguna forma de reorganizar esa suma para evitar eso? Se puede suponer que el límite de tamaño entero es

s^{n}

$s^n$ , la suma de ese resultado para todos

p

$p$ . Un resultado más fuerte sería que todos los términos sumados no excedan su suma en valor absoluto. Un resultado aún más sólido sería que todos los términos sumados no fueran negativos. Pero incluso el caso más débil está bien.

jose carlos santos

Bienvenido a MSE. Para obtener información básica sobre cómo escribir matemáticas en este sitio, consulte, por ejemplo , la ayuda básica sobre la notación mathjax , el tutorial y la referencia rápida de mathjax , el tutorial de matemáticas del metasitio principal y la edición de ecuaciones .

Rob Pratt

Las sumas alternas como esta a menudo se pueden interpretar como una fórmula de inclusión-exclusión y se pueden simplificar a una expresión más simple de coeficientes binomiales. Vea esta respuesta reciente para una suma alterna que se parece mucho a la suya.

Respuestas (3)

Reorganización de sumas alternas de productos de coeficientes binomiales

Bienvenido a MSE. Para obtener información básica sobre cómo escribir matemáticas en este sitio, consulte, por ejemplo , la ayuda básica sobre la notación mathjax , el tutorial y la referencia rápida de mathjax , el tutorial de matemáticas del metasitio principal y la edición de ecuaciones .
Las sumas alternas como esta a menudo se pueden interpretar como una fórmula de inclusión-exclusión y se pueden simplificar a una expresión más simple de coeficientes binomiales. Vea esta respuesta reciente para una suma alterna que se parece mucho a la suya.

Mike Earnest · Answer 1

No puedo responder a su pregunta exactamente, pero asumiendo que está tratando de calcular esta suma mientras evita el desbordamiento de enteros, aquí hay un truco que podría funcionar. Dejar $a_k$ ser el valor absoluto de la $k^{th}$ sumando en su suma. Puedes probar que los números $a_k$ aumentar hasta un punto, y luego disminuir después. Esto implica que su suma alterna está limitada arriba por el mayor $a_k$ . Alquiler $m=\max_k a_k$ , puedes calcular $m$ por adelantado, y luego calcula la suma con todas las sumas realizadas módulo $m$ . Esto asegura que nunca tenga cálculos parciales más grandes que $m$ , sin dejar de dar la respuesta correcta.

Esa es una idea muy útil. Puedo mejorarlo en mi caso particular sabiendo que la suma de todas esas sumas (que son todas positivas) es $s^n$ , y $s^n$ no se desborda en mi aplicación, por lo que podría calcular cada término módulo $s^n$ . Lo cual no es trivial en el marco que tengo, pero vale la pena seguirlo.

Rob Pratt · Answer 2

Si el índice de suma $k$ subió a $n$ en lugar de $p/s \le n$ , sería la fórmula de inclusión-exclusión para el número de $(n-1)$ -subconjuntos de $\{1,\dots,p+n-1\}$ que contienen al menos un elemento de cada uno de los siguientes $n$ intervalos disjuntos:

{1, \dots, s} {s + 1, \dots, 2 s} ⋮ {(norte - 1) s + 1, \dots, norte s}

$\{1,\dots,s\} \\ \{s+1,\dots,2s\} \\ \vdots \\ \{(n-1)s+1,\dots,ns\}$ El número de tales subconjuntos es claramente

0

$0$ porque

n > n - 1

$n > n-1$ . Como en la respuesta vinculada, puede generalizar reemplazando el

n - 1

$n-1$ con cualquier número menor que

n

$n$ y seguir obteniendo lo mismo

0

$0$ resultado.

Entonces tu suma es

\sum_{k = 0}^{⌊ pag / s ⌋} (- 1)^{k} (\binom{norte}{k}) (\binom{pag - k s + norte - 1}{norte - 1}) = - \sum_{k = ⌊ pag / s ⌋ + 1}^{norte} (- 1)^{k} (\binom{norte}{k}) (\binom{pag - k s + norte - 1}{norte - 1})

$\sum_{k=0}^{\lfloor p/s \rfloor}(-1)^k \binom{n}{k}\binom{p-ks+n-1}{n-1} = -\sum_{k=\lfloor p/s \rfloor+1}^n(-1)^k \binom{n}{k}\binom{p-ks+n-1}{n-1}$

Ese resultado no es 0. En realidad, es el número de formas en que la suma de n dados de s lados, cada uno numerado de 0 a s-1, es p.
OK, estaba resumiendo $k=n$ , pero su suma se trunca en $p/s \le n$ .

Misha Lavrov · Answer 3

Si sabe que la respuesta final se ajusta al tamaño entero fijo, entonces no tiene que preocuparse por el desbordamiento intermedio. Cálculo con, digamos, $64$ -bit enteros es equivalente al módulo de cálculo $2^{64}$ . Entonces, incluso si las respuestas intermedias se desbordan y le dan algo que solo es el módulo correcto $2^{64}$ todavía garantiza que la respuesta final es correcta módulo $2^{64}$ , que será realmente correcto.

Así por ejemplo en $8$ -bit aritmética entera que puedo calcular

100 + 200 - 50 - 150

$100 + 200 - 50 - 150$ y obten

100

$100$ , a pesar de que las sumas parciales no encajan en

8

$8$ bits:

con sin firmar $8$ -bit enteros, $100+200$ vendría a $44$ , restando $50$ rendiría $250$ , y restando $150$ rendiría $100$ .
con firmado $8$ enteros de -bit, los términos individuales ni siquiera cabrían, y estaríamos calculando $100 + (-56) - 50 - (-106)$ . Las sumas parciales serían $100 + (-56) = 44$ , $44-50 = -6$ , y $-6 - (-106) = 100$ .

Desafortunadamente, por razones que van más allá de las matemáticas puras, no es tan simple como eso poder confiar en el ajuste desbordante correctamente en el entorno que estoy usando. Pero el módulo es el camino a seguir, como lo he implementado en base a otra respuesta. Pero luego resulta que necesitas calcular el módulo de coeficientes binomiales lo que sea que uses (usé $s^n$ ) y eso no se puede hacer simplemente desbordando. Usé una sugerencia de otro lugar para usar una versión en caché de la relación de recurrencia aditiva para eso, nuevamente módulo $s^n$ .
Es cierto que no es fácil calcular un coeficiente binomial que se ajuste a un número entero de 64 bits cuando los pasos intermedios para encontrarlo no se ajustan. si al menos $k! \binom nk$ Si todavía fuera lo suficientemente pequeño, sería fácil, pero más allá de eso, es posible que deba hacer algo más complicado.

Reorganización de sumas alternas de productos de coeficientes binomiales

Christopher Dearlove

jose carlos santos

Rob Pratt

Respuestas (3)

Mike Earnest

Christopher Dearlove

Rob Pratt

Christopher Dearlove

Rob Pratt

Misha Lavrov

Christopher Dearlove

Misha Lavrov

Simplificando el producto de múltiples expansiones binomiales

Prueba combinatoria de la identidad 3n=∑nk=0(nk)2k3n=∑k=0n(nk)2k3^n=\sum_{k=0}^n \binom nk 2^k

Dos relaciones en serie, cada una implica a la otra - del libro de particiones de Andrews

Pregunta de prueba de suma binomial/combinatoria

Suma del producto de coeficientes binomiales: ∑nk=0(−1)k(nk)(n+kk)=(−1)n∑k=0n(−1)k(nk)(n+kk)=(− 1)n\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k} = (-1)^n

Formulación de una suma alterna de combinaciones de productos

Prueba combinatoria de ∑i=0m2n−i(ni)(mi)=∑i=0m(n+m−im)(ni)∑i=0m2n−i(ni)(mi)=∑i=0m(n+ m−im)(ni) \sum \limits_{i = 0} ^{m} 2^{ni} {n \choose i}{m \choose i} = \sum\limits_{i=0}^m { n + m - yo \elegir m} {n \elegir i}

Contando las formas en la cuadrícula si uno puede moverse de (x,y)(x,y)(x,y) a (x+a,x+b)(x+a,x+b)(x+a, x +b) para x,y,a,b≥0x,y,a,b≥0x,y,a,b\geq 0 arbitrario.

Prueba combinatoria para la identidad ∑nk=0(nk)(−2)k=(−1)n∑k=0n(nk)(−2)k=(−1)n\sum_{k=0}^n \binom{n}{k}\left(-2\right)^k = (-1)^n

Suma parcial de coeficientes binomiales n elige k multiplicado por k para k de n/2+1 a n