0
$\begingroup$

As a part of a bigger problem I have to determine In how many ways $37$ different objects can be divided among two groups of $32$ and $5$ objects each if

i) object $A$ and $B$ cannot belong to the same group

ii) object $A$ and $B$ must belong to the same group.

My skills in combinatorics are obviously not what they have been since as I remember from that course, this is a typical standard problem, but i can't manage to make any conclusions. My idea is just to determine all combinations to divide the $37$ objects into groups of $32$ and $5$ each and then subtract the cases of restriction i) and ii) separately.

I guess that is one way to solve the problem?

Then for i), we first notice that we can divide our $37$ objects into groups of $32$ and $5$ each in ${37 \choose 32}$ ways. But how many of theese consist both object $A$ and $B$? If we were just dealing with one group I guess we'd only have to first place A and B in the group and then count the number of combinations to place the other objects in that group? Can we do something alike in this case?

$\endgroup$
1
$\begingroup$

Objects A and B cannot belong to the same group:

There are $\dbinom{35}{31}=52360$ ways to:

  • Put A in the first group and B in the second group
  • Choose $31$ out of $35$ objects for the first group
  • Put the remaining objects in the second group

There are $\dbinom{35}{31}=52360$ ways to:

  • Put B in the first group and A in the second group
  • Choose $31$ out of $35$ objects for the first group
  • Put the remaining objects in the second group

So there are $52360+52360=104720$ ways to do that.


Objects A and B must belong to the same group:

There are $\dbinom{35}{30}=324632$ ways to:

  • Put A in the first group and B in the first group
  • Choose $30$ out of $35$ objects for the first group
  • Put the remaining objects in the second group

There are $\dbinom{35}{3}=6545$ ways to:

  • Put A in the second group and B in the second group
  • Choose $3$ out of $35$ objects for the second group
  • Put the remaining objects in the first group

So there are $324632+6545=331177$ ways to do that.

$\endgroup$
0
$\begingroup$

Item (i)

Your solution is in (one of) the right direction(s).

A direct solution would be:

  • Choose if $A$ will be in the largest or the smallest group

After this, $B$ will have to be in the other group, and we have 35 elements left to organize.

  • Choose the other 31 elements of the largest group among the remaining 35

EDIT:

Item(ii)

A direct solution could consist of two cases.

-$A$ and $B$ in the small group

You have to choose other 3 elements to complete the small group.

-$A$ and $B$ in the large group

You have to choose other 5 elements to complete the small group.

$\endgroup$
  • $\begingroup$ I edited my question (restriction ii). $\endgroup$ – alot Oct 17 '14 at 21:28
0
$\begingroup$

In each case there are $2$ ways to choose groups for $A,B$ satisfying the restriction. In case (i) they are both equivalent for when is left, and the remaining choices give $\binom{25}4$ possibilities, for $2\times\binom{25}4$ in all. In case (ii) the remaining choices are different and must be computed separately and added, for $\binom{35}5+\binom{35}3$ possibilities.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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