Textbook Notes (270,000)
US (100,000)
Berkeley (1,000)
COMPSCI (50)
Chapter 12

COMPSCI 70 Chapter Notes - Chapter 12: Product Rule, Anagrams, Coin Flipping

Department
Computer Science
Course Code
COMPSCI 70
Professor
Rao Satish
Chapter
12

This 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.
In-depth 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
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 d-degree 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
In-depth 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 -to-1
function from to (an -to-1 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 ordered-to-unordered 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 size-set 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