4
$\begingroup$

I am having trouble with some combinatorial question. Its not my field and the question is difficult for me. Any help will be appreciate.

Let $m_1,..., m_{{M}}$ be numbers such that $m_i \in \{0, 1, ..., 2m\}$ and $\sum_{i=1}^Mm_i=2m$.

Which possibilities and how many possibilities for the sum of half of $m_i$, i.e. for the sum $m_1+...+ m_{\frac{M}{2}}$ to be odd?

Thank you.

I have started with possibility that one of the $m_i, i=1,..., \frac{M}{2}$, say $m_1=2k-1$, for $k=1,..., m$ and the rest $m_2=...=m_{M/2}=0$. So, I can have $m$ such possibilities.

Now I am considering possibilities that, say, $m_3=...=m_{M/2}=0$ and $m_1=1$, $m_2=2k$, for $k=1,...,m-1$. Such possibilities is $m-1$.... and so on up to $m_1=2m$, I guess.

With three non-zero terms, I am stuck.... Plus, I have assumption that $\sum_{i=1}^Mm_i=2m$. And in my question I should consider sum of the half of $m_i$. I am confused.

2 Answers 2

1

Here's one way to obtain a closed form for the second interpretation of Gerry Myerson.

If it weren't for the pesky "first $r$ sum to odd" condition, we'd have a classic problem that could be solved by the Stars and Bars method. The number of solutions is just $\binom{2m+2r-1}{2m}$. If we let $O$ denote the number of solutions where the sum of the first $r$ is odd, and $E$ denote solutions where the sum of the first $r$ is even, this gives us $O+E$. So now we just need to find $E-O$. To do so, we'll divide the sequences summing to $2m$ into classes and sum over each class separately.

For $k=1,2\dots,r$, let $y_k=m_k+m_{2r+1-k}$. We consider the class corresponding to $y$ to be all permutations with that sum of pairs. For each class we can write $(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}.$ The trick I used here was that I can think of $E-O$ as meaning that even sums contribute $1$ and odd sums contribute $(-1)$ to the class, which is the behavior of $(-1)^{sum}$. This sum factors! We can write it as $\prod_{i=1}^r \sum_{m_i+m_{2r+1-i}=y_i} (-1)^{m_i}.$ The sum inside the product is now easy to compute (the solutions are just $(0,y_i),(1,y_{i}-1),\dots,(y_i,0)$), and is $0$ if $y_i$ is odd, $1$ is $y_i$ is even. Multiplying over all $y_i$, we see that the contribution of a class is $0$ unless all the $y_i$ are even, in which case it is $1$.

Therefore $E-O$ is just the number of solutions to $y_1+\dots+y_r=2m$ with all the $y_r$ even, which (letting $z_i=y_i/2$) is just the number of solutions to $z_1+\dots+z_r=m$, which is (stars and bars again) $\binom{m+r-1}{m}$. Combining this with $E+O$, we see $O=\frac{\binom{2m+2r-1}{2m}-\binom{m+r-1}{m}}{2}$

  • 0
    I think it's time, Michael, for you to sit down, take a deep breath, figure out what exactly it is that you want to know, and then edit your question to reflect that clearly and unambiguously, with examples to illustrate the concepts.2012-02-21
3

EDIT: See after the break for what may be the interpretation that was intended.

I'll assume $M=2r$ is even (otherwise I don't know what you mean by $M/2$).

So, you're adding $r$ numbers, and you want the sum to be odd. This will happen if, and only if, the number of odd numbers in your sum is odd.

So, suppose $k$ of your numbers are odd, and the other $2r-k$ are even.

Then you could choose $1$ odd number and $r-1$ even numbers, in ${k\choose1}{2r-k\choose r-1}$ ways.

You could choose $3$ odd numbers and $r-3$ even, in ${k\choose3}{2r-k\choose r-3}$ ways.

And so on. Then add up all the different ways of choosing that you will have worked out, and there's your answer (assuming I have found the correct interpretation for your question).


It appears that the problem is, given $m$ and $M=2r$, find the number of ways of choosing $m_1,\dots,m_{2r}$ such that $\sum_1^rm_i$ is odd and $\sum_1^{2r}m_i=2m$.

First let's note the standard formula: the number of solutions in non-negative integers to $a_1+\cdots+a_s=n$ is $n+s-1\choose s-1$.

Now we want, for each odd $q$, the number of ways to get $r$ numbers to sum to $q$, and the other $r$ numbers to sum to $2m-q$. So the answer is $\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$) makes me suspect there is no simple closed form.

  • 0
    Yes. Your interpretation is correct now. Only $m$ and $r$ are given. Sorry, I should of mentioned it before. Thank you.2012-02-19