When counting various outcomes sometimes the order of things does not matter. If so, each unique unordered outcome is called a combination.
Once again, consider the permutations when selecting three letters from {A, B, C, D}.
A,B,C
A,C,B
B,A,C
B,C,A
C,A,B
C,B,A
A,B,D
A,D,B
B,A,D
B,D,A
D,A,B
D,B,A
A,C,D
A,D,C
C,A,D
C,D,A
D,A,C
D,C,A
B,C,D
B,D,C
C,B,D
C,D,B
D,B,C
D,C,B
Notice how these 24 permutations fall into only four distinct categories if the order does not matter. Therefore, from a group of size four you can pick an unordered subset of size three in only 4 ways rather than the original 24.
In general, it would be nice to have a direct formula to determine the number of such combinations without having to explicitly list them all out.
Theorem3.4.1.Combinations of a subset without replacement.
The number of ways to select an unordered group of r items from a set of n distinct items is
Consider creating a permutation of r objects from a set of size n by first picking an unordered subset of size r and then counting the number of ways to order that subset. Using our notation and the multiplication principle,
Label each item in your group in some defined order. Since order doesn’t matter, as you repeatedly sample r times with replacement you can always write down your outcomes sorted from low to high placement. Finally, separate like values by some symbol, say "|", and consider each of the n distinct objects as indistinct *’s. There will be n-1 of these separators since there will be n to choose from. For example, if choosing r=6 times from the set {a, b, c, d}, then the outcome b, b, a, d, a, b could be collected as a, a, b, b, b, d and written in our code as **|***||* . Notice that shuffling around the identical *’s would not change the code (and similarly for the identical |’s) but swapping a * with a | would be a different outcome. Therefore, we can consider this to be a multinomial coefficient 3.3.5 and the number of ways to rearrange this code is
A standard deck of cards consists of four suits (clubs, diamonds, hearts, and spades), with each suit containing 13 cards (ace, two through ten, jack, queen, and king) for a total of 52 cards in all.
How many 7-card hands will consist of exactly 2 hearts and 3 clubs?
Notice that to determine the number of outcomes required you to use the combination forumula several times and then multiply the results using the multiplication principle.
A school dance committee is to consist of 2 freshmen, 3 sophomores, 4 juniors, and 5 seniors. If 7 freshmen, 9 sophomores, 7 juniors, and 7 seniors are eligible to be on the committee, in how many ways can the committee be chosen?
\({7 \choose 2}\) ways to choose 2 freshmen for the committee, \({9 \choose 3}\) ways to choose 3 sophomores for the committee, \({7 \choose 4}\) ways to choose 4 juniors for the committee, and \({7 \choose 5}\) ways to choose 5 seniors for the committee. So by the generalized basic principle of counting, there are a total of
Once again, you can see that using the formulas can be easy and also can be part of a bigger problem pasted together using the multiplication principle.
Revisiting your ipad’s security, what happens if the order in which the digits are entered does not matter? If so, then you would be picking a combination of 4 digits without replacement from a group of 10 digits. Namely,
which once again is more since numbers are allowed to repeat.
Definition3.4.6.Binomial Coefficients.
The value \(_nC_r\) is known as the binomial coefficient. It is denoted by \({n \choose r}\) and is read "n choose r".
Binomial coefficients have a number of interesting properties. Many of these are very useful as well in probability calculations. Several of these properties are collected below. In particular, these relationships verify that the binomial coefficients are the values found in Pascal’s Triangle.