2n = Number of subsets of n items = number of n-bit binary strings n! = Number of ways to order n different items
P(n, r) = n!/(n r)! = n(n 1) … (n r+1)
= The number of ways to fill r named bins, 1..r, one
item per bin, using items drawn from 1,…,n. No replacement; an item, once used, is gone.
1
ECS 20 — Lecture 18 — Fall 2013 —26 Nov 2013
Phil Rogaway
Today:
Let’s count!
Side board
…
123
1 2 3 4
r-2 r-1 r
n-3 n-2 n-1 n
C(n, r) = n! / r!(n r)! = P(n, r)/r!
= number of r-element subsets from a
set of n different items.
No replacement; an item, once used, is gone.
1 2 3 4
In particular, C(n,2) = n(n1)/2
n-3 n-2 n-1 n
S,
|S| = r
product rule = if event A can occur in a ways and, independent of this, event B can occur in b ways, then the number of combinations of ways for A and B to occur is ab.
Really just a statement that |A B| = |A| |B| for finite A, B.
sum rule = if event A can occur in a ways and
event B can occur in b ways, but both events
cannot occur together, then the number of ways for A or B to occur is a+b. Really just a statement that |A B| = |A|+|B| for disjoint A, B.
inclusion/exclusion counting: |A B| = |A||B||AB|
And generalizations, like
|A B C| = |A||B||C| |AB| |BC| |AC| + |ABC|
ln (n!) n ln n n Stirlings’s formua
Example counting exercises
Please calculate values explicitly to the point of getting out numbers – I like to see actual numbers.
1. License plates in Nebraska are 3 distinct letters (A-Z, but not O), followed by 3 distinct decimal digits. How many possible license plates are there?
Answer: 25*24*23*10*9*8 = P(25,3) P(10,3) = 9,936,000
2. How many ways can a blue, white, and red ball be put into 10 different bins? Assume no bin can contain two balls.
Answer: 10*9*8 = P(10,3) = 720
3. How many different ways a salesman travel among
n cities, where he starts in city 1 and visits each
other city once and only once before returning to city 1.
Answer: (n 1)!
4. How many ways can you select a president, vice president,
and treasurer in a club of 30 people? Answer: P(30,3) = 24,360
5. How many way can you form Male-Female dance partners if there are 12 women and 8 men. Assume each man is partnered with some woman (4 women go un-partnered).
Answer: P(12,8) = 19,958,400
6. How many ways you position 7 people in a circle?
Answer: 6! = 720
2
7. A man, a woman, a boy, a girl, a dog, and a cat are walking single-file down the road.
a. How many ways can this happen? Answer: 6! = 720
b. How many ways if the dog comes first? Answer: 5! = 120
c. How many ways if the dog immediately follows the boy? Answer: 5! = 120
d. How many ways if the dog (and only the dog) is immediately between the man and the boy.
Answer: 2*4! = 48 (form a man-dog-boy or a boy-dog-man combo)
(so walking down the street is a woman, a girl, a cat, and a man-dog-boy (4!)
or, walking down the street is a woman, a girl, a cat, and a boy-dog-man (4!)
8. In how many ways can 10 adults and 5 children be positioned
in a line so that no two children are next to each other? (they fight)
Answer: 10!*P(11,5) = 10! 11! / 6! = 201,180,672,000 1011.3 AAAAAAAAAAA
12345
9. How many arrangements are there of the letters a..z such that there are exactly 10 letters between the “A” and the “Z”?
Answer: 15!*P(24,10)*2 = 24!*30 1.86*1025
(reasoning: after selecting the AxxxxxxxxxxZ block, treat it as atomic
and rearrange it with the 14 remaining letters in any of 15! ways. Double to account for both the AxxxxxxxxxxZ and ZxxxxxxxxxxA possibilities.)
10. You take a group of four people to a Chinese restaurant that has 100 different dishes. All food will be shared among the four of you. How many ways can you order 4 different dishes?
Answer: C(100,4) = 100*99*98*97 / (4*3*2*1) = 3,921,225
11. You toss a coin 8 times. How many ways can it land with 5 heads total?
Answer: C(8,5) = 56
(Note this is C(8,3). In general, C(n,r) = C(n,n-r).)
3
12. How many 6-element subsets are there of the 26 letters, A … Z ? Answer C(26,6) = 230,230
How many 2-element subsets are there of the 26 letters, A … Z ? C(26,2) = 26*25/2 = 338.
In general, C(n,2) = n(n1)/2
13. An urn contains 15 red, distinctly numbered, balls, and 10 white, distinctly numbered balls.
5 balls are removed.
(A) How many different samples are possible?
Answer: C(25,5) = 53,130
(B) How many samples contain only red balls?
Answer: C(15,5) = 3003.
(B’) So what is the probability that a random sample will contain only red balls?
Answer: 3003 / 53,130 0.05652 (05.652 %) (a little more than about 1 in 18) (C) How many samples contains 3 red balls and 2 white balls?
Answer: C(15,3) * C(10,2) = 20,475
(C’) So what’s the chance that a random sample will contain 3 red balls
and one white ball
Answer: 20,475 / 53,130 0.3854 (38.54%)
14. How many numbers are there between 1 and 1000 have are not divisible by 3, 5, or 7
Let A3 = numbers between 1 and 1000 that are divisible by 3. |A3|=333
Let A5 = numbers between 1 and 1000 that are divisible by 5. |A5|=200
Let A7 = numbers between 1 and 1000 that are divisible by 7. |A7|= 1000/7 =142
Let A3,5 = numbers between 1 and 1000 that are divisible by 3 & 5. | A3,5 | = 1000/15 Let A5,7 = numbers between 1 and 1000 that are divisible by 5 & 7. | A3,5 | = 1000/35 Let A3,7 = numbers between 1 and 1000 that are divisible by 3 & 7. | A3,5 | = 1000/21
Let A3,5,7 = nums between 1 and 1000 that are divisible by 3 &5& 7. | A3,5,7 | = 1000/3*5*7 So answer = = 457
15. How many numbers divide pq where p and q are distinct, large primes? (n) = | {i [1..n]: i | n}. pq n q p 1 = (p 1)(q 1)
4