## 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

(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

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

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.
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 -
\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.