# Minimum number of combinations

I have a group of 10 players and I want to form two groups with them.Each group must have atleast one member.In how many ways can I do it?

-
Do you need to assign all 10 players to one of the two groups, or is e.g. 2 in group 1 and 2 in group 2 (6 unassigned) valid group sizes? –  Tim S. Apr 11 '14 at 18:29
There wont be any unpicked players.The only condition is a team should have atleast one member(the other obviously having the remaining 9 players) –  Renjith Apr 12 '14 at 5:51

We solve first a different problem. We want to divide our people into two teams, one to wear blue uniforms, the other to wear red. Our set has $2^{10}$ subsets. Throw away the empty set and the full set. That leaves $2^{10}-2$ ways to choose the team that will wear blue uniforms.

However, there are no coloured uniforms in our actual problem. So the number of ways to divide our $10$ people into two non-empty groups is $\frac{2^{10}-2}{2}$.

Remark: One could, less plausibly, interpret the problem as meaning that some people may remain unpicked for either group. Again, we count first the number of ways to split the people into uniformed groups, and then divide by $2$.

Call the groups B, R, and U (unpicked). It is convenient to first count the ways we can split into these groups, with no restriction. There are $3^{10}$ ways to do this. Now we remove the forbidden configurations, in which there are no B, or no R, or both. There are $2^{10}$ with no B, $2^{10}$ with no R. The sum $2\cdot 2^{10}$ double-counts the configurations in which there are no B and no R. It follows that there are $3^{10}-2\cdot 2^{10}+1$ legal configurations. Like before, divide by $2$. We get that the number of ways to choose $2$ groups neither of which is empty is $\frac{3^{10}-2\cdot 2^{10}+1}{2}$.

-
This is the answer assuming that there will be no players left unpicked, am I right? –  Boluc Papuccuoglu Apr 11 '14 at 19:54
Yes. One can also find an expression for the problem where there may be unpicked people. Is that the problem you are interested in? –  André Nicolas Apr 11 '14 at 19:58
I am unsure as to whether the OP's intent is asking that question or the other, so just trying to clarify. –  Boluc Papuccuoglu Apr 11 '14 at 19:59
@BolucPapuccuoglu: I assumed without checking that you were the OP. Have added to the post an answer to the modified problem, since it may be of interest. –  André Nicolas Apr 11 '14 at 20:11

Take one of the guy, say, Joe. We will form Joe's team. Either of the $9$ other players can be or not be in Joe's team, so there are $2^9$ choices.

But this include the case where all $10$ players are on the same team, so we remove $1$ from that, leading to $2^9-1$.

Added For completeness, I'll add a way if leftovers are allowed, but this method loses its efficiency in that case.

So either Joe will be picked, or he won't. If he is, the $9$ remaining players can go anywhere from Joe's team, his opponents or the leftovers, which gives $3^9$ possibilities. Of those, we need to substract the ones that leave the opposing team empty, namely $2^9$ of the $3^9$, giving a total of $3^9-2^9$ valid teams in which Joe is part of.

For those where Joe is not part of, we can use @Andre's methode to find $(3^9-2*2^9+1)/2$ (This is where the "Joe" method stops working.

Another way of solving this is to choose how many members from our original $10$ players are gonna be part of the teams, and then sum over the possible combinations. This would give $$\sum_{k=2}^{10}{10\choose k}(2^{k-1}-1).$$ The term $(2^{k-1}-1)$ can be found using "Joe" method. Note that the sum starts at $2$ because we don't allow for empty team.

-

The "proper" way to solve this is that you want to know the ways to partition 10 elements into 2 parts; the ways to partition $n$ elements into $k$ groups is given by the Stirling number of the second kind $\genfrac{\{}{\}}{0pt}{}{n}{k}$, in your case $\genfrac{\{}{\}}{0pt}{}{10}{2} = 511$ (value courtesy of Casio)

-