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.
Does order matter with permutations?
ABSOLUTELY.
Alternatively how can we note a permutation?
What is a more general formula of permutations and when is it used?
This occurs when you have n>r
this is used when you have more objects (n) and they are placed in a smaller number of containers (k)
example: horse races
How is the general permutation formula expressed?
Does order matter for the general permutation formula?
ABSOLUTELY.
How do you do permutation with repitition?
It is just the same as counting rule #2
nr
essentially whatever your sampling you are putting back each time to be sampled again and again for each event (container)
Are distinguishable permutations groupings?
Why?
Absolutely.
Because ORDER MATTERS.
What are indisnguishable permutations?
Combinations.
What is so IMPORTANT about combinations?
order DOES NOT MATTER
Which contains more possibilities, combinations or permutations?
permutations
Order matters and therefore duplicates such as
A1A2 does not equal A2A1
and therefore each counts as a unique combination.
If it was a combination then
A1A2 equals A2A1
So is combination a special type of grouping?
Yes, one where we are not concerned with the ordering of objects.
What is the combination formula and how is it noted?
With combinations is the number of objects selected i.e. taken the same as the objects left behind?
Yes.
How do you a combination with repititon?
What does this mean?
This means that objects can be repeated (and are either infinite in number or are replaced (put back) but the order of the objects DOES NOT MATTER.
What is an example of a combination with repetition?
Assume there are ten different types of donuts (n) on the menu and you want to purchase three (r) donuts; of course you could get all glazed if you wanted to.
How many different combinations of donuts could you purchase?
