2
$\begingroup$

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.

  • 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".2012-02-24

1 Answers 1

3

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.

  • 0
    A good way of learning about [generating functions](http://en.wikipedia.org/wiki/Generating_function) would be to read Herbert S. Wilf's [generatingfunctionology](http://www.math.upenn.edu/~wilf/DownldGF.html). 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](http://oeis.org/A008284)2012-02-27