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.

I've asked related question before, combinatorial question (sum of numbers) but it turned out that I formulated it wrong. But it was interesting problem any way. Thank you very much for the help!

My real question is: Given numbers $r$ and $m$. Let $m_1,..., m_{{2r}}$ be numbers such that $m_i \in \{0, 1, ..., 2m\}$ and $\sum_{i=1}^{2r}m_i=2m$.

Find number of ways choosing $m_1,...,m_{2r}$, such that sum of any $r$ of them will be odd.

I was trying to calculate number of repetitions (order is not important) and then just subtract it from the result in the question 'combinatorial question (sum of numbers)'. But it seems I have to use different procedure.

Thank you.

share|improve this question
1  
The condition, "the sum of any $r$ of them will be odd," is equivalent to "$r$ is odd, and $m_1,\dots,m_{2r}$ are all odd". –  Gerry Myerson Feb 24 '12 at 23:10

1 Answer 1

up vote 3 down vote accepted

I think it is clear that each $m_i$ will have to be odd and so $r$ will also have to be odd. So you want the number of compositions of $2m$ into $2r$ odd numbers.

Consider adding $1$ to each of them: you now want the number of compositions of $2m+2r$ into $2r$ positive even numbers.

This is the same as the number of compositions of $m+r$ into $2r$ positive integers. This is ${m+r-1 \choose 2r-1}$. You need $m \ge r$ to have any possibilities.

But if order does not matter, you want the number of partitions of $m+r$ into $2r$ positive integers. There is not a simple formula though you can use generating functions or something like my Java applet.

share|improve this answer
    
Thank you very much. I am not familiar with generating functions. Where I can find enough information about these functions to solve my problem? –  Michael Feb 27 '12 at 21:02
    
A good way of learning about generating functions would be to read Herbert S. Wilf's generatingfunctionology. In this particular case, I think you want the coefficient of $x^m$ in the expansion of $$\frac{x^r}{\prod_{j=1}^{2r} \left(1-x^j\right)}.$$ Also look at OEIS A008284 –  Henry Feb 27 '12 at 23:12
    
Thank you very much. –  Michael Feb 28 '12 at 19:43

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.