Let \(n, r\) be nonnegative integers with \(r\leq n\text{.}\) An \(r\)-combination of a set of \(n\) elements is the number of subsets of size \(r\) that can be chosen from a set of \(n\) elements. We denote it \(\binom{n}{r}\text{,}\) which is read “\(n\) choose \(r\text{.}\)”
Other common notation are \(C(n, r)\text{,}\) or \(nCr\text{.}\) We will use \(\binom{n}{r}\) notation, which we first saw in Section 5.1. For example, \(\binom{5}{4}\) is the number of subsets of size 4 chosen from a set of 5 elements.
Since order does not matter in a set, the order in which we choose elements of a set does not matter. Recall, when counting permutations, the order in which we chose our elements did matter. We can use what we know about permutations, though, to count combinations.
We can calculate combinations by first finding all the \(r\)-permuatations of a set, then dividing by all the possible orderings of that subset: \(\frac{P(n, r)}{r!}\text{.}\) This can be rewritten to be the standard formula for calculating combinations:
Note, since \(0!=1\text{,}\)\(\binom{n}{0}=1\) and \(\binom{0}{0}=1\text{.}\) This also makes sense with the definition, as there is only one set with 0 elements, the empty set.
We use combinations: \(\binom{15}{3}\text{.}\) It does not matter if a member was chosen first, second, or third, they would still be a member of the group. Thus, there are \(\frac{15!}{3!12!}=455\) ways to choose a group of 3.
Now suppose you want to choose a group of 3 students in a class of 15 for a group project, but the first student chosen will be the note-taker, the second will be the presenter, the third will manage the discussion. How many ways can you choose the group?
We use permutations: \(P(15, 3)\text{.}\) Now it does matter if a member was chosen first, second, or third, as each member has a different role. Thus, there are \(\frac{15!}{12!}=2730\) ways to choose a group of 3 where the members’ roles are defined.
In deciding whether to use combinations or permutations, you need to decide whether order matters. For combinations, order doesn’t matter; think about choosing subsets. For permuations, order does matter; think about choosing ordered lists.
We can think of forming a binary string with 2 ones as a list of 5 places where we need to choose 2 places for the ones. Once we’ve done that, the other places must have 0’s. Thus, we have five places and choose 2:
We can think of the string of letters as 6 places where we can choose to put letters. First we can choose the place to put the “l”: we have 6 places, we need to choose 1: \(\binom{6}{1}.\)
We can think of the string of letters as 6 places where we can choose to put letters. First we can think of all the letters as distinct. Then we have 6 letters to choose for the first place, 5 for the second, 4 for the third, etc. Thus we have \(6!\) ways to place 6 distinct letters.
But the letters are not distinct, so we need to divide by the number of ways we over-counted. For each permutation we just counted, switching the two “e”s gives us the same word, so we need to divide by the number of ways to rearrange the two “e”s: \(2!.\) Similarly, we need to divide by equivalent arrangements of the two “t”s: \(2!\text{.}\)
\(\binom{7}{1}\cdot \binom{6}{6}+\binom{7}{2}\cdot \binom{6}{5}+\binom{7}{3}\cdot \binom{6}{4}\text{,}\) count the groups of one junior and 6 seniors, two juniors and 5 seniors, three juniors and 4 seniors. Note, there are no groups with no juniors.
Find the number of groups with A and not B: \(\binom{11}{6}\text{.}\) Note, we only need to choose 6 out of 11 since we know A is in the group and B is not, so we just need to choose the other 6 members.
Now, find the number of groups with neither A nor B: \(\binom{11}{7}\text{.}\) Note, we need to choose 7 out of 11 since we know A and B cannot be chosen.
Two council members have the same major and are not permitted to serve together on a committee. How many ways can a committee of 6 be selected from the membership of the council?
Two council members always insist on serving together on a committee. If they can’t serve together, they won’t serve at all. How many ways can a committee of 6 be selected from the membership of the council?
Suppose the council consists of three freshmen, four sophomores, three juniors, and five seniors. How many committees of eight contain two from each class?
Suppose the exam instructions specify that at most one of the questions 1 and 2 may be included among the ten. How many different choices of the ten questions are there?
Suppose the exam instructions specify that either questions 1 and 2 are to be included among the ten or neither is to be included. How many different choices of ten questions are there?
In Morse code, symbols are represented by variable-length sequences of dots and dashes. For example, \(A=\cdot -, 1=\cdot - - - -, ?=\cdot \cdot - - \cdot \cdot\text{.}\) How many different symbols can be represented by sequences of seven or fewer dots and dashes?
