Combinatorics Flashcards
Combinatorics is
the number of ways of arranging things
When considering the number of possible combinations,
its often helpful to think of ordered slots in a line that we can fill
Number of ways of picking one card from each of 20 different packs =
52^20
Number of outcomes from the throw of five dice and the toss of five coins =
6^5 x 2^5
The number of ways of arranging n objects is
n!
0! =
1
(n+1)! =
(n+1)n!
Permutations: it gives us the number of ways of putting n items into k slots =
n!/(n-k)!
Choose function -
order does not matter
Number of ways of choosing k items from n =
n!/(n-k)!k!
Combinations -
order does not matter
Permutations -
order does matter
Choosing r things from n number of things, repetition allowed, order matters =
n^r
Repetition allowed, order matters
Choosing r things from n number of things, repetition not allowed, order matters =
n!/(n-r)!
Choosing r things from n number of things, repetition allowed, order doesn’t matter =
(r+n-1)!/r!(n-r)!
Choosing r things from n number of things, repetition not allowed, order doesn’t matter =
n!/(n-r)!r!
When considering the number of possible values in a sequence,
consider the number of possibilities in each character position, then multiply together.
Find the number of possible 4 digit sequences consisting of right and up movements
Theres two possibilities for each of the four positions so there is 2^4 possibiltiies
If there are n items and k slots then the maximum number of items in a slot is at least
n/k
6 numbers, 4 positions, no repeats:
6!/(6-4)! possible permutations
(y^2 + yx + 1)^n –> coefficient of x^3y^5
1 y^2, 3 xy, (n-4)’s ones : (n 1,3,n-4) = (n! / (n-4)! 3!) = 4(n, 4)
(a+b)^n
sum of powers of a and b = n therefore 2n
(y^2 + xy)^k total powers =
2*k = 2k
(y^2 + xy)^k : to get x^3 y^5
2k = 5+3 therefore k=4
3 xy terms 1 y^2 term : 4C1 –> (n, 4)
(n,r) =
(n, n-r)
AABBB
How many variations
5 choices 2 letters order does not matter no repeats 5C2