Question

2. A binary string s a finite sequence u = ala2 . . . an, where each ai įs either 0 or 1. In this case n is the length of the string v. The strings ai,aia2,...,ai...an-1,aan are all prefixes of v. On the set X of all binary strings consider the relations Ri and R2 defined as follows R, = {(u, u) | w and u have the same length } {(w, u) | w is a prefix of u } R2 (a) Prove that Ri is an equivalence relation. (b) Write down the equivalence classes of the strings 0, 01, and 111 c) Consider the set Y of all binary strings of length 2 or 3. The relation R2 on the set Y is a partial ordering. Draw a Hasse diagram of the partial order R2 on the set Y. Identify maximal and minimal elements of the poset . (a) How many ways are there to put 14 identical objects in 3 boxes with at least 8 objects in one box? (b) How many ways are there to put 14 identical objects in 3 boxes with no more than 7 objects in one box? (c) How many numbers between 0 and 999 have the sum of their digits equal to 20?

Answer 1

Consider the relations R, and R, on the set X of all binary strings R, (w,v) w and vhave the same lenght R,{(w, v)wis a prefix of v 2(a) Proof: If a relation is said to be equivalence relation, it must be reflexive, symmetric, and transitive. The relation R, = {(w,v)|w and vhave the same lenght Here, w and vare two binary strings of set X If the string ve X, then the string v is related to itself as length of v is equal to length v Therefore, the relation R, is reflexive If the strings w and v e X, then the strings w and v are related as the length of wis equal to v and the length of v is equal to w That is, length(w) = length(v) and length(v) 1 length(w). Hence, wR,v Therefore, the relation R, is symmetric. 1 If a E X,be X, and cE X, the strings a, b, and c related as, length(a) length(b) length(b) length(c) length(c) length(a) Hence, aR,c Hence, the relation R, is transitive Therefore, the relation R, is equivalence relation

2(b) If a relation is said to be equivalence relation, it must be reflexive, symmetric, and transitive. The equivalence class of a string a of set X is the set of all elements of X which are related to the string a The equivalence class of string 0 of length 1 is 0, 1 The equivalence class of string 01 of length 2 is (00, 01, 10, 11 The equivalence class of string 111 of length 3 is 000, 001, 010, 011, 100, 101, 110, 111 2(c) Let the set Y of all binary strings of length 2 or 3 The set Y of all binary strings of length 2 or 3 is 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111 The relation R, ={(w,v)|w is a prefix of v } 2 The relation R2 on the set Y is a partial ordering That is, if a relation is said to be partial ordering relation, it must be reflexive, antisymmetric, and transitive The relation R on the set Y is said to be antisymmetric if and only if, aRb and bRa then a b

Hasse Diagram of the partial order R2 on the set Y: The minimal elements of the poset is 00, 01, 10, 11 The maximal elements of the poset is 000, 001, 010, 011, 100, 101, 110, 111} 00 01 01 01 Minimal elements 000 00f 010 011 100 101 10 11Maximal elements

3(а) The number of ways to put 14 identical objects in 3 boxes with at least 8 objects in one box: Let one of the boxes is filled with 8 boxes Then, the remaining balls are 14-8 6 balls These 6 balls must be put in 3 boxes The number of ways to put the balls in one box is given as follows: number of balls+number of balls- C number of boxes- 6+3-1 8! 2!x (8- 2)! 8! 2!x 6! 8 x 7 - 28 2 The number of ways to put the balls in three boxes is 28x3-84 ways Therefore, the number of ways to put 14 identical objects in 3 boxes with at least 8 objects in one box is 84 ways

3(b) The number of ways to put 14 identical objects in 3 boxes with no more than 7 objects in one box The number of ways with no more than 7 objects in one box the total number of ways the number of ways which have at least 8 objects in a box The total number of ways to put the balls in the boxes is as follows: number of balls+number of balls-1, C. 'number of boxes-l 14+3-1, 6C2 16 16! 2!x (16- 2) 16! 2! x 14! 16 x15 - 120 2 The number of ways to put the balls in the boxes is 120 ways The number of ways to put 14 identical objects in 3 boxes with at least 8 objects in one box is 84 ways The number of ways with no more than 7 objects in one box 120-88 36 ways. Therefore, the number of ways with no more than 7 objects in one box is 36 ways

3(c) The total numbers between 0 and 999 have the sum of their digits equal to 20 is as follows: The maximum sum of two 1-digit numbers is 18 (9+9) Then, it requires three 1-digit numbers to get the sum 20 Let the three 1-digit numbers are a, b, and c Then, abc 20 Case 1: If one of the digits is 2, then the remaining two digits are 9. Then, the number of ways of 2,9,9 to get the sum 20 is (3!)/(2!) 3 ways Case 2: If one of the digits is 3, then the remaining two digits are 8 and 9. Then, the number of ways of 3,8,9 to get the sum 20 is (3!) 6 ways. Case 3: If one of the digits is 4, then the remaining two digits are 7 and 9. Then, the number of ways of 4,7,9 to get the sum 20 is (3!) 6 ways. If one of the digits is 4, then the remaining two digits are 8 and 8. Then, the number of ways of 4,8,8 to get the sum 20 is (3!)/(2!) 3 ways. So, total 6+3 9 ways Case 4: If one of the digits is 5, then the remaining two digits are 6 and 9. Then, the number of ways of 5,6,9 to get the sum 20 is (3!) 6 ways If one of the digits is 5, then the remaining two digits are 7 and 8. Then, the number of ways of 5,7,8 to get the sum 20 is (3!) 6 ways. So, total 6+3 12 ways. Case 5: If one of the digits is 6, then the remaining two digits are 5 and 9. Then, the number of ways of 6,5,9 to get the sum 20 is (3!) 6 ways. Then, the total number of ways is 3+6+9+12+6 36 ways. Therefore, the total numbers between 0 and 999 have the sum of their digits equal to 20 is 36 ways