Textbook Notes (270,000)
US (100,000)
Berkeley (1,000)
COMPSCI (50)
COMPSCI 70 (20)
Rao Satish (20)
Chapter 12
Department
Computer ScienceCourse Code
COMPSCI 70Professor
Rao SatishChapter
12This preview shows half of the first page. to view the full 2 pages of the document.
Use counting to find sizes of sample spaces, event spaces, sample point probabilities, etc.
○
See counting as a basis for probability (discrete and continuous probability)

counting  combinatorial analysis; counting the number of outcomes
Objects made by choosing from , then ,.… then , the number of objects is .
○
If an event is composed of different independent events, then we can multiply together the probabilities of the independent e vents.
○
Indepth description: If an object can be made by a succession of choices, where there are ways of making the 1st choice, and for every way of making the 1st choice there are ways of making the 2nd choise, and for every way of making the
1st and 2nd choice there are of making the 3rd choice, and so on up to the th choice, then the total number of distinct objects that can be made in this way is the product
○
Even if the first choice actually does affect the second choice, if the number of choices we have in the 2nd choice is not af fected, then we use the First Rule of Counting
▪
Ex. The number of 10 digits numbers without repeating a digit = 10! (the digit 1st picked affects the next digit that will be picked, but the number of digits we pick from does not change if the 1st digit we picked is different)
▪
We are talking about size, not the value of the element
▪
The current choice affects the set of choices that we will make later, but not the size of the set
▪
Order matters (no matter how many choices we can make in the 1st step, the number of choices we have in the 2nd step does not change/is not affected by the number of choices we have in the 1st step)
○
Ex. Picking 1 and then 2 is not the same as picking 2 and then 1 from the set
▪
Picking distinct elements from a set and we care about the order in which we picked the elements
○
Suppose we have independent events. Event 1 can be performed in ways, event 2 in ways, .… event in ways. Then the nuber of ways that these events cn be performed together is
○
The number of functions mapping to is
(
ways to choose for , ways to choose for , .… etc.)
▪
The number of polynomials of degree at most d mod p is (there are coefficients in a ddegree polynomial, and each has different values () it can be)
▪
Example of 1st Rule of Counting
○
First Rule of Counting: Product rule (make the product of choices at each step)
1)
If the order does not matter, then count the number of ways to arrange the situation with order and then divide by the number of orderings/sorted objects
○
Indepth description: Assume an object is made by succession of choices, and the order in which the choices made does not matter. Let be the set of ordered objects (the set of all possibile arrangements/subsets of elements considered the order
of the elements) and let be the set of unordered objects (the set of all possible groupings/subsets of elements, where groups with the same elements, no matter the order of the elemen ts, are considered the same group). If there exists to1
function from to (an to1 mapping) (is the number of ordered objects per unordered objects; the number of ordered objects that correspond to the same one unordered object)), then
(i.e. the number of unordered objects is the
number of ordered objects and divided by )
○
Used to count unordered sets (i.e. the order of the elements within the set does not matter)
○
Ex. is the same as and
▪
The ordered world is larger than the unordered world, because one unordered object can have multiple different orderings of its elements, each of which is one ordered object
○
places the ordered outcomes into bins corresponding to the unordered outcomes
○
Gives the number of length subsets from distinct elements
□
"n choose k":
▪
Picking distinct elements from a set of elements and not caring about the order in which they were picked, the number of elements in the range of the function is
▪
The number of ways of constructing a element subset from a set of items
○
The Second Rule of Counting uses the First Rule of Counting twice (once in the numerator, and the second time ofr the denominator), and then divides the two
○
Second Rule of Counting:
, where is the set of unordered objects, is the set of ordered objects, and is the number of ordered objects per unordered objects
2)
Rules of counting
Object = outcome

Size of ordered objects > size of unordered objects (when choosing the same number of elements from the same base number of elements)

Permutations regard when order matters (the order in which you put the numbers in matters)
○
is the number of ordered subsets of size from a set of size
▪
Derived from the First Rule of Counting
▪
The number of ordered objects/subsets (permutations) of size from a set of size :
○
is the size of each object and is the number of elements we get to choose from
▪
The number of possible ways/outcomes we can get from choosing elements from elements, where 2 outcomes are different is the order of their elements is different
▪
gives the first terms of , the factorial of
▪
The number of ordered objects of size from a set of size :
○
permutation  a way of rearranging elements in a set; an ordered subset/object

is the size of each object and is the number of elements we get to choose from
▪
The number of possible ways/outcomes we can get from choosing elements from elements, where outcomes of the same elements are all the same (no matter the order their elements are in)
▪
Each unordered object corresponds to ordered objects (i.e. ordered objects correspond/map to the same one unordered object)
▪
Theorem:
□
"n choose k":
▪
Gives the number of subsets of size within a larger set of size
▪
The number of unordered objects of size from a set of size :
○
Pascal's rule gives us
○
combinations  used when order doesn't matter (the order of selection does not matter)

Permutations (unordered) and combinations (ordered)
Ways to create a subset of from elements (number of ways to choose/arrange elements from elements)

Sampling summary chart
order matters
order does NOT matter
without replacement
with replacement
or
with replacement & order matters > with replacement & order doesn't matter > w/o replacement & order matters > w/o replacement & order doesn't matter

Ex. card dealing (one card cannot be dealt twice)
○
Use: permutation
(the first terms of )
▪
Sampling without replacement + order does matter:
▪
When order matters:
○
Use: combination
(a.k.a. the Second Rule of Counting)
▪
If a set contains multiple same elements, a subset that contains the same elements of another are considered 1 (the same) subset

Sampling without replacement + order does not matter:
▪
Each unordered object corresponds to ordered objects (i.e. ordered objects correspond/map to the same one unordered object)
▪
The number of correspondences to ordered objects that each unordered object has is uniform (the same number for all unordered objects)
▪
When order does not matter:
○
sampling WITHOUT replacement  an element that was picked cannot be picked again; no two rounds/trials can have the same outcome (cannot produce the same element)

Ex. coin tossing, rolling a die
○
Having choices at each trial, for trials → sequences
▪
Sampling with replacement + order does matter:
, but
▪
When order matters:
○
We can choose to place either the bars/dividers or the stars/balls among the possible positions

Use: Stars and Bars representation
, which is also
▪
Sampling with replacement + order does not matter:
, and
▪
The number of ordered objects corresponding to one unordered object can be different for different unordered objects

The orderedtounordered ratio is not uniform among all unordered objects

Ex. In a set of , the unordered object has only 1 ordered object that corresponds to it. has
ordered objects corresponding to it. has ordered objects corresponding to it.

Stars and Bars gives us ways to add up numbers to sum to , or "items from with replacement where ordered doesn't matter"

Why use stars and bars:
▪
bars (or bins)

represents the number of different possibilities for each of the elements
▪
stars (or balls)
▪
Putting 1 ball into one bins means that one of the elements in the final object is the element that the bin corresponds to the element chosen from the set of size
□
Say element , and so putting balls into bin is the same as picking from the sizeset number of times
□
Putting a ball into one of the bins is the same as picking that element from the set of size once
□
"Only one ball in each bin" equivalent to "without replacement" (we cannot pick the same element twice) (we cannot give a ball to the same bin more than once)
"5 balls into 10 bins" is equivalent to choosing/taking 5 elements/samples from 10 possible elements (possibilities) with replacement
Equivalent meanings
□
Interpreting balls and bins problems
▪
When order does not matter:
○
sampling WITH replacement  an element that was picked can be picked again in the next rounds; multiple rounds/trials can have the same outcome (can produce the same element)

Sampling with/out replacement
Second rule of counting
First rule of counting
Stars and bars (balls and bins)
12. Counting, Combinatorial Proofs
Monday, October 2, 2017
7:52 AM
CS70 Page 1
You're Reading a Preview
Unlock to view full version