Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

7.1: Intro, Probability and Pigeonhole Principle

( \newcommand{\kernel}{\mathrm{null}\,}\)

Intro: What is Combinatorics?

Combinatorics studies the arrangements of objects according to some rules. The questions that can be asked include

  • Existence. Do the arrangements exist?
  • Classification. If the arrangements exist, how can we characterize and classify them?
  • Enumeration. How many arrangements are there?
  • Construction. Is there an algorithm for constructing all the arrangements?

Example 7.1.1

In how many ways can five people be seated at a round table? What if a certain pair of them refuses to sit next to one another? What if there are n people?

Example 7.1.2

A binary string is a sequence of digits, each of which being 0 or 1. Let an be the number of binary strings of length n that do not contain consecutive 1s. It is easy to check that a1=2, a2=3, and a3=5. What is the general formula for an?

Example 7.1.3

The complexity of an algorithm tells us how many operations it requires. By comparing the complexity of several algorithms for solving the same problem, we can determine which one is most efficient. Let bn be the number of operations required to solve a problem of size n. If it is known that bn=2bn1+3bn2,n3,

where b1=1 and b2=3, what is the general formula for bn?

Consider the number of integers from 2 to 5, inclusive.  You might think there  3 integers since 52=3.  However, if we include the 1st and last integer, our set is {2,3,4,5} and you can see there are 4 integers.

Theorem 7.1.1: Counting Natural Numbers

If m,nZ and mn then the number of integers from n to m is mn+1.

Example 7.1.4

How many four-digit codes exist from 1000 to 9999?

Solution

99991000+1=9000 so there are 9000 four-digit codes from 1000 to 9999

Probability

Definition: Sample Space

A sample space is the set of all possible outcomes.  For example, the sample space for rolling a die is:

123456

which is the set of the six possible results from tossing a die.

Definition: Event

An event is a subset of a sample space.  For example, an event for rolling two dice is: the sum is 9, i.e.

36634554

Definition: Probability for Equally Likely outcomes

If E is an event, then the probability of that event, P(E) is:

P(E)=the number of outcomes in Ethe total number of outcomes in the sample space.

For example, there are 36 outcomes for rolling two dice, so P(sum of 9)=436=19.

 

Since an event is a subset of the sample space, the largest number of elements in an event is the number of elements in the sample space.

Thus the maximum probability of an event is 1.  The smallest number of elements in an event is zero, so the minimum probability of an event is 0.

P(E1)=1 means event E1 will always happen.

P(E2)=0 means event E2 will never happen.

Example 7.1.1

Pick a card from a standard 52-card deck. What is the probability that the number of the card is

(a) a six

(b) a number less than 20

(c) a number greater than 15

Solution

(a) 113 

(b) 1

(c) 0

Pigeonhole Principle

The Pigeonhole Principle says that if you have more pigeons than pigeonholes, then at least one pigeonhole will get two pigeons.

Pigeonhole Principle.png

If you have a function from a finite set to a smaller finite set, then the function cannot be one-to-one; in other words, there must be at least two elements in the domain with the same image in the codomain.

More formally,

Theorem 7.1.2 Pigeonhole Principle

If f:XY where X and Y are finite sets with |X|>|Y|, then f is not one-to-one.

Example 7.1.5

Without looking, you pull socks out of a drawer that has just 5 blue socks and 5 white socks. How many do you need to pull to be certain you have two of the same color?

Solution

You could have two socks of different colors, but once you pull out three socks, there must be at least two of the same color.
The answer is three socks. 

Example 7.1.6

in a group of 30 people, each person picks a number from 1 to 10.  What is the minimum number of people needed to be sure you have two people with the same number?

Solution

11 

Summary and Review

  • This chapter is about combinatorics, which is a study of arrangements of objects.
  • We have a theorem to find the size of a set of consecutive integers.
  • The probability of a event is the # of ways it can happen divided by the total # of outcomes.
  • Probability is a number from 0 to 1, inclusive.
  • The Pigeonhole Principle says if you have more pigeons than pigeonholes, at least 2 pigeons must cuddle up.

Exercises 

exercise 7.1.1

A random number is picked from 80 to 600.

(a) How many numbers are there to pick?

(b) What is the probability of picking the number 220?

Answer

(a) 60080+1=521 so there are 521 numbers
(b) 1521

Exercise 7.1.2

Are you able to answer any of the 1st three examples in this section?

If so, tell your professor what you came up with.  If not, look back after you have done more work in this chapter

Exercise 7.1.3

In a group of 100 people, each person picks a number from 100 to 120.  What is the minimum number of people you need to be sure two of them have the same number?

Answer

22

Exercise 7.1.4

In a group of 20 people, each person has one pet that is a cat, a dog or a goat. What is the minimum number of people you need to be sure two of them have the same type of pet?

Exercise 7.1.5

How many cards do you need to pick from a standard 52-card deck to be sure to get a red card?

Answer

27, because if you pick all of the 26 black cards, the next one must be red.

Exercise 7.1.6

In a school of 600 students, do there have to be two students with the same birthday (month and day)? Why?

Exercise 7.1.7

How many integers do you need to pick to be sure that at least two of them have the same remainder after dividing by 5?

Answer

6, because there are 5 possible remainders: 0, 1, 2, 3, 4

Exercise 7.1.8

How many cards do you need to pick from a standard 52-card deck to be sure to get two cards of the same suit?

Exercise 7.1.9

If you pick one card from a standard 52-card deck, what is the probability it will be a diamond?

Answer

14

Exercise 7.1.10

If you pick one card from a standard 52-card deck, what is the probability it will be

(a) a two or three

(b) a two and a three

(c) a red card or a black card

Exercise 7.1.11

If you pick one card from a standard 52-card deck, what is the probability it will be

(a) an eight or a nine or a ten?

(b) an eight and a nine?

Answer

(a) 313
 

(b) 0


This page titled 7.1: Intro, Probability and Pigeonhole Principle is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Harris Kwong (OpenSUNY) .

Support Center

How can we help?