MODULE 3 - COUNTING

•  Counting "enumerative combinatorics"

  • determine the number of objects
  • study of arrangements of objects
• Fundamental Counting Principle "counting Rule"

  • way to figure out the number of outcomes in a probability problem
  • purpose is to assign a numeric value to a group of objects
• Basic counting principles

  1. Product Rule
  2. Sum Rule
  3. Subtraction Rule (inclusion-exclusion for two sets)
  4. Division Rule
• Product Rule

  • Suppose that a procedure can be broken down into a sequence of two tasks. If there are n1 ways to do the first task and for each ofthese ways of doing the first task, there are n2 ways to do the second task, then there are n1n2 ways to do the procedure.
  • If one event can occur in m ways AND a second event can occur in n ways, the number of ways the two events can occur in sequence is then m · n.
• Sum Rule

  • If a task can be done either in one of n1 ways or in one of n2 ways, where none of the set of n1 ways is the same as any of the set of n2 ways,then there are n1 + n2 ways to do the task.
  • If an event can occur either in m ways OR in n ways (non-overlapping), the number of ways the event can occur is then m + n
• Subtraction Rule "Inclusion-Exclusion for Two Sets"

  • especially when it is used to count the number of elements in the union of two sets.
  • If a task can be done in either n1 ways or n2 ways, then the number of ways to do the task is n1 + n2 minus the number of ways to do the task that are common to the two different ways.
  • If an event can occur either in m ways OR in n ways (Overlapping), the number of ways the event can occur is then m + n decreased by the number of ways that the event can occur commonly to the two different ways.
• Division Rule

  • n ∕ d ways to do a task if it can be done using a procedure that can be carried out in n ways, and for every way w, exactly d of the n ways correspond to way w
•  Permutation

  • ordered arrangement of distinct objects
  • r-permutation is an ordered arrangement of r elements of a set
• Combination

  • unordered arrangement of elements of a set
  • r-combination is a subset of the set with r elements
• Combination Formula 


  C(n,r) = n!/r!(n-r)!

  n = the total number of elements in a set

  r = the number of selected objects

  ! – factorial; Factorial(noted as !) = a product of all positive integers less or equal to the number preceding the factorial sign.
• "r"


  the number of selected objects arranged in a certain order
• Permutation Formula


  P(n,r) = n!/(n-r)!