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
    Very nice. Surprised me, as it didn't agree with my numerical experiment, but I found a mistake in my computation.2012-02-19
  • 0
    @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.2012-02-20
  • 0
    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?2012-02-20
  • 0
    Sorry. It should be sum of any r of $m_i$, $m_i\in\{0,1,...,2m\}$ is odd.2012-02-20
  • 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
    Thank you. But how the answer depend on $2m$?2012-02-18
  • 0
    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.2012-02-19
  • 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