In how many ways can I select 4 groups from 10 indistinguishable items where each selected group only contains either 0 or an odd number of items

Question

If this question asked instead to select groups of even number of items, then I know how to approach it.

The even approach is: there is a bijection to a sequence of 8 bits (10/2+4-1), where each 0 correspond to $two$ items and 1's are partition lines between groups. For example, 01100001 would be groups of 2, 0, 8, and 0 items. The number of ways to select these $even$ groups is ${8 \choose 3}$ because there are 8 bits, and 3 partitions.

But I'm confused what to do about the odd case. It's not correct to now assume that each 0 correspond to an $odd$ number of item, because then a multiple of 0's could be $even$ or $odd$.

How should this problem be approached?

Answer 1

Since you can select any number of items from the set $\{0,1,3,5,7,9\}$. So use generating functions as follows: $$\text{find coefficient of $x^{10}$ in }\quad (x^0+x^1+x^3+x^5+x^7+x^9)^4$$ Think of the approach in the following manner: each group's selection is given by the polynomial $(x^0+x^1+x^3+x^5+x^7+x^9)$. So when you multiply this for each group, a general term will be something like $$x^{a+b+c+d}, \quad \text{where } \quad a,b,c,d \in \{0,1,3,5,7,9\}$$ We want the coefficient of $x^{10}$ because that would amount to $a+b+c+d=10$ with $a,b,c,d$ chosen from appropriate values.

Answer 2

First: Give one item to each group. So every group has one item, and we have last 6 items. Then by using your even approach, use three $0$ (every zero means two items) and three $1$, get ${6 \choose 3}$. ( for example: in 010110 situation we distribute 2+1 items to 1st group, 2+1 items to 2nd group, 0+1 item the third one, and 2+1 items the last one. Obviously every group has odd many items)

What we do in the above is not enough since we do not calculate one of the groups has zero item stuation. So we will continue.

Second: Now we consider to give zero item to one group. So we take care the last three groups. Again we give one item each of one of the three groups. Then we have 7 items. So we can not distribute the items by using $0$ approach. It means the situation is impossible.

Third: We will give zero item to two groups. Then we give one item each of one of the last two groups. So we have 8 items (it means four $0$) and 2 grous (it means one bar 1). Then we have ${5 \choose 4}$

Fourth: We will give zero item to three groups. Then the situation is impossible.

Fifth:We will give zero item to four groups. Then the situation is also impossible.

Aftermath we have 25 ways.

Answer 3

I would follow an approach different from the binary representation.

Seems from your description to understand that the groups are distinguished (labelled).

Now, suppose none of the groups is empty, then you are looking for the solutions to $$ \left( {2a + 1} \right) + \left( {2b + 1} \right) + \left( {2c + 1} \right) + \left( {2d + 1} \right) = 10 $$ that is $$ a + b + c + d = 3 $$ where $0 \le a,b,c,d$.
This is the number of weak compositions of $3$ into $4$ parts which is equal to $\binom{3+4-1}{4-1}=\binom{6}{3}$.

Then assume one of the group is empty: you have four choices for that. For the non empty groups $$ \eqalign{ & \left( {2a + 1} \right) + \left( {2b + 1} \right) + \left( {2c + 1} \right) = 10\quad \Rightarrow \cr & \Rightarrow \quad a + b + c = 7/2 \cr} $$ so no solution.

You can choose $2$ empty groups in $\binom{4}{2}$ ways, and then $$ \eqalign{ & \left( {2a + 1} \right) + \left( {2b + 1} \right) = 10\quad \Rightarrow \cr & \Rightarrow \quad a + b = 4 \cr} $$ which gives $5$ solutions

Of course, no solution again with three empty groups.

Summing up $$ N = \left( \matrix{ 4 \cr 0 \cr} \right)\left( \matrix{ 6 \cr 3 \cr} \right) + \left( \matrix{ 4 \cr 2 \cr} \right)\left( \matrix{ 5 \cr 1 \cr} \right) = 50 $$ and the path to extend it to a general case is clear.