Probability/Combinatorics

Question 1

combinations

Answer 1

• a subset of distinct elements
• order does not matter

​2 types

1. With repetition (w/ replacement)
   
   • (n + k - 1)!/k!(n-1)!
   • multisubset
   • n multichoose k
   • combination is unique based on number of repeats in final answer, without regard to order
2. Without repetition (w/o replacement)​​
   
   • nCk= n!/k!(n-k)!
   • basically permutation, but dividing out order (number of arrangements)
   • this is also the binomial coefficient

Question 2

permutations

Answer 2

• ordered subset of element in a set
• permutation of all n items (number of ways to arrange n items) is n!
• always more permutations than combinations
• arrange a perm

2 types

1. With repetition (w/ replacement)
   
   • n^k
   • k spots, n options for each spot
2. Without repetition (w/o replacement)
   
   • nPk = n!/(n-k)!
   • k-permutations of n

Question 3

counting principle

Answer 3

• if there are a ways to do one thing, and b ways to do another, there are a*b ways to do both

Question 4

probability

Answer 4

number of desired outcomes

total number of outcomes

Question 5

dependent events

Answer 5

• events A and B are dependent if the occurance of one effects the other

Question 6

independent events

Answer 6

• events A and B are independent if the occurance of one does not effect the other
• P(A | B) = P(A) and P(B | A) = P(B)
• if either P(A) == 0 or P(B) == 0, they are independent

Question 7

addition rule

Answer 7

P(A ∪ B) = P(A) + P(B) - P(A ∩ B)

-where-

P(A ∩ B) = 0 [if A and B are disjoint]

Question 8

product rule

Answer 8

If A and B are dependent:

• P(A ∩ B) = P(B) * P(A | B) = P(A) * P(B | A)

If A and B are independent:

• P(A ∩ B) = P(A) * P(B)

Question 9

general product rule

Answer 9

P(A₁ ∩ A₂ ∩ … ∩ A_n) =

P(A₁) * P(A₂ | A₁) * P(A₃ | A2 ∩ A₁) * … * P(A_n |A_n-1 ∩ A_n-2 … ∩ A₁)

• the probability of the intersection of all events is the probabiluty of the first, times the second given the first times the third given the second and the first time the nth given the intersection of all the previous ones

Question 10

bayes theorum

Answer 10

P(A | B) = P(A) * P(B | A)

P(B)

• just multipcation rule reordered

Question 11

law of total probability

Answer 11

P(B) = P(A ∩ B) + P(A’ ∩ B)

Question 12

arbitrary number of subsets

Answer 12

• generalization of the combinations rule, but with an arbitrary number of groups
• numerator is factorial of total group size
• denominator is the product of factorials of the individual group sizes you want to form
• all the k’s should equal n

n!/k₁!…k_r!

Question 13

distinguishable permutations

Answer 13

• permuting a set where elements repeat
• ex: permuting mississippi

Steps

1. permute n elements as normal (n!)
2. divide out the permutations of the repeating elements
   
   1. ex: 11!/2!*4!*4!

Question 14

set composition principle

Answer 14

• when using the multiplication rule (ie the counting principle) to enumerate distinct elements in a*b, a and b must be disjoint; if not, then you’re overcounting
• -or-*
• if you use the counting principle to generate a subset, you must be able to determine which item was derived in which step
• ex:
  
  • consider a 2-pair poker hand
  • you get back the hand JJKK5
  • you know the 5 had to come from the last step
  • but did the K’s come from the first step or the second step?