Transcript Permutations+Combina.. - SIUE Computer Science

MATH 224 – Discrete Mathematics
Counting
Basic counting techniques are important in many aspects of computer science. For
example, consider the two code segments below.
x = 0;
for (i=0; i < m; i++)
x = x+1;
for (j=0; j < n; j++)
x = x+1;
x = 0;
for(i=0; i < m; i++) {
for (j=0; j<n; j++)
x = x+1;
} // rof
What is the value of x after executing the code on the right, after
executing the code on the left?
4/13/2015
1
MATH 224 – Discrete Mathematics
Counting
In the code segments below what happens to x?
x = 0;
for (i=0; i < m; i++)
x = x+1;
for (j=n; j > 1; j=j/2)
x = x+1;
x = 0;
for(i=0; i < m; i++) {
for (j=n; j>1; j=j/2)
x = x+1;
} // rof
What is the value of x after executing the code on the right, after
executing the code on the left?
4/13/2015
2
MATH 224 – Discrete Mathematics
Counting License plate numbers
Consider a license plate that has six characters where the first 3 are digits and the
last three are upper case letters. If zeros are not allowed for the first two digits and
there are five three letter sequences that are not allowed, how many different license
plates are possible.
With three decimal digits there are 1000 possible numbers. There are
100 numbers with a leading zero and 100 numbers with a zero as the
second digit. As a result there are 1000 – 100 – 100 + 10 = 810
possible 3 digit sequences. Why was 10 added? What about 9*9*10
possible values?
Then there are 263 = 17,576 three character sequence with five not
allowed. So we have a total of 810*17,571 = 14,236,560.
4/13/2015
3
MATH 224 – Discrete Mathematics
Counting IPv4 Internet Addresses
Each address consists of 4 bytes, that is written as four decimal numbers. For example,
the internet address of the CS web pages is 146.163.150.3. Each of the four parts is
written as a decimal number that may take on values between 0 and 255. What is the
total number of addresses that are available? 2564 = 4,294,967,296
Some of these are not used as address, but have special meaning. So just as an
example, the first byte may not be 0 or 255, and the last byte may not be 0 or 255. Let’s
determine the number of addresses taking these restrictions into account. (Note that
Example 16 on Page 341 of our text gives the complete set of restrictions for IPv4
addresses.)
For the last byte not being 0 or 255 we get 2*224 =33,554,432, and also for the first byte
33,554,432 for all ones or all zeroes. So we have a total of 4,294,967,296 + 4*216
−33,554,432 −33,554,432 = 4,228,120,576. Why was 4*216 added to the total? How
does this compare with the result in our text? Why do you think that even more
addresses are needed? IPv6 uses 8 bytes for addresses giving 2568 =
18,446,744,073,709,551,616 possibilities before subtracting those that are used for a
general address.
4/13/2015
4
MATH 224 – Discrete Mathematics
Permutations
Permutations count the number of ways distinct objects can be arranged. So for example
three different blocks can be arranged in 3! or six ways.
How many ways can four different blocks be arranged? How
many was can n different blocks be arrange.
4/13/2015
5
MATH 224 – Discrete Mathematics
Permutations
If we choose r objects out of n objects that is called the number of r-permutation
from a set of n elements, P(n, r). We assume that n ≥ r ≥ 0. How many ways can
four blocks where only two are selected be arranged?
P(n, r) = n!/(n-r)!, so in this case we have 4!/2! = 24/2 = 12. Note when n = r
the denominator is 0!. In order to make this formula work and for other reasons,
0! is defined to be 1.
4/13/2015
6
MATH 224 – Discrete Mathematics
Permutations
If we have a pair of dice, how many different patterns, counting order, are possible?
This is just the number of 2-permutations of 6 distinct items plus the case were both
numbers are the same. Thus we have P(6,2) + 6 = 6!/(6-2)! + 6 = 720/24 + 6 = 36. Do
you know a simpler way to determine this number? This may more easily be
determined as 62.
The traveling salesperson problem asks a person to visit a number of different places
and then return to the starting point. How many different tours are possible for 5
locations? The answer is 5! if we allow any starting point. What will the number be
if we fix the starting point? What if we want to find the shortest tour and the
number of cities is large? For example, what are the number of tours if there are
20 cities? If we fix the starting point the number of tours would be
121,645,100,408,832,000. Can we check all of them to find the shortest?
0
3
4/13/2015
2
1
4
7
MATH 224 – Discrete Mathematics
Combinations
Sometimes all we care about is the items that are selected and not the order in which they
are selected, e.g., a hand of cards. So for example if we have four different block colors
and want to know the number of different sets of two blocks, we have to divided the
number of permutations by the number of different orderings. In this case, each of the
larger boxes represents a single combination since only the colors matter not the order.
4/13/2015
8
MATH 224 – Discrete Mathematics
Combinations
Combinations count the number of ways of choosing r objects from a set of n
objects r-choose n, where order doesn’t count. So C(n, r) = P(n, r)/r!. Here we
divide by the number of ways of ordering r objects.
In this case we have C(4, 2) = 4!/2!2! = 24/4 = 6. Note that the number of
combinations is also the same as the binomial coefficient that we have
already seen.
4/13/2015
9
MATH 224 – Discrete Mathematics
Combinations
Combinations are written as C(n, r) often read as n choose r. The formula for
combinations is C(n, r) = P(n, r)/P(r, r) = P(n, r)/r! = n!/(n-r)!r! The combinations
of n choose r are the same as the binomial coefficients that we have already seen.
Note that C(n, r) = C(n, n-r) since C(n, r) = n!/(n-r)!r! and C(n, n-r) = n!/r!(n-r)!.
We can use combinations to determine how many different hands of cards can be
drawn since order does not matter. If we are playing 5-card draw the number of
hands is 52!/47!∙5! = 52∙51∙50∙49∙48/120 = 2,598,960. We can use this to determine
the probability of getting a royal flush. To get a royal flush you must have the ace,
king, queen, jack, and 10 all from the same suit. Since there are 4 suits and order
does not matter, the chances of getting a royal flush is 4/2,598,9760 ≈ 0.00015%.
That is pretty low odds.
4/13/2015
10
MATH 224 – Discrete Mathematics
Combinations, Binomial Coefficients &
Pascals Triangle
1
B(j, k) =
1 = 20
j≥k≥0
1 1
1 if k = 0 or j = k
B(j –1,k –1)+B(j – 1,k,)
1
2 1
4 = 22
8 = 23
1 4 6 4 1
16 = 24
1 5 10 10 5 1
32 = 25
1 6 15 20 15 6 1
64 = 26
1 7 21 35 35 21 7 1
128 = 27
28 56 70 56 28 8 1
9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
4/13/2015
2 = 21
1 3 3 1
all other cases
1 8
1
Sum of Row
256 = 28
512 = 29
1024 = 210
11
MATH 224 – Discrete Mathematics
Combinations
Combinations may also be used to determine the number of ways of getting a
particular result when tossing coins. For example, if we want to determine the likely
hood of getting 4 heads when tossing a coin 8 times we need to consider the number
of ways of getting 4 heads and 4 tails. That is just C(8,4) = 8!/4!4! = 70. Then there
are 28 = 256 possible outcomes so the probability of getting 4 heads is 70/256 ≈
0.273. What would C(8,0)+C(8,1) + … + C(8,8) be?
Well that would be 1 + 8 + 28 +56 +70 +56 + 28 + 8 + 1 = 256. Do you know what
result you always get when adding all the disjoint probabilities?
4/13/2015
12