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 willnotreceive 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 asubsetof 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