Week 5 - Advanced Counting Flashcards
d. The difference between a permutation and a combination?
d. The difference between a permutation and a combination is that in a permutation the set of objects which position (or order) is important.
Ordered partitions ? And the formula for when you have 5 items that need to have 3 go in bucket a, 2 go in bucket b and 1 go in bucket c
where a set S is broken up into different “unique” cells that when added up equal the cardinality of set S can equal to. I.e. Set s into [a1,a2,a3]
n!/(a1a2..ak)
n!/(3!2!1!)
Unordered partition? And the formula?
Where a set S is broken up into different similar cells and when added up equal to the cardinality of set S.
m = n!/(a1*a1*a2*a2) n = m/2!*2!
m being the ordered partition, and n being the unordered partition. (unordered is always smaller since 1,2,3 is the same as 3,2,1)
Whats the formula for a permutation with repetition?
n^r, where n is the number of things to choose from, and we choose r of them
Whats the formula for a permutation with no repetition?
n!/(n-r)!. Think of a race where position matters, but there can’t be any repetition.
ii. where n is the number of things to choose from, and we choose r of them
Whats the formula for a Combination with no repetition?
n!/(r!*(n-r)!) an example could be lotteries
Whats the formula for a combination with repetition?
C(n+r-1, r) = (n+r-1)!/[r!(n-r)!], =[( think of ice cream being scooped out
Where n is the number of things to choose from, and we choose r of them
How many ways are there to place k differently labeled balls at most one per box, into n labeled boxes?
Order matters, no repetition.
n!/(n-r)!
How many ways are there to place k identical (unlabeled) balls at most one per box, into n labeled boxes?
order doesn’t matter, no repetition
n!/(r!*(n-r)!)
How many ways are there to place k unlabeled balls, into n labeled boxes?
order doesn’t matter, repetition
C(n+r-1, r)
Whats the difference between a regular set and a multi set?
A multi-set can contain duplicate elements
vii. How many ways are there to rearrange the letters of a given word?
n! (if no repeats), if repeats then (n!/k!), where k! is repeat
When you have n objects of k types, with n(i) objects of type I, then the number of arrangements is:
C(n, n1) * C(n-n1, n2)
c. Number of ways to arrange a multi-set when we know the different types:
: n!/(n1!n2!n3!..nk!)
If A and B are not disjoint, we get the simplest form of the Inclusion-Exclusion Principle:
(2) |A∪B| = ?
= |A| + |B| - |A∩B|.
