Combinatorics Flashcards
What does enumerating possibilities mean?
It means to determine how many possible outcomes can occur.
What are 3 components for the general framework for enumerating possibilities?
- Grouping 2. Permutation 3. Combination
What is combinatorics?
The method for determining the number of ways something can occur.
(the branch of math dealting with the study of finite or discrete objects.)
Why study combinatorics in psychology?
- Experimental design
- Probability theory – know the numbers of events for various outcomes to compute probabilities.
What is a probability?
The ratio (proportion of a specific event can occur divided by the total number of event occurrences.)
In other words what is a probability?
The total number of possible events (given some constraint–reference set–) out of the total number of events that are possible.
In order to compute a probability what do we need to do?
How is this done?
We need to figure out how many outcomes are possible.
Through enumeration i.e. counting
grouping
permutations
combinations
What is coutning rule 1?
n(n‐1)(n‐2)(n‐3)…1
which can be written as:
n!
so…
n(n‐1)(n‐2)(n‐3)…1 = n!
Where n = the number of objects that need to be arranged.
What does the first counting rule do?
IT tells us the NUMBER OF WAYS objects can be arranged in ORDER.
ORDER MATTERS.
EACH OBJECT IS COUNTED.
If ORDER MATTERS then which counting rule do you use?
How is it expressed?
Counting rule #1
n!
For which counting rule are items removed?
The first counting rule.
That is why they decrease each factor.
i.e. n(n-1)(n-2) etc until you reach 1
Which counting rule do you use if an item is not removed?
Counting rule #2
Does ORDER MATTER for counting rule #2?
What is a simple example of counting rule #2?
How is expressed?
YES.
A six-sided die is rolled 3 times how many possible outcomes are there?
6*6*6
Expressed as kn
k= the number of categories of events
What is counting rule #3 and how is different from counting rule #2?
Counting rule #3 is a generalization of #2 and it basically states that every k may have a different number of possible dimensions (k).
In counting rule #2 the number of dimensions remain the same.
Does ORDER MATTER for counting rule #3?
ABSOLUTELY.
Are items removed from the set for counting rule #3?
No. Each trial (k) has one event that occurs and one item is removed and then one moves onto the next trial (k)– that contains different dimensions.
What is a general framework for enumerating possibilities?
n (objects from a total pool)
r (a subset of n that is smaller and defined by some characteristic) r<=n
we place the objects into containers
What are some characteristics of containers (k)?
The can be considered invidual trials
k containers can contain a single object or multiple objects
k containers can be eitehr distinguishable i.e. labled or indistinguishable–the same
What are the three different types of counting problems?
And what are all of these types trying to do?
enumerate possibiltiies
grouping
permutation
combination
What are the unique aspects of grouping?
All objects are selected. (r=n)
all objects are mutually distinguishable – i.e. different like race horses finishing a race or ingredients on a sandwhich
all objects are assigned to specific containers (trials) (k)
such that all containers contain objects (k>0)
Does ORDER MATTER for grouping formulas?
ABSOLUTELY
What is the general grouping formula?
Otherwise stated:
Counting rule #1
divided by the factoring of each sub group (r)
(each small r1 r2 rk) is a seperate container (trial)
Why is a permutation considered a special type of grouping?
This is where:
n=r=k
each object goes into one and only one labled container
this equals counting rule #1
n!
Are objects replaced with permutations?
No way.
That is why they decrease in number similar to counting rule #1.
