Introduction to Counting

◼
  • Counting is an essential part of mathematics. We have briefly touched the topic when dealing with cardinalities of sets.
    • ◼
  • Although it may sound simple at first it is not, and there are different techniques and principles that will help us count different sets.
    • ◼
  • The most important part of counting is to correctly determine what are the things that we are counting.
    • ◼
  • For example, if we roll two dice, we might ask what is the number of possible outcomes. This is actually ambiguous as would getting a 2 and a 3 be considered different than getting a 3 and a 2 (for example if the dice were of different colors)?
    • ◼
  • Depending on the answer to the question above the result of the count would be either 36 or 21.
    • ◼
  • If perhaps we are only interested in the totals, then the answer would be 11.

    • The Addition Principle

    ◼
  • The addition principle states a basic and intuitive fact.
    • ◼
  • Suppose we have two disjoint sets A and B, such that |A| = m and |B|= n for some n,m∈. Then |A⋃B| = m+n.
    • ◼
  • In general if
    A
    1
    ,...,
    A
    n
    are pairwise disjoint sets (i.e.
    A
    i
    
    A
    j
    =∅
    for all i and j), and
    |
    A
    i
    |=
    m
    i
    ∈
    , then
    |
    A
    1
    ⋃...⋃
    A
    n
    |=
    n
    ∑
    i=1
    m
    i
    .
    • ◼
  • Example:
    • ◼
  • If we roll two dice in order. How many different ways are there to get 7 or 11?
    • ◼
  • We first find out the number of ways to get 7 (6 ways) and add that to the number of ways to get 11 (2 ways) to get the total (8 ways)
    • ◼
  • How many different outcomes do we have when rolling two dice in order?
    • ◼
  • We can tackle this problem by separating it into the number of outcomes for each of the values of the first dice (i.e. six outcomes for every value of the first roll). So the answer is 6+6+6+6+6+6 =36.
    • ◼
  • Note that this is only valid when the sets are disjoint. If the sets have elements in common we need more information.
    • ◼
  • Non-Example
    • ◼
  • In a regular deck there are 26 red cards and 12 face cards, but there are only 32 cards which are red or are face cards.

    • The Multiplication Principle

    ◼
  • In simple terms, the multiplication principle states that if A and B are sets such that |A|=m, and |B| = n, with m,n∈ , then |AB| = m n.
    • ◼
  • The way in which we apply the multiplication principle comes when we have events (that usually happen in sequence) and for each outcome of the first event we have the same number of outcomes for the second event.
    • ◼
  • Example:
    • ◼
  • What is the number of outcomes when rolling two dice in order?
    • ◼
  • We have 6 possibilities for the first die, and 6 possibilities for the second die. So 6x6=36.
    • ◼
  • Like the addition principle this extends to multiple events. If an outcome is determined by a sequence of events where the number of outcomes of each subsequent event is independent of the outcomes of the previous ones, then the number of overall possible outcomes is the product of the number of outcomes for each event.
    • ◼
  • Example:
    • ◼
  • What is the number of outcomes of rolling three dice in order?
    • ◼
  • 6x6x6 = 216
    • ◼
  • What is the number of outcomes of rolling three dice in order if no two dice roll the same number?
    • ◼
  • The first die has a possibility of rolling any of 6 values. The second die has the possibility of rolling any value except the one in the first roll, so 5. The third die has the possibility of rolling any value except those in the first two rolls, so 4. For a total of 6x5x4 = 120.

    • Permutations

    ◼
  • The previous example ties up with an important concept. That of permutations.
    • ◼
  • Imagine that you had a bag of n numbers and you were to randomly take k of them and line them up. How many possible ways are there to do this?
    • ◼
  • Well, we would use the multiplication principle. We have n possibilities for the first element. We have n-1 possibilities for the second. We have n-2 possibilities for the third, and so on until we have n-k+1 possibilities for the
    th
    k
    element. So we would have
    n(n-1)(n-2)...(n-k+1)
    possibilities. That is
    n!
    (n-k)!
    . We call this number the k-permutations of n elements and denote it by P(n,k).
    • ◼
  • There is a special case when k=n
    P(n,n)=
    n!
    (n-n)!
    =
    n!
    0!
    =n!
    which is the number of ways of ordering n elements. In this case we call this just the number of permutations of n elements, as opposed to “n-permutations of n elements” .
    • ◼
  • The above holds true because 0! = 1 which is a mathematical convention, much like
    0
    0
    =1
    .
    • ◼
  • Example:
    • ◼
  • In a class of 64 students how many ways are there to select a class president, a vice-president and a class secretary?
    • ◼
  • P(64,3) = 64*63*62=249984

    • Combinations

    ◼
  • Let us go back to the example with the three dice “What is the number of outcomes of rolling three dice in order if no two dice roll the same number?”
    • ◼
  • What if we were to not considering the order in which the dice were rolled? For example if we counted the outcome 6,5,4 and 5,6,4 as the same?
    • ◼
  • We would first have to consider how many times the same triple appears. In this case each triple appears 3! = 6 times. Why?
    • ◼
  • Knowing this then we would just simply obtain the result by dividing by 6, that is 120/6 = 20.
    • ◼
  • This idea can be generalized by thinking of the number of subsets of size k from a set of size n. As above we were thinking of the number of subsets of size 3 of a set of size 6.
    • ◼
  • In the general case we would have
    P(n,k)
    k!
    =
    n!
    k!(n-k)!
    . We sometimes write this number as C(n,k) but more commonly as
    
    n
    k
    
    , and we usually pronounce it as “n choose k”
    • ◼
  • Example:
    • ◼
  • How many ways can we choose two groups of two from a group of 4 people?
    
    4
    2
    
    =6

    • Binomial Coefficients

    ◼
  • Numbers of the form
    
    n
    k
    
    are often referred to as binomial coefficients. We will explain why shortly.
    • ◼
  • A binomial is an expression that is the sum of two different terms, such as x+y. When we expand the powers of a binomial
    n
    (x+y)
    we obtain a sum of terms
    c
    0
    n
    x
    +
    c
    1
    n-1
    x
    y+...+
    c
    k
    n-k
    x
    k
    y
    +...
    c
    n
    n
    y
    . The
    c
    i
    for i∈{0,1,...,n} are the binomial coefficients.
    • ◼
  • Consider
    n
    (x+y)
    =(x+y)(x+y)...(x+y)
    then the coefficient of
    n-k
    x
    k
    y
    is the number of times that we can choose k y terms out of the n multiplicands. Thus why we can conclude that
    c
    k
    =
    n
    k
    .
    • ◼
  • A few interesting properties come up:
    • ◼
  • 
    n
    0
    =1
    for all n∈
    • ◼
  • 
    n
    1
    
    = n for all n∈
    • ◼
  • 
    n
    k
    
    =
    
    n
    n-k
    
    for all n∈ and k<n.

    • Principle of Inclusion Exclusion

    ◼
  • We know form previous lessons that for arbitrary sets A, B we have |A⋃B| = |A|+|B|-|A⋂B|. This can be generalized to an arbitrary finite number of sets.
    • ◼
  • In general
    • ◼
  • So for example |A⋃B⋃C| = |A|+|B|+|C| - |A⋂B| - |B⋂C| - |C⋂A| + |A⋂B⋂C|