Math 2320 Test 2: Solutions Whiteley, November 13, 8:30

Marks (20)      Calculators are permitted. However, always show your 
work.   Full marks may not be given for correct answers given without 
adequate explanation. 

(5)  1. Give a  combinatorial proof, using the subsets of a finite set,  for 
Pascal's Identity: 
                C(n+1,r)  =  C(n,r-1) + C(n,r). 
Note: a proof using algebra with factorials will  not  receive
significant marks.  The proof must be combinatorial - counting one
collection in two different ways.

Consider a set  of n+1 elements:  {1,2, ...  , n, n+1}.

The collection  S  of all subsets of size  r  has size  |S| = C(n+1,r).
We divide that set S  up into two disjoint subsets:
  T= collection of all subsets of size  r which contain  the element  n+1.
  U= collection of all subsets of size  r which do not contain the element n+1.
Now T consists of all subsets of  r-1 elements from  {1,... n}  which then 
have the element  n+1 added.  This collection has size  |T| = C(n,r-1).
   U  consists of all subsets of  r  elements from  {1,... n}  
   which has size  |U| = C(n,r).
This establishes a bijection between   S  and  T union U.
By the addition principle on disjoint sets:
     C(n+1,r)  = |S| =  |T|  +  |U|  = C(n,r-1)  +  C(n,r)


(8)  2.  A group plans to distribute $r$ trees to $s$ families living down one 
side of a street.  In each case, indicate the reasons you give the formula 
you end up with.

   a)  In how many ways can they distribute all the trees, if the trees are 
     distinct,  there are more families than trees and each family receives 
    at most one tree?

   For the first tree, there are  s  choices of family;
   For the second tree, there are  s-1  choices of family;
    ....
  For the last tree (number r), there are  s-r+1  choices of family.
By the multiplication principle, there are  s (s-1) ... (s-r+1)  ways to 
distribute the trees.

Alternatively, this is just a permutation of  r  families  from the  set of  s:
    P(s, r)  =  s! / (s-r)!

   b)  In how many ways can they distribute  all the trees, if the trees are 
identical, there are more families than trees and each family recives at 
most one tree?

    Distributing the trees is the same as selecting a  subset  
    of  r families who will each recieve one tree.   
    This is   C(s,r) =  s! / [r! (s-r)!].

    Alternatively, you could take the previous answer, and realize that any 
permutation of the order in which the families are chosen give the same 
net effect:
    By the equivalence principle, this is  P(s, r)/r!  =  s! / [(s-r)! r!]

   c)  In how many ways can they distribute all the trees, if the trees are
  distinct and a family can receive any number?   [The order a family 
  receives its trees does not matter.]

    This amounts to giving a permutation of size  r  of the families, 
     with repetition allowed.   
    This  gives  s  choices for the first tree, s  choices for the second tree, ....
    for a total of  s^r.  


   d)   In how many ways can they distribute all the trees, if the trees are
     identical and  a family can receive any number of trees?

    This is like distributing candies to kids.  We set up  s-1  dividers to 
    mark the boundary between the  s  families.   
    Consider strings of  r  identical trees and   s-1  identical dividers.  
     This has size   (s+r-1)!/[(s-1)! r!].
     Equivalently, for a string of  (s+r-1)  symbols with  r identical trees, 
     we just pick the  r  places for the trees:  C(s+r-1,r)  = (s+r-1)!/[(s-1)! r!]

   e)  In how many ways can they distribute  all the trees, if the trees are 
   identical, there are more trees than families and  each family must 
   receive at least one tree? 

   Set aside  s  trees (one per family) they will be distributed after, 
      in exactly one way  (i.e. we will multiply by 1).
   Now distribute the remaining  r-s  identical trees to the  s  families.
     As in  c)  this leaves   s-1  dividers and  r-s   trees, which can be 
     distribute  in  (r-1)!/[(s-1)! (r-s)!]  ways.


3.  Consider the set  A  of bit strings (strings of  0,1 ) defined by 
   the recursive definition:  
              (i)  00 \in  A;
             (ii)  if  \alpha \in A  then  \alpha 1 \in A  and   \alpha 10\in A;
	          if  \beta  is any bit string, then  \beta 00 \in A. 
 
(4)     a) Prove by induction that if   \gamma \in A  then  \gamma 
          contains two adjacent  0 's.

   We use induction on the length  of  \alpha.  
      Base case:  The shortest strings in A  have length  2.  
	The single such string is  00   which has two consecutive  0's.
      Assume that all strings in  A  of length  <= k  have two consecutive  0's.
      Consider a string  \gamma  of length  k+1 > 2.
	Since  \gamma is created within the recursive process,  in (ii),
     we have three cases:
        \gamma = \alpha 1,  with \alpha in  A (of length  k).  By the inductive
            assumption  \alpha in  A has  two consecutive  0's, so  
           \gamma= \alpha1  also has two consecutive  0's.
      \gamma = \alpha 10,  with \alpha in  A (of length  k-1).  
            By the inductive assumption  \alpha in  A has  
           two consecutive  0's, so  
          \gamma= \alpha10  also has two consecutive  0's.
     \gamma = \beta 00.  Clearly \gamma= \beta 00  has two 
        consecutive  0's.
   We conclude that all strings  \gamma in  A  of length  k+1 also have 
       two consecutive  0's.
   
   By the second principle of induction, all strings in  A  have two 
    consecutive  0's.


Alternatively, use the well ordered principle.  If the set of  strings in  A 
which  do not contain two  consecutive  0's is non-empty, then we can take 
the shortest such string \gamma  in  A  without two consecutive  0's.
   If  \gamma  has length <= 2, then \gamma in  A means  \gamma = 00.
        This is a contradiction.
   If  gamma has length  = k+1>2,  then  \gamma  in  a means one of three
   cases holds:
    \gamma = \alpha 1,  with \alpha in  A (of length  k).  
        By the assumption  that  \gamma was the shortest failure, 
        \alpha in  A has  two consecutive  0's.
        Therefore  \gamma= \alpha1  has two consecutive  0's - 
         a contradiction. 
    \gamma = \alpha 10,  with \alpha in  A (of length  k-1).  
            By the assumption that \gamma was the shortest failure, 
              \alpha in  A has  two consecutive  0's,   so  
              \gamma= \alpha10 also has two consecutive  0's.  Contradiciton.
     \gamma = \beta 00.  Clearly \gamma= \beta 00  
               has two consecutive  0's.
   We conclude that there is no shortest failure.  Therefore, all strings  
      \gamma in  A  of length  k+1 also have two consecutive  0's.


(3)     b):  Prove that if  \gamma  contains two adjacent  0's then 
              \gamma \in A.

     We also do this proof by induction on the length of  \gamma, 
       which has two consecutive  0's.

    No string of length  0  or  1  has two consecutive  0's.
    The only string of length  2  with  two consecutive  0's  is  00, 
        which is in  A  by clause  (i) of the definition.
    Assume that all strings of length  <= k  with two consecutive  0's
        are in the recusively defined set   A.
    Consider a string  \gamma which contains  two consecutive  0's.
        If  \gamma  = \beta 00, then \gamma in A  by clause (ii).
        Otherwise  \gamma =  \beta 10  or  \gamma = \beta 1.
            In each of these cases, since  \gamma has two consecutive  0's,
           we conclude that \beta must also have two consecutive  0's.
       However  \beta has length  <= k.  By the induction hypothesis,
           we know that  \beta in A.  Now by clause  (ii) of the recursive
           definition, we conclude that  \gamma is also in  A.

Back to 2320 Home Page