Homework 1: Combinatorial Problems

11/19/23, 11:33 PM HW01-Nyi Nyi Moe Htet Student: Nyi Nyi Moe Htet Date: 11/19/23 Instructor: Xiaolong Han Course: CSUN_MATH340_HAN (1) Assignment: HW01 1. Two experiments are to be performed. The first can result in any one of m possible outcomes. If the first experiment results in outcome​i, then the second experiment can result in any of ni possible​outcomes, i = ​1, ​2, ..., m. What is the number of possible outcomes of the two​experiments? Choose the correct answer below. m A. ∑ ni i=1 B. n m C. n × m n D. ∑ ni i=1 2. In how many ways can r objects be selected from a set of n objects if the order of selection is considered​relevant? The number of ways is 3. There are n n! (n − r)! . different linear arrangements of n balls of which r are black and n − r are white. Give a combinatorial explanation of this r fact. Each arrangement is determined by the choice of the r positions where the black balls are situated. 4. Determine the number of vectors x1 , ..., xn ​, such that each xi is either 0 or​1, and the following inequality is true. n ∑ xi ≥ k i=1 There are n j n different vectors whose sum is j. ​Hence, there are https://tdx.acs.pearsonprd.tech/api/v1/print/highered ∑ j=k n j vectors that meet the criterion. 1/6 11/19/23, 11:33 PM HW01-Nyi Nyi Moe Htet 5. Prove that the following equation is true.​Hint: Consider a group of n men and m women. How many groups of size r are​possible? n+m = r n m 0 r + n m 1 r−1 + ... + n m r 0 Consider a group of n men and m women. n+m There are groups of size r. r There are n m i r−i groups of size r that consist of i men and ​(r − ​i) women. Rewrite the expression given in the problem statement by using the information from the previous steps. Choose the correct equation below. i n+m A. = r r=0 i n+m B. = r n r m−i i n m i r−i r = r ∑ i=0 r n+m D. ∑ r=0 n+m C. ∑ = r ∑ i=0 n r m−i i n m i r−i 6. n+m For a group of n men and m women, there are groups of size r and r n m i r−i groups of size r that consist of i men and r − i women. Additionally, the following equation is true. r n+m = r ∑ i=0 n m i r−i Use this information to prove that 2n n n = ∑ i=0 = 2n n n m 0 r n = ∑ k=0 n n i n−i + n k n m 1 r−1 + ... + n m r 0 2 . n Which of the following shows that the right side of the previous equation simplifies to ∑ k=0 A. n n = r n r−n 2 C. (n − r) 2 = ​, for r ≥ n n B. r n r 2 ​, for r ≤ n https://tdx.acs.pearsonprd.tech/api/v1/print/highered D. 2 n r 2 = = n r n n−r n k 2 ​? 2 ​, for r ≤ n ​, for r ≤ n 2/6 11/19/23, 11:33 PM HW01-Nyi Nyi Moe Htet 7. From a group of n​people, suppose that we want to choose a committee of​k, k ≤ ​n, one of whom is to be designated as chairperson. Complete parts (a) through​(d). n ​(a) By focusing first on the choice of committee and then on the choice of the​chair, argue that there are For the selection of the​committee, n k ​selection(s) is(are) being made from a group of possible outcomes. For the selection of the​chair, k k ​people, so there are k k k possible choices. n ​people, so there are ​selection(s) is(are) being made from a group of 1 possible outcomes. These two values are then multiplied together. ​(b) By focusing first on the choice of the nonchair committee members and then on the choice of the​chair, argue that there are n (n − k + 1) possible choices. k−1 For the selection of the nonchair committee​members, people, so there are group of n−k+1 n k−1 k−1 ​selection(s) is(are) being made from a group of possible outcomes. For the selection of the​chair, ​people, so there are 1 n ​ ​selection(s) is(are) being made from a n − k + 1 possible outcomes. These two values are then multiplied together. ​(c) By focusing first on the choice of the chair and then on the choice of the other committee​members, argue that there are n n−1 k−1 possible choices. For the selection of the​chair, n 1 ​selection(s) is(are) being made from a group of possible outcomes. For the selection of the other committee​members, group of n ​(d) Verify that k n = ( n − k + 1) k n k ( n − k + 1) ​people, so there are n−1 k n k−1 n−1 k−1 = = = n =n k−1 kn! n−k !k! !(k − 1)! n(n − 1)! n−k !(k − 1)! https://tdx.acs.pearsonprd.tech/api/v1/print/highered n−1 k−1 ​people, so there are ​selection(s) is(are) being made from a possible outcomes. These two values are then multiplied together. k−1 is true by using the factorial definition of m r . n! = (n − k + 1)n! n−k+1 n−1 k−1 n n−k = = !(k − 1)! n! n−k !(k − 1)! n! n−k !(k − 1)! 3/6 11/19/23, 11:33 PM HW01-Nyi Nyi Moe Htet 8. Show​that, for n > ​0, the following equation is true.​Hint: Use the binomial theorem. n ∑ ( − 1) i n =0 i i=0 ​First, identify the binomial theorem. Choose the correct equation below. n n A. (x + y) = ∑ k=0 n n B. (x + y) = ∑ k=0 n n C. (x + y) = ∑ k=0 n n D. (x + y) = ∑ k=0 n k n x y k n k n−k x y k n+1 k n+1 k k n x y k n−k x y Letting x = − ​1, identify the value of y that can be substituted into the binomial theorem.​Then, replace the k shown in the theorem with the i in the given equation and simplify the result. −1+ 1 n n = ∑ k=0 n ( − 1) k 1 k n−k n = ∑ i=0 n ( − 1) i = 0 i ​(Simplify your​answers.) 9. Present a combinatorial explanation of why n r = n r,n − r . Choose the correct answer below. A. A choice of r elements from a set of n elements is equivalent to breaking these elements into two​subsets, one of size r​(equal to the elements​selected) and the other of size n − r ​(equal to the elements not​selected). B. A choice of r elements from a set of n elements is equivalent to thinking about these elements as three different​sets, one of size n − r ​(equal to the elements​selected), one of size n​(the total number of​elements), and the final of size r​(equal to the elements not​selected). C. A choice of r elements from a set of n elements is equivalent to breaking these elements into two​subsets, one of size n − r ​(equal to the elements​selected) and the other of size n​(equal to the elements not​selected). D. A choice of r elements from a set of n elements is equivalent to thinking about these elements as three different​sets, one of size r​(equal to the elements​selected), one of size n​(the total number of​elements), and the final of size n − r ​(equal to the elements not​selected). https://tdx.acs.pearsonprd.tech/api/v1/print/highered 4/6 11/19/23, 11:33 PM HW01-Nyi Nyi Moe Htet 10. Argue that there are exactly r n−1 k n−r+k solutions of the following equation for which exactly k of the xi are equal to 0. x1 + x2 + ... + xr = n r There are to k choices of the n k ​x's equal to 0. Given​this, the other r−k of the​x's must be positive and sum . n−1 ​Thus, there are r−k−1 distinct positive​integer-valued vectors x1 ,x2 ,...,xr − k satisfying the equation x1 + x2 + ... + xr − k = n​, where xi > 0 and i = ​1, ​..., r − k. Use the information from the previous steps to identify the equation from which the desired result follows. Choose the correct answer below. A. B. C. D. n r−n−1 n−1 r−k−1 n r−k−1 n−1 r−n−1 = = = = n−1 n−r+k n−1 n−r+k n−1 n−r+k n−1 n−r+k 11. Consider a function f x1 ,...,xn of n variables. How many different partial derivatives of order r does f​possess? Assume all partial derivatives exist and are continuous on the domain of f. Choose the correct answer below. A. B. C. D. n+r n n+r−1 n−1 n n−r n r−1 https://tdx.acs.pearsonprd.tech/api/v1/print/highered 5/6 11/19/23, 11:33 PM HW01-Nyi Nyi Moe Htet 12. Determine the number of vectors x1 ,...,xn such that each xi is a nonnegative integer and the following inequality is true. n ∑ xi ≤ k i=1 Choose the correct answer below. k A. ∑ j=0 n B. ∑ j=k k C. ∑ j=0 n D. ∑ j=k j+n−1 j j+n−1 j j+n+1 j j+n+1 j https://tdx.acs.pearsonprd.tech/api/v1/print/highered 6/6