### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 533 Class Note for STAT 22500 with Professor Martin at Purdue

### View Full Document

## 16

## 0

## Popular in Course

## Popular in Department

This 10 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Purdue University taught by a professor in Fall. Since its upload, it has received 16 views.

## Similar to Course at Purdue

## Reviews for 533 Class Note for STAT 22500 with Professor Martin at Purdue

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

Stat 225 Lecture Notes Counting Techniques Ryan Martin Spring 2009 1 Basic Counting Rule Recall that in the classical probability model7 the probability of an event E is ME l E 7 11 lt gt m lt gt the number of outcomes in E divided by the total number of outcomes Counting the number of outcomes that make up a given event can be very dif cult and impractical since7 even for relatively simple situations7 there can be a tremendous number of such outcomes For example 0 There are 275987960 ways to deal a poker hand 0 A sequence of 10 tosses of a coin has 1024 possible outcomes 0 There are 13983816 to select 6 out of 49 lottery numbers Let7s consider an easier example rst Example 11 Suppose we ip a coin and then roll a 6 sided die Let E be the event that we get a Tail77 on the coin and an even number on the die To use formula 11 to nd ENE7 we need to know the total number of outcomes From a tree diagram see Figure 1 it is easy to see that there are 12 possible outcomes Three of the outcomes result in a Tail77 and an even roll7 therefore7 ME 312 025 Exercise 12 I own 5 shirts7 2 pair of pants and two pair of shoes How many di erent out ts could I wear Draw a tree diagram Mathematicians are lazy and did not want to work this hard They developed a set of counting rules7 which are included in what is called combinatorics The rst is the Basic Counting Rule BCR7 often called the multiplication rule for obvious reasons Proposition 13 BCR Suppose that r actions are to be performed in a de nite order Suppose further that there are ink possibilities for action k for k 1 r Then there are mlmg m possibilities altogether for the r actions Fig 1 A tree diagram for Exercise 11 The rst set of branches denote the outcome of the coin toss H or T and the second set denote the outcome of the die roll 176 Exercise 14 If you rolled four fair six sided dice7 what is the probability that you get at least one 3 Exercise 15 How many di erent pizzas can be made with 10 distinct toppings More generally7 how many possible subsets does a set containing 71 elements have Exercise 16 Let A and B be nite sets7 each with n elements How many one to one functions are there from A to B Relate your answer to the number of tries it would take to successfully decode a simple substitution cipher by guessing Note a substitution cipher is the coding scheme used in a standard cryptogram 2 Sampling With and Without Replacement De nition 21 Consider a population with N members 0 Sampling with replacement is where 71 members of the population are selected7 one at a time7 and after the observation is made the member is returned to the population for possible re selection 0 Sampling without replacement is the same as with7 except the selected member is not returned to the population for re selection Exercise 22 ls the experiment of ipping a coin ve times considered sampling with replacement or without Exercise 23 How many possible outcomes are there if you draw three cards from standard deck with replacement Without replacement Exercise 24 A baseball team has nine starting players How many di erent batting orders does the coach have to choose from 3 Permutations First is a de nition you may recall from calculus De nition 31 The product of the rst n positive integers is called n factorial and is denoted by nl De ne 0 1 De nition 32 A permutation of r objects from a collection of m objects is any ordered arrangement of r distinct objects from the m objects The number of possible permuta tions of r objects that can be formed from a collection of m objects is denoted In the above de nition the term ordered77 means that the order in which the objects are arranged matters matters in the sense that di erent ordering count as di erent permutations In other words a permutation abc is not the same as bac since they are not in the same order A standard example of this are the so called committee problems which we will encounter shortly Exercise 33 Consider a collection of four objects u my a List all possible permutation of two objects from the collection of four b How many permutations are there in your list from a c Use the BCR to determine 42 Even in the relatively simple exercise above listing all possible permutations is te dious The permutation rule will help simplify this task Proposition 34 Permutations Rule The number of permutations ofr objects from a collection ofm objects is ml m m7 r Proof We will use the BCR to prove the claim The kth action is choosing one of the remaining in 7 k 1 objects remaining from the list of m where k 1 r In the notation of the BCR mkm7k1 k1r Then according to the BCR in would be the product of the mk7s ie m mm i 1 39 39 39 m 7 r 1 mltm 70 ngrr1jg7Tli1Tm1 Wilma which proves the claim D Exercise 35 Suppose 6 teams take part in an international soccer championship How many ways can the gold silver and bronze medals be distributed among the teams as sume there are no ties Exercise 36 You and two friends visit a local restaurant that features 10 different beverages How many ways can you and your thirsty friends each enjoy a beverage An important special case of the permutations rule is Proposition 37 Special Permutations Rule The rzumber of possible permutations of m objects among themselves is ml Proof 64 ml D Exercise 38 Five children will sit down randomly in a line of ve chairs How many possible arrangements of children are there What is the probability that the two friends Matt and Ben sit next to one another Exercise 39 Suppose 3 business 5 mathematics and 2 statistics books are arranged randomly on a shelf What is the probability that the books of the same subject are together Nearly all probability courses discuss the following problem called the Birthday Prob lem Not only does its solution require the counting techniques discussed above but the conclusion is quite surprising BIRTHDAY PROBLEM Assume that people7s birthdays are equally likely to occur among the 365 days of the year we are ignoring leap years and the fact that birth rates are not constant over the entire year What is the probability that at least two people in a group of size n will share the same birthday It is obvious that the probability changes with 71 why Let E be the event that at least two people out of 71 share the same birthday and let 0 The surprising result in this problem is that 0 can be relatively large for small 71 somewhat contrary to what one would expect Under the classical probability model 0 Now NQ is just the number of ways we could choose 71 birthdays sampling with replacement First NQ of ways to choose 71 b days w replacement 365 For the numerator we make use of the complementation rule That is of ways to choose 71 distinct b days 365 which is sampling without replacement Putting everything together we have 1 2 71 017PE 17177 17717 365 365 365 Using a computer program we can graph 0 versus 71 to see what happens see Figure 2 Note that 023 gt 05 and 060 m 1 9n l l l l l l l 0 10 20 30 40 50 60 n Fig 2 Plot of 9 vs n 4 Combinations A concept related to permutations is combinations7 which we de ne below De nition 41 A combination of r objects from a collection ofm objects is an unordered arrangement of r distinct objects from the m objects The number of possible combina tions of r objects that can be formed from a collection of m objects is denoted and read in choose r7 The de nition of a combination is similar to that of a permutation The important di erence is in the keyword unordered This will be discussed in more detail in the following section Exercise 42 Explain what is meant by unordered77 in the de nition of combination Exercise 43 A popular brewpub features a sampler special 10 off your choice of two out of the ve beer selections Write out all possible samplers that are available How many are there Exercise 44 Which is larger7 m or Just as they did for permutations7 the lazy mathematicians developed a rule for the number of combinations to simply calculation of Proposition 45 Combinations Rule The number ofpossible combinations ofr objects from a collection ofm is m 7 ml r T rlm 7 ry these numbers are referred to as binomial coef cients Exercise 46 Explain how this follows immediately from the Permutations Rule Before we get to the examples let7s rst discuss how to compute Most calculators have factorial functions However you may encounter problems when m is large It is often better to use the equivalent expression for m mltm71gtltme2gtltmer1gt r T 77177 In the next exercise you are asked to prove that can be de ned recursively This recursive relation how a computer nds can also be used to construct the diagram called Pascal s Triangle shown below Pascal7s Triangle Exercise 47 Prove the following identity for k S n ltki17l Example 48 Suppose three balls are to be placed randomly in three boxes What is the probability that exactly one box remains empty Let E be the said event There are 3 ways to choose the one box that remains empty 2 ways to choose the box that gets two balls and 2 ways to place the balls Thus NE 3 2 2 12 Finally the total number of ways to distribute the three balls is found as follows There are 3 boxes we could put the rst ball in 3 boxes we could put the second ball in and 3 boxes would could put the third ball in thus NQ 33 27 Therefore the probability that exactly one box remains empty is PEi igi 044 NQ 27 9 quot Exercise 49 A teacher plans to construct a 25 question exam from previous exams The previous exams consist of 50 true false questions and 80 multiple choice questions a How many exams can be constructed b How many exams can be constructed having exactly 13 true false questions Exercise 410 Suppose the statistics department consists of 15 full professors 10 asso ciate professors and 25 assistant professors If a committee of 6 is selected at random what is the probability that all the members of the committee are associate professors Exercise 411 In the de nition of it was mentioned that these numbers are often referred to as binomial coe cients and this exercise explains why From calculus you are certainly familiar with the Binomial Theorem if n 2 1 then V L a b Zemkakbn k a b E R k0 for some sequence of numbers cmk Prove that on 5 Combinations vs Permutations The key difference in the de nitions of permutations and combinations is whether or not ordering matters That is in the context of permutations the two collections 1102 and a2a1 would be considered different while in the context of combinations those collections would be the same Standard problems that illustrate the difference are committee problems If you are asked to choose a three person committee from a group of ten people this is a combi nation problem Alternatively if the committee consists of a president vice president and treasurer then the problem is a permutation problem In summary Permutation gt order matters Combination gt order does not matter 6 Partitions The nal class of counting problem we will consider is that of counting the number of ways a collection can be partitioned into distinct subgroups De nition 61 An ordered partition ofm objects into h distinct groups ofsizes 7711 771 is any division of the m objects into a combination of m objects constituting group i for i 12 h The number of such partitions possible is denoted by m m1m2gtquot39gtmk Exercise 62 Suppose you have six differently colored balls and three baskets ln how many ways can you put three balls in the rst basket two in the second and one in the third Proposition 63 Partitions Rule Let m1 771 be non negative integers whose sum is m The number of possible ordered partitions of m objects into h groups of size 7711 mk respectively is lt m ml 7 m1mk m1lmkl and these numbers are referred to as multinomial coef cients Exercise 64 Explain how the Combinations Rule is simply a special case of the Parti tions Rule Exercise 65 How many possible arrangements of the letters BOILERS are there This can be done using the BCR as well as the Partitions Rule Give both arguments Exercise 66 In the game of Bridge each of four players are dealt 13 cards from a 52 card deck What is the probability that one player gets all the spades Example 67 The Partition rule can also be used when some orderings are indistin guishable7 Suppose we have a handful of Skittles consisting of 5 red 3 orange and 2 yellow Skittles Note that we cannot tell the difference between those Skittles of the same color So given an arrangement such as RRYOYRORRO we could interchange the rst two reds and still as far as we can tell have the same arrangement We think about this problem as follows for each of the 10 arrangements there are 5 ways we can order the reds 3 ways we can order the oranges and 2 ways we can order the yellows within the arrangment of 10 Therefore the number of distin guishable arrangments is 10 i 10 5 32 532 39 7 More Practice Problems Counting problems can often be dif cult to solve because it is not immediately obvious which of BCR Permutations Combinations or Partitions Rule you should use In some cases you will need a combination of more than one of the rules It takes practice to be able to easily solve these problems Here are some to try Exercise 71 If ve girls and ve boys are randomly assigned to one of ten positions in a line what is the probability that all the girls are in a row and all the boys are in a row Exercise 72 In some state the license plate numbers consist of three distinct letters followed by three distinct digits 079 How many different license plates can be made Exercise 73 You are required to select a six character case sensitive password for an online account Each character may be an upper case letter a lower case letter or a digit from 079 How many different passwords can be created under each of the following restrictions a There are no restrictions b The rst character may not be a number c The last four characters must all be different d There must be at least one upper case and at least one lower case letter Exercise 74 A club has 11 members How many ways can a president7 Vice president and treasurer be chosen Exercise 75 A deck of cards labeled 1 2 n is shuf ed and the cards are dealt one at a time What is the probability that the tenth card dealt is the card labeled 10 Exercise 76 A fair coin is ipped ten times What is the probability you get exactly ve Heads Exercise 77 Briefcases often have a lock with a three digit combination Find the probability that a thief guesses the correct combination if a The three digits in the combination must be distinct and order does not matter b The three digits in the combination must be distinct and order does matter c The three digits in the combination need not be distinct and order does not matter d The three digits in the combination need not be distinct and order matters Exercise 78 If four die are rolled7 what is the probability they all show different faces Exercise 79 Prove the combinatorial identity 2 133 7 3 12 7 if using probabilistic reasoning and ii algebra and the Combinations Rule Exercise 710 Consider a game of bridge Find the probability of the following hands a Exactly two Aces b An 8 4 1 distribution c A 5 5 2 1 distribution d No Diamonds 8 Even More Practice Problems Warning Some of these problems are dif cult 1 In the game of Bridge7 each of four players are dealt 13 cards from a 52 card deck How many ways can this be done Hint use the Partitions rule What is the probability that one player gets all spades 2 Suppose 71 balls are distributed randomly in 71 boxes What is the probability that exactly one of the 71 boxes is empty Hint See Example 48 3 If Sam and Peter are among 71 men who are arranged at random in a line7 what is the probability that exactly k men are seated between them 4 lTaP will soon require we each change our passwords every 30 days Furthermore7 they recommend not using actual words because these are easier to hack into Many people have expressed concern that it will be dif cult to remember their password if it is always changing Here are the strategies of two hypothetical Purdue students a So that Tiffany can remember her password7 she decides to use a pattern She will always have six characters and only choose from lower case letters7 digits 0797 and the tilde symbol If her password always starts with a letter and has at least two numbers and the tilde7 how many passwords can she choose from b Reggie decides to use an eight character password The rst three letters are alway A7 U and G for his birth month but the case upper or lower will be chosen randomly The remaining ve characters are three lower case letters and two digits in 079 How many passwords can Reggie create 10

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.