Chp 3 Notes: Combinatorics Flashcards
What is the outcome space?
the set of possible outcomes denoted by Ω
What are sets?
Unordered collections of elements whose elements cannot appear multiple times in the set.
How can sets be represented?
- by listing its elements within braces
* A = {1,2,3} - by specifying the precise conditions for an element to be in the set
* Z+= {x : x is a positive integer} - As a combination of sets
What are events?
Subsets of Ω (the outcome space) are called events
What is the complement of an event?
The complement of an event A is the set of outcomes that are in Ω but not in A. The complement of the set A is denoted Ac
What is a tuple?
- ex. (H,H,T)
- order matters and the same element can appear multiple times in a tuple, but not in a set
- cannot be expressed as products of individual sets
What is the size of a set?
- the number of elements in it
- denoted by | A |
- ex. | { H, T} | = 2, |∅| = 0
To see an example of this notation, suppose there is a group of n concert-goers, each of whom is selecting a band T-shirt. The available colors are red, yellow, and black. How many possible outcomes are there?
Suppose there are four children—Alice, Bill, Christie, and Doug—at an animal shelter, checking out the current pool of n dogs. Each child writes down the name of the dog he or she likes most. How many possible outcomes are there?
- a sampling with replacement problem
Suppose there are four children—Alice, Bill, Christie, and Doug—at an animal shelter, checking out the current pool of n dogs. Now suppose that these same children are actually picking out dogs. First Alice chooses a dog to adopt, then Bill chooses a dog to adopt, and so on. How many outcomes are there now?
In this situation, Alice has n choices, but Bill has only n−1 choices, Christie has n−2 choices, and Doug has n − 3 choices. So there are n(n − 1)(n − 2)(n − 3) possible outcomes.
- a sampling without replacement problem
- use permutation formula
How many ways are there to order (shuffle) a deck of 52 cards?
- each ordering is called a permutation
- Well, the result is a 52-tuple, drawn from a set of size 52, in which no card is repeated. Therefore, the number of permutations is 52 · 51 · 50 · · · 1, which is called 52 factorial and denoted as 52!. More generally, the number of permutations of n elements is n factorial or n!.
When do we use factorial?
when we want to know how many permutations (ways to order) a set
What is the permutation formula and when do we use it?
What is the combinatorial function? When do we use it?
- C( n, k) or n! / (k! (n-k)!)
- when order doesn’t matter because it removes the overcounting after counting tuples (edit from the permutation function)
- also when order is fixed (b/c it’s fixed, we shouldn’t overcount for different permutaitons)
How do we derive the solution to this question:
how many subsets of size k does a set of n elements have?
Snow White is off to pick strawberries and asks three of the dwarfs (chosen from the seven: Dopey, Grumpy, Doc, Happy, Bashful, Sneezy, Sleepy) to join her. How many possible groups are there?
how many strings in {0, 1} 10 contain exactly four 1s?
You walk into a candy store and notice that there are five types of candy. Your mother allows you to pick exactly three pieces of candy, of whichever type(s) you want. How many ways are there to do this?
