Exam Prep Notes on Combinations, Permutations, and Slots

Slots (Fundamental Counting Principle)

• Slots involve doing things one at a time in succession.
• Keywords:
  • Repeat (numbers can repeat).
  • Numbers can't repeat.
  • No replacement.
  • In succession.
  • One at a time.
• If any of these words appear in a problem, it indicates a slot problem.

Combinations

• Combinations generally involve multiple things at once.
• There should be no replacement or repetitions.
• Order doesn't matter.
• Example: Picking three people out of 35 to leave ten minutes early (order of selection doesn't matter).
• Committees: The word "committee" usually indicates a combination because committee members have equal status (no named positions).
• Formula: nCr = \frac{n!}{ (n-r)! * r!}
  • n is the total number of items.
  • r is the number of items being chosen.
• Combinations can never be done as slots.

Permutations

• In permutations, order matters.
• Example: Picking three people where one is president, one is vice president, and one is secretary (specific positions are named).
• Specific positions are involved.
• Examples: A race where coming in first, second, and third place matters.
• Formula: nPr = \frac{n!}{(n-r)!}
  • n is the total number of items.
  • r is the number of items being chosen.
• Permutations don't allow for repeats.
• Every permutation problem could be done as a slot problem, but not every slot problem can be done as a permutation.

Calculator Usage

• Use the nCr button for combinations and the nPr button for permutations.
• Input the total number (n) first, then the nCr or nPr button, then the number you are choosing (r), and finally press enter.
• r must be smaller than n; otherwise, you will get an error.
• Given the same values for n and r, permutations will always give a larger number than combinations because the combination formula divides by more.

Examples

• Example 1: Out of a group of 30 people, we need a committee of 5. How many ways can this be done?
  • This is a combination problem due to the word "committee."
  • Solution: 30C5
• Example 2: Out of a group of 30 people (18 girls and 12 boys), how many ways can we form a committee of 5 with exactly three girls?
  • Since we need three girls, we also need two boys to make a committee of 5.
  • Solution: (18C3) * (12C2)
  • The word "and" implies multiplication.
• Example 3: Using the same group, how many ways can we form a committee of 5 with four boys?
  • If we need four boys, we need one girl.
  • Solution: (12C4) * (18C1)
• Example 4: How many ways can we form a committee of 5 with five girls?
  • Solution: 18C5
  • Alternatively, (18C5) * (12C0), but since anything C0 is 1, it doesn't change the answer.
• Example 5: Out of 20 people, how many ways can we pick a president, vice president, and secretary?
  • This is a permutation problem because the positions are named, indicating order matters.
  • Solution: 20P3
  • Can also be done as a slot problem: 20 choices for president, 19 for vice president, and 18 for secretary. Result: 20 * 19 * 18.
• Example 6: How many ways can we pick a group of three men or three women from eight men and six women?
  • This is a combination problem because order doesn't matter.
  • Solution: (8C3) + (6C3)
  • The word "or" implies addition.

Additional Notes

• If a problem involves "at least," consider all possibilities that satisfy the condition and add them together.
• Example: From 40 people (25 men and 15 women), how many ways can we pick five people with at least three men?
  • Possibilities: 3 men and 2 women, 4 men and 1 woman, or 5 men.
  • Solution: (25C3 * 15C2) + (25C4 * 15C1) + (25C5)
• Special Cases: When calculating combinations, anything C1 is just the number itself (e.g., 15C1 = 15), and anything C0 is 1.

Slot problems with Restrictions

• Family of 10 taking an ooda. How many ways cane they be arranged in a row if ma and pa need to be in the middle?
  • Solution: Since the middle position matters and it can either be MA or PA the first position is multiplied by two and the rest of the 8 slots are arranged as 8 factorial.
  • 2 * 8!