Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

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}$$

share|improve this answer
    
Very nice. Surprised me, as it didn't agree with my numerical experiment, but I found a mistake in my computation. –  Gerry Myerson Feb 19 '12 at 12:01
    
@Kevin C.Thank you very much. It is very interesting and knowledgeable proof. But I realized that in your proof the order is important. I am interested in the question when the order is not important, i.e. 1+3+5 is the same as 3+1+5 or 5+1+3.... Sorry, I did not mentioned it before-its not my field and for me it is hard to realize what else can be important in the question. Would the same proof work in the case when order is not important. –  Michael Feb 20 '12 at 20:11
    
Michael, the proof is heavily dependent on the order mattering. But if the order doesn't matter, what does it mean for the sum of the first $M/2$ to be odd? –  Kevin Costello Feb 20 '12 at 21:26
    
Sorry. It should be sum of any r of $m_i$, $m_i\in\{0,1,...,2m\}$ is odd. –  Michael Feb 20 '12 at 22:56
    
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. –  Gerry Myerson Feb 21 '12 at 0:54
add comment

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.

share|improve this answer
    
Thank you. But how the answer depend on $2m$? –  Michael Feb 18 '12 at 21:10
    
Ah, perhaps I have misinterpreted the problem. I was assuming that $m_1,\dots,m_M$ were given, but perhaps it is only $m$ that is given, and you want an answer involving all possibilities for $m_1,\dots,m_M$. So now I think you need two things: given $m$ (and $r$?), how many ways to write $2m$ as a sum of $2r$ non-negative integers, and in how many of those is the sum of the first $r$ integers odd. I think it can be done with generating functions. Let me know if I have the right interpretation, and I'll try to work on it. –  Gerry Myerson Feb 19 '12 at 0:42
    
Yes. Your interpretation is correct now. Only $m$ and $r$ are given. Sorry, I should of mentioned it before. Thank you. –  Michael Feb 19 '12 at 0:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.