# mixed permutations and combinations

I have a problem that I am not too sure of. In a team of 16, there are 5 couples and 6 single people. In how many ways can at most 1 couple be chosen if 6 people are required to represent the team at a conference?

This is my solution: 6P6 (0 couples and 6 single people only) + 11C6 * 6! * 2! (choose 1 member of a couple and the other 6 single people, this can be done in 2!*6! ways) + 5C1 * 2! * 10C4 *2! * 4! (exactly one couple is chosen and any of the singles along with the other partners of the other couples)

Is this correct?

The following approach is reasonably systematic. There will be lots of words, but at the end there will be a more or less compact formula.

We count first the teams that have no couple, then, in basically the same way, the teams that have $1$ couple. A couple, viewed as an entity, will be called a family. There are $5$ families.

No couples: Maybe we choose $6$ singles. That can be done in $\binom{6}{6}$ ways. Of course this is $1$, but we call it by the complicated name $\binom{6}{6}\binom{5}{0}2^0$. Soon that will look reasonable!

Or else we pick $5$ singles, $1$ family, and a representative of the family. This can be done in $\binom{6}{5}\binom{5}{1}2^1$ ways.

Or else we pick $4$ singles, $2$ families, and a representative of each family. This can be done in $\binom{6}{4}\binom{5}{2}2^2$ ways.

Or else we pick $3$ singles, $3$ families, and a representative of each family. This can be done in $\binom{6}{3}\binom{5}{3}2^3$ ways.

Or else we pick $2$ singles, $4$ families, and a representative of each family. This can be done in $\binom{6}{2}\binom{5}{4}2^4$ ways.

Or else, finally, we pick $1$ singles, $5$ families, and a representative of each family. This can be done in $\binom{6}{1}\binom{5}{5}2^5$ ways.

Add up. A number of cases, but only one idea.

One couple: The idea is the same. There are $\binom{5}{1}$ ways o pick the couple. We will count the number of ways to pick the remaining $4$ people, add them up, and multiply by $\binom{5}{1}$. But rom here on, we only count the ways of picking the $4$.

We could pick $4$ singles. This can be done in $\binom{6}{4}$ ways, but we call the number $\binom{6}{4}\binom{5}{0}2^0$.

Or else we pick $3$ singles, $1$ family, and a representative of the family. This can be done in $\binom{6}{3}\binom{5}{1}2^1$ ways.

Or else we pick $2$ singles, $2$ families, and a representative of each family. This can be done in $\binom{6}{2}\binom{5}{2}2^2$ ways.

Or else we pick $1$ single, $3$ families, and a representative of each family. This can be done in $\binom{6}{1}\binom{5}{3}2^3$ ways.

Or else, finally, we pick $0$ singles, $4$ families, and a representative of each family. This can be done in $\binom{6}{0}\binom{5}{4}2^4$ ways.

Final answer: We gather the whole thing into a compact formula. $$\sum_{i=0}^5 \binom{6}{6-i}\binom{5}{i}2^i +\binom{5}{1}\sum_{i=0}^4 \binom{6}{4-i}\binom{5}{i}2^i.$$

You’re off on the wrong foot right away with that $6$P$6$ for the case in which the team is made up entirely of singles: there is only one such team, and you’re counting $6!=720$. We’re not picking six people and assigning each of them a specific rôle; we’re just picking a group of $6$ people. If we pick them from the singles, we can do it in $\binom66=1$ way.

I think that I’d break it down according to how many singles we choose.

• As we just saw, there is one team consisting of $6$ singles.

• To form a team with $5$ singles, we can pick the singles in $\binom65=6$ ways and the sixth person in $\binom{10}1=10$ ways for a total of $6\cdot10=60$ teams.

• To form a team with $4$ singles, we can pick the singles in $\binom64=15$ ways. And since we’re allowed one couple, we can pick any two of the other ten people, so there are $\binom{10}2=45$ to pick the other two members of the team. That gives us another $15\cdot45=675$ teams.

• $3$ singles can be picked in $\binom63=20$ ways, and we can pick any three of the other ten people, so we get another $20\binom{10}3=20\cdot120=2400$ teams.

Now it gets a little trickier, since we start running into restrictions on whom we can choose from the couples.

• $2$ singles can be picked in $\binom62=15$ ways. There are $\binom{10}4=210$ ways to pick $4$ people from the couples, but some of these are forbidden: specifically, we may not pick two couples. Since there are $5$ couples altogether, there are $\binom52=10$ pairs of couples. That’s $10$ sets of four people that we aren’t allowed to choose, leaving $210-10=200$ sets that we are allowed to choose. Thus, we can form $15\cdot200=3000$ teams with $2$ singles.

• One single can be picked in $6$ ways. There are $\binom{10}5=252$ ways to choose $5$ people from the couples, but here again some are not allowed. Specifically, we have to throw out those groups that consist of two-and-a-half couples. As before, there are $\binom52=10$ ways to pick two couples, and there are then $6$ ways to pick one more person from the remaining three couples. That makes $10\cdot6=60$ ways to fill out the team and gives us $6\cdot60=360$ teams.

There’s one more case, the teams containing no singles; I’ll let you have a chance to work it out on your own, but feel free to ask if you get stuck.