combinatoria pregunta (la suma de los números)

Question

Estoy teniendo problemas con algunos combinatoria pregunta. No es mi campo y la pregunta es difícil para mí. Cualquier ayuda se aprecia.

Deje $m_1,..., m_{{M}}$ ser números de tal manera que $m_i \in \{0, 1, ..., 2m\}$$\sum_{i=1}^Mm_i=2m$.

Que posibilidades y de cómo muchas posibilidades para la suma de la mitad de $m_i$, es decir, por la suma de $m_1+...+ m_{\frac{M}{2}}$ a un ser extraño?

Gracias.

He empezado con la posibilidad de que uno de los $m_i, i=1,..., \frac{M}{2}$, decir $m_1=2k-1$ $k=1,..., m$ y el resto a $m_2=...=m_{M/2}=0$. Así, puedo tener $m$ tales posibilidades.

Ahora estoy pensando en las posibilidades que, dicen, $m_3=...=m_{M/2}=0$ y $m_1=1$, $m_2=2k$, para $k=1,...,m-1$. Tales posibilidades es $m-1$.... y así sucesivamente hasta el $m_1=2m$, supongo.

Con tres cero términos, estoy atascado.... Además, he supuesto de que $\sum_{i=1}^Mm_i=2m$. Y en mi pregunta que debo considerar la suma de la mitad de $m_i$. Estoy confundido.

Answer 1

EDIT: a Ver, después de la ruptura de lo que puede ser la interpretación que se pretendía.

Asumiré $M=2r$ es incluso (de lo contrario no sé a qué te refieres por $M/2$).

Así que, estás añadiendo $r$ números, y desea que la suma sea impar. Esto ocurre si, y sólo si, el número de los números impares en su suma es impar.

Así, supongamos $k$ de sus números son impares, y el otro $2r-k$ son incluso.

Entonces usted puede elegir $1$ número impar y $r-1$ números, en ${k\choose1}{2r-k\choose r-1}$ maneras.

Usted puede elegir el $3$ números impares y $r-3$, incluso, en ${k\choose3}{2r-k\choose r-3}$ maneras.

Y así sucesivamente. Luego se suman todas las diferentes formas de la elección de que se han trabajado, y ahí está su respuesta (suponiendo que he encontrado la correcta interpretación de su pregunta).

---

Parece que el problema es que, dado $m$$M=2r$, hallar el número de maneras de elegir a $m_1,\dots,m_{2r}$ tal que $\sum_1^rm_i$ es impar y $\sum_1^{2r}m_i=2m$.

Primero vamos a la nota de la fórmula estándar: el número de soluciones en los enteros no negativos a$a_1+\cdots+a_s=n$$n+s-1\choose s-1$.

Ahora queremos, para cada uno de los impares $q$, el número de maneras de conseguir $r$ números de la suma de a $q$, y el otro $r$ números de la suma de a $2m-q$. Así que la respuesta es $$\sum_{q\rm\ odd}{q+r-1\choose r-1}{2m-q+r-1\choose r-1}$$ I don't know whether there is a closed form for this sum. A numerical experiment I tried ($m=5$, $r=2$) me hace sospechar que no es sencilla la forma cerrada.

Answer 2

Aquí es una manera de obtener una forma cerrada para la segunda interpretación de Gerry Myerson.

Si no fuera por los molestos "primero $r$ suma impar" condición, tendríamos un clásico problema que podría ser resuelto por las Estrellas y las Barras de método. El número de soluciones es sólo $\binom{2m+2r-1}{2m}$. Si dejamos $O$ denotar el número de soluciones donde la suma de los primeros a $r$ es impar, y $E$ denotar soluciones donde la suma de los primeros a $r$ es incluso, esto nos da la $O+E$. Así que ahora sólo tenemos que encontrar a $E-O$. Para ello, vamos a dividir las secuencias de sumar a $2m$ en clases y que suma más de cada clase por separado.

Para $k=1,2\dots,r$, vamos a $y_k=m_k+m_{2r+1-k}$. Consideramos que la clase correspondiente a $y$ a todas las permutaciones con que la suma de los pares. Para cada clase se puede escribir $$(E-O)_{class} =\sum_{class} (-1)^{m_1+\dots+m_r}=\sum_{m_1+m_{2r}=y_1} \dots \sum_{m_{r}+m_{r+1}=y_r} (-1)^{m_1+\dots+m_r}.$$ El truco que he utilizado era el que puedo pensar de $E-O$ lo que significa que incluso las sumas contribuir $1$ e impar sumas contribuir $(-1)$ a la clase, que es el comportamiento de $(-1)^{sum}$. Esta suma de factores! Se puede escribir como $$\prod_{i=1}^r \sum_{m_i+m_{2r+1-i}=y_i} (-1)^{m_i}.$$ La suma en el interior del producto ahora es fácil de calcular (las soluciones son sólo $(0,y_i),(1,y_{i}-1),\dots,(y_i,0)$) $0$ si $y_i$ es impar, $1$ $y_i$ es incluso. Multiplicando sobre todas las $y_i$, vemos que la contribución de una clase es $0$ menos que en todas las $y_i$ son incluso, en cuyo caso es $1$.

Por lo tanto, $E-O$ es el número de soluciones a $y_1+\dots+y_r=2m$ todos los $y_r$, incluso, que (dejando $z_i=y_i/2$) es el número de soluciones a $z_1+\dots+z_r=m$, que es (las estrellas y las barras de nuevo) $\binom{m+r-1}{m}$. La combinación de este con $E+O$, vemos $$O=\frac{\binom{2m+2r-1}{2m}-\binom{m+r-1}{m}}{2}$$