Lecture 1: Permutations and combinations

18.440: Lecture 1 Permutations and combinations, Pascal’s triangle, learning to count Scott Sheffield MIT 18.440 Lecture 1 1 Outline Remark, just for fun Permutations Counting tricks Binomial coefficients Problems 18.440 Lecture 1 2 Outline Remark, just for fun Permutations Counting tricks Binomial coefficients Problems 18.440 Lecture 1 3 Politics � Suppose that betting markets place the probability that your favorite presidential candidates will be elected at 58 percent. Price of a contact that pays 100 dollars if your candidate wins is 58 dollars. � Market seems to say that your candidate will probably win, if “probably” means with probability greater than .5. � The price of such a contract may fluctuate in time. � Let X (t) denote the price at time t. � Suppose X (t) is known to vary continuously in time. What is the probability it will reach 59 before reaching 57? � “Efficient market hypothesis” suggests about .5. � Reasonable model: use sequence of fair coin tosses to decide the order in which X (t) passes through different integers. 18.440 Lecture 1 4 Which of these statements is “probably” true? � � 1. X (t) will go below 50 at some future point. � � 2. X (t) will get all the way below 20 at some point � � 3. X (t) will reach both 70 and 30, at different future times. � � 4. X (t) will reach both 65 and 35 at different future times. � � 5. X (t) will hit 65, then 50, then 60, then 55. � � Answers: 1, 2, 4. � � Full explanations coming at the end of the course. � � Point for now is that probability is everywhere: politics, military, finance and economics, all kinds of science and engineering, philosophy, religion, making cool new cell phone features work, social networking, dating websites, etc. � � All of the math in this course has a lot of applications. 18.440 Lecture 1 5 Outline Remark, just for fun Permutations Counting tricks Binomial coefficients Problems 18.440 Lecture 1 6 Outline Remark, just for fun Permutations Counting tricks Binomial coefficients Problems 18.440 Lecture 1 7 Permutations � I How many ways to order 52 cards? � I Answer: 52 · 51 · 50 · . . . · 1 = 52! = 80658175170943878571660636856403766975289505440883277824× 1012 � I n hats, n people, how many ways to assign each person a hat? � I Answer: n! � I n hats, k < n people, how many ways to assign each person a hat? � I n · (n − 1) · (n − 2) . . . (n − k + 1) = n!/(n − k)! � I A permutation is a map from {1, 2, . . . , n} to {1, 2, . . . , n}. There are n! permutations of n elements. 18.440 Lecture 1 8 Permutation notation � I A permutation is a function from {1, 2, . . . , n} to {1, 2, . . . , n} whose range is the whole set {1, 2, . . . , n}. If σ is a permutation then for each j between 1 and n, the the value σ(j) is the number that j gets mapped to. � I For example, if n = 3, then σ could be a function such that σ(1) = 3, σ(2) = 2, and σ(3) = 1. � I If you have n cards with labels 1 through n and you shuffle them, then you can let σ(j) denote the label of the card in the jth position. Thus orderings of n cards are in one-to-one correspondence with permutations of n elements. � I One way to represent σ is to list the values σ(1), σ(2), . . . , σ(n) in order. The σ above is represented as {3, 2, 1}. � I If σ and ρ are both permutations, write σ ◦ ρ for their composition. That is, σ ◦ ρ(j) = σ(ρ(j)). 18.440 Lecture 1 9 Cycle decomposition � I Another way to write a permutation is to describe its cycles: I � For example, taking n = 7, we write (2, 3, 5), (1, 7), (4, 6) for the permutation σ such that σ(2) = 3, σ(3) = 5, σ(5) = 2 and σ(1) = 7, σ(7) = 1, and σ(4) = 6, σ(6) = 4. � I If you pick some j and repeatedly apply σ to it, it will “cycle through” the numbers in its cycle. � I Generally, a function is called an involution if f (f (x)) = x for all x. � I A permutation is an involution if all cycles have length one or two. � I A permutation is “fixed point free” if there are no cycles of length one. 18.440 Lecture 1 10 Outline Remark, just for fun Permutations Counting tricks Binomial coefficients Problems 18.440 Lecture 1 11 Outline Remark, just for fun Permutations Counting tricks Binomial coefficients Problems 18.440 Lecture 1 12 Fundamental counting trick � I n ways to assign hat for the first person. No matter what choice I make, there will remain n − 1 was to assign hat to the second person. No matter what choice I make there, there will remain n − 2 ways to assign a hat to the third person, etc. � I This is a useful trick: break counting problem into a sequence of stages so that one always has the same number of choices to make at each stage. Then the total count becomes a product of number of choices available at each stage. � I Easy to make mistakes. For example, maybe in your problem, the number of choices at one stage actually does depend on choices made during earlier stages. 18.440 Lecture 1 13 Another trick: overcount by a fixed factor � I If you have 5 indistinguishable black cards, 2 indistinguishable red cards, and three indistinguishable green cards, how many distinct shuffle patterns of the ten cards are there? � I Answer: if the cards were distinguishable, we’d have 10!. But we’re overcounting by a factor of 5!2!3!, so the answer is 10!/(5!2!3!). 18.440 Lecture 1 14 Outline Remark, just for fun Permutations Counting tricks Binomial coefficients Problems 18.440 Lecture 1 15 Outline Remark, just for fun Permutations Counting tricks Binomial coefficients Problems 18.440 Lecture 1 16 n k
notation � I How many ways to choose an ordered sequence of k elements from a list of n elements, with repeats allowed? � I Answer: nk � I How many ways to choose an ordered sequence of k elements from a list of n elements, with repeats forbidden? � I Answer: n!/(n − k)! � I How many way to choose (unordered) k elements from a list of n without repeats? � I Answer: � I What is the coefficient in front of x k in the expansion of (x + 1)n ? � I Answer: 18.440 Lecture 1 n k n k := n! k!(n−k)! . 17 Pascal’s triangle � I Arnold principle. � I A simple recursion: � I � I What is the coefficient in front of the expansion of (x + 1)n ?
Answer: kn .



n−1
n (x + 1)n = n0 · 1 + n1 x 1 + n2 x 2 + . . . + n−1 x + nn x n .
Question: what is nk=0 kn ? � I Answer: (1 + 1)n = 2n . � I � I n k
= n−1 k−1
n−1 k k x in +
. 18.440 Lecture 1 18 Outline Remark, just for fun Permutations Counting tricks Binomial coefficients Problems 18.440 Lecture 1 19 Outline Remark, just for fun Permutations Counting tricks Binomial coefficients Problems 18.440 Lecture 1 20 More problems � I � I How many full house hands in poker?

13 43 · 12 42 � I How many “2 pair” hands?


13 42 · 12 42 · 11 41 /2 � I How many royal flush hands? � I 4 I � 18.440 Lecture 1 21 More problems � I � I How many hands that have four cards of the same suit, one card of another suit?

13 4 13 4 ·3 1 I � How many 10 digit numbers with no consecutive digits that agree? � I If initial digit can be zero, have 10 · 99 ten-digit sequences. If initial digit required to be non-zero, have 910 . � I How many 10 digit numbers (allowing initial digit to be zero) in which only 5 of the 10 possible digits are represented? � I This is one is tricky, can be solved with inclusion-exclusion (to come later in the course). � I How many ways to assign a birthday to each of 23 distinct people? What if no birthday can be repeated? � I 36623 if repeats allowed. 366!/343! if repeats not allowed. 18.440 Lecture 1 22 MIT OpenCourseWare http://ocw.mit.edu 18.440 Probability and Random Variables Spring 2014 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.