For example, you have a bag of 12 uniquely colored marbles. Pick 5 marbles out of the bag. This set of 5 marbles is one pick. Toss the marbles back in the bag. Pick 5 marbles again, making sure that the selection differs from the first pick. So on and so forth. The question is, how many unique picks of 5 marbles can you make?
In general, all the ways you can pick r items out of n items is called the combination of n things taken r at a time (or r-combination). Notation:
n!
C(n,r) = -------- reads "The combination of n things taken r at a time" or
(n-r)! r! "n choose r" _
n^r
Since n!/(n-r)! is the falling powers of n^r, C(n,r) = ----
r!
An r-combination is the number of all possible unordered subsets of r objects
taken from a set of n objects. You can consider C(n,r) in terms of sets:
Let S = {1,2,3,4}
C(4,0) = 1 possible subset of size 0: {}
C(4,1) = 4 possible subsets of size 1: { {1}, {2}, {3}, {4} }
C(4,2) = 6 possible subsets of size 2: {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}
C(4,3) = 4 possible subsets of size 3: { {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4} }
C(4,4) = 1 possible subset of size 4: { {1,2,3,4} }
The formula C(n,r), 0 <= r <= n, yields the same results:
C(4,0) = 4!/(4!0!) = 1
C(4,1) = 4!/(3!1!) = 4
C(4,2) = 4!/(2!2!) = 6
C(4,3) = 4!/(3!1!) = 4
C(4,4) = 4!/(4!0!) = 1
Observations:
n
Given |S| = n, [ C(n,r) = |P(S)|.
r=0
The ways to pick r objects out of n is equivalent to the ways to pick
n - r objects to be left behind; thus, C(n,r) = C(n,n-r).
C(n,n) = 1
C(n,1) = n
C(n,0) = 1
For example, let S={1,2,3,4}. P(4,2) is the number of permutations of the subsets of size 2 taken from S. Since the number of subsets is C(4,2) and a set of size 2 has 2! bijections, P(4,2) = 2! * C(4,2). Thus, P(4,2) = 4!/2!, which is 4 to the falling powers of 2. The 12 permutations of P(4,2) are shown here:
{ (1,2), (1,3), (1,4),
(2,1), (2,3), (2,4),
(3,1), (3,2), (3,4),
(4,1), (4,2), (4,3) }
P(4,2) = 12.
Formula:
n!
P(n,r) = -----
(n-r)!
_
= n^r reads "n to the falling powers of r"
C(4,2) = 4*3/2 = 6.
P(4,2) = 4*3 = 12.
Since arrangement does not matter, tuples such as (1,2) and (1,2) are counted
as 1 item:
{ (1,2), (1,3), (1,4),
(2,3), (2,4), (3,4), }
A Caesar cipher is a permutation over the letters of the alphabet where each
plaintext letter is translated to the letter a fixed number of letters after
it in the alphabet. A cipher that maps each letter to its neighbor three
letters to the right is shown here:
Plaintext A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Ciphertext X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
f("APPLES") = "XMMIBP"
The total number of permutations of S is the number of bijections from S -> S,
which is |S|!. For an alphabet of 26 letters, the number of permutations is 26!.
Observations:
C(n,r) is P(n,r) divided by r!.
_
P(n,n) = n^n = n!
P(n,0) = 1
P(n,1) = n
C(7,7) = 1
C(7,1) = 7
C(7,0) = 1
P(7,4) = 7*6*5*4
P(7,7) = 7!
P(7,1) = 7
P(7,0) = 1
Example 1.
Count the ways you can arrange 4 out of 10 people in a row. This is P(10,4),
which is 10!/6! = 10*9*8*7 = 5040.
Example 2.
The ways you can pick 4 out of 10 people to serve on a committee is C(10,4).
C(10,4) = 10*9*8*7/(4*3*2) = 210
The ways to pick 6 people out of the 10 to NOT serve on a committee is C(10,6).
C(10,6) = 10*9*8*7/(4*3*2) = 210
Example 3. The ways you can pick 5 cards out of a deck of 52 cards is an
r-combination since order does not matter. This is C(52,5) = 52^5_/5!
= 52*51*50*49*48/5*4*3*2
= 52*51*10*49*2
= 2,598,960
Example 4.
The number of 5-card hands that are flushes is a product of r-combinations.
This is the number of ways to pick 5 cards from the same suit. In a deck
of 52 cards, there are 4 suits and 13 faces (13 faces per suit thus 4*13=52).
You first pick a suit. Then you pick 5 faces from that suit.
C(4,1)C(13,5)
Example 5.
C(13,1)C(4,4)C(48,1)
Example 6.
C(13,1)C(4,2)C(50,3) = 13*6*(50*49*8)
Note: the expression C(13,1)C(4,1)C(3,1)C(50,3) is not correct. Why? Because
that expression
is incorrectly assuming that position matters. E.g., C(4,1)C(3,1) = 12
whereas C(4,2) = 4*3/2 = 6.
Example 7.
How many bit strings of length 10 contain 3 '1's?
(Think of this as the number of ways you can put a '1' into a bit string.)
C(10,3)
Example 8.
a) the string AB?
Glue AB into a single item. There are 6 remaining items. There are thus 7!
permutations of all items:
P(7,7) = 5040
b) the string ABC?
Glue ABC into a single item. There are 5 remainining letters. Thus,
there are 6! possibilities:
P(6,6) = 720
c) the string BA and EDC?
Glue the substrings into 2 items. There are thus 5 total items:
P(5,5) = 5! = 120
Example 9. Divide all possible arrangements by 7 to eliminate duplicates. Thus, 7!/7 = 6!
Example 10.
A group of 100 potential jurists are grouped as follows:
Panel A=45 people; Panel B=35; Panel C=20
How many ways are there to select 12 jurists if 5 are selected Panel A, 4 are selected from Panel B, and the other 3 are selected from the Panel C?
Apply the Product Rule to all possible arrangements of the 3 panels:
C(45,5) * C(35,4) * C(20,3)