Date: Wed, 29 Oct 2003 12:40:55 -0600 (CST) - NOT BY WRIGHT 8 CLOCK!
   From: Mark Jacobson <jacobson@math-cs.cns.uni.edu>
     To: 810-080-01@uni.edu, 810-080-03@uni.edu
Subject: C(n, r), P(n, r) cars and trucks...

Hi discrete students,

    Reminder:  We have a QUIZ this Friday, October 31st.

    Regarding the 8 women and 11 men HW problem, here is yet another
              example problem.

    Suppose you have 4 cars and 3 trucks to park.

    You want to park them such that no two trucks are next to each other.

    How many ways can you park the cars?  4 factorial ways = 4*3*2*1 = 24

    PART AAA answer: 4 factorial = 4! = 24

    Consider the car positions as C and consider the underscore_ as
    a location where you could place a Truck, since we always must
    have at least one car separating any truck from another truck.

    Here is the situation:

    _C_C_C_C_

    _C_C_C_C_
    1 2 3 4 5   <---- There are 5 different locations where we could
                      place a truck.  There are three trucks to place.

    How many possible choices of THREE slots are there?

    _C_C_C C       123                    5!          5*4       20
    _C_C C_C       124      C(5, 3) = ----------- = -------- = ---- = 10
    _C_C C C_      125                (5-3)!(3!)       2!        2
    _C C_C_C       134
    _C C_C C_      135
    _C C C_C_      145
     C_C_C_C       234
     C_C_C C_      235
     C_C C_C_      245
     C C_C_C_      345

    TCTCTC C       123                    5!          5*4       20
    TCTC CTC       124      C(5, 3) = ----------- = -------- = ---- = 10
    TCTC C CT      125                (5-3)!(3!)       2!        2
    TC CTCTC       134
    TC CTC CT      135
    TC C C_CT      145
     CTCTCTC       234
     CTCTC CT      235
     CTC CTCT      245
     C CTCTCT      345

   PART BBB answer:  C(5, 3) = 10

   Finally, how many ways can the 3 trucks be placed for any one
   of the 10 different sets of positions?

   PART CCC answer:  3! = 3 factorial = 6 ways.

   Taking the product of AAA and BBB and CCC, we have:

    *****final answer is thus:    (4!) * C(5,2) * 3! = 24 * 10 * 6 = 1,440

       *** PART AAA answer:  4 factorial = 4! = 24

       *** PART BBB answer:  C(5, 2) = 10

       *** PART CCC answer:  3! = 3 factorial = 6 ways.

   The final answer is:    (4!) * C(5,3) * 3!

   You would not need to multiply it all the way out on an exam.

   Be sure to review your principle of inclusion and exclusion too.
   There will be a Venn diagram and Ghostbusters tools counting
   problem on the Friday quiz.

   Peter Venkman  = P
   Raymond Stantz = R
   Egon Spengler  = E

   There will also be something on binary relations and the
   reflexive, symmetric, transitive and antisymmetric properties
   that binary relations on sets either have or do not have.

   POSETs and Hasse diagrams could be on the quiz.

   Mark