Suppose there are 2n students in a class (numbered Student 1, Student 2, Student 2n), n...

  

Transcribed Image Text:

Suppose there are 2n students in a class (numbered Student 1, Student 2, Student 2n), n ≥ 1, and we want to form n groups, each with 2 students. Each student must be in exactly one group. (a) (4 pts) Suppose the ordering of the groups matter, and the order of the two students within each group does not matter. Find the number of ways to group the students in terms of n. Hint 1: This is the same as counting the number of length-n sequences containing sets of size 2 with distinct elements, i.e., sequences in the form ({a₁, b₁}, {a2, b₂},..., {an, bn}) where a₁,..., an, b₁,...,bn € {1,2,..., 2n} are distinct, representing that the first group is {a1, b₁}, the second group is {a2, b2}, etc. The ordering of the groups matter, e.g., ({1,3}, {2,4}) ({2,4}, {1,3}). But the order of the two students within each group does not matter, e.g., ({1,3}, {2,4}) = ({3, 1}, {4, 2}) since {1,3} = {3,1} and {2,4} = {4,2}. Hint 2: Use the multinomial coefficient. (b) (4 pts) Suppose the ordering of the groups matter, and the order of the two students within each group matters (maybe there is a group leader in each group, and a group with Students 1,2 where Student 1 is the group leader is considered different from a group with Students 1,2 where Student 2 is the group leader). Find the number of ways to group the students in terms of n. Hint: This is the same as counting the number of length-n quences containing pairs with distinct elements, i.e., sequences in the form ((a₁, b₁), (a2, b2),..., (an, bn)) where a₁,..., an, b₁,..., bn € {1,2,..., 2n} are distinct. We have ((1,3), (2, 4)) # ((2,4), (1,3)) and ((1,3), (2, 4)) ((3, 1), (4, 2)).. (c) (4 pts) Suppose the ordering of the groups does not matter, and the order of the two stu- dents within each group does not matter. Find the number of ways to group the students in terms of n. Hint 1: This is the same as counting the number of sets of size n containing sets of size 2 with distinct elements, i.e., sets in the form {{a₁, b₁}, {a2, b₂},..., {an, bn}} where a₁,..., an, b₁,..., bn € {1,2,..., 2n} are distinct. We have {{1,3}, {2,4}} = {{2,4}, {1,3}} and {{1,3}, {2,4}}={{3, 1}, {4,2}}. Hint 2: Partition the set of sequences in part (a), where each partition contains sequences corresponding to the same set. How large is each partition? (d) (4 pts) Suppose the ordering of the groups does not matter, and the order of the two stu- dents within each group matters. Find the number of ways to group the students in terms of n. Hint 1: This is the same as counting the number of sets of size n containing pairs with dis- tinct elements, i.e., sets in the form {(a₁, b₁), (a2, b₂),..., (an, bn)} where a₁,..., an, b₁,..., bn € {1,2,..., 2n} are distinct. We have {(1,3), (2,4)} = {(2,4), (1,3)} and {(1,3), (2,4)} # {(3, 1), (4,2)}. Hint 2: Partition the set of sequences in part (b), where each partition contains sequences corresponding to the same set. How large is each partition? (e) (4 pts) Suppose the ordering of the groups does not matter, and the order of the two students within each group does not matter. You select a way to group the students uniformly at random among the set of all ways to group the students. Find the probability that Student 1 is grouped with Student 2. Suppose there are 2n students in a class (numbered Student 1, Student 2, Student 2n), n ≥ 1, and we want to form n groups, each with 2 students. Each student must be in exactly one group. (a) (4 pts) Suppose the ordering of the groups matter, and the order of the two students within each group does not matter. Find the number of ways to group the students in terms of n. Hint 1: This is the same as counting the number of length-n sequences containing sets of size 2 with distinct elements, i.e., sequences in the form ({a₁, b₁}, {a2, b₂},..., {an, bn}) where a₁,..., an, b₁,...,bn € {1,2,..., 2n} are distinct, representing that the first group is {a1, b₁}, the second group is {a2, b2}, etc. The ordering of the groups matter, e.g., ({1,3}, {2,4}) ({2,4}, {1,3}). But the order of the two students within each group does not matter, e.g., ({1,3}, {2,4}) = ({3, 1}, {4, 2}) since {1,3} = {3,1} and {2,4} = {4,2}. Hint 2: Use the multinomial coefficient. (b) (4 pts) Suppose the ordering of the groups matter, and the order of the two students within each group matters (maybe there is a group leader in each group, and a group with Students 1,2 where Student 1 is the group leader is considered different from a group with Students 1,2 where Student 2 is the group leader). Find the number of ways to group the students in terms of n. Hint: This is the same as counting the number of length-n quences containing pairs with distinct elements, i.e., sequences in the form ((a₁, b₁), (a2, b2),..., (an, bn)) where a₁,..., an, b₁,..., bn € {1,2,..., 2n} are distinct. We have ((1,3), (2, 4)) # ((2,4), (1,3)) and ((1,3), (2, 4)) ((3, 1), (4, 2)).. (c) (4 pts) Suppose the ordering of the groups does not matter, and the order of the two stu- dents within each group does not matter. Find the number of ways to group the students in terms of n. Hint 1: This is the same as counting the number of sets of size n containing sets of size 2 with distinct elements, i.e., sets in the form {{a₁, b₁}, {a2, b₂},..., {an, bn}} where a₁,..., an, b₁,..., bn € {1,2,..., 2n} are distinct. We have {{1,3}, {2,4}} = {{2,4}, {1,3}} and {{1,3}, {2,4}}={{3, 1}, {4,2}}. Hint 2: Partition the set of sequences in part (a), where each partition contains sequences corresponding to the same set. How large is each partition? (d) (4 pts) Suppose the ordering of the groups does not matter, and the order of the two stu- dents within each group matters. Find the number of ways to group the students in terms of n. Hint 1: This is the same as counting the number of sets of size n containing pairs with dis- tinct elements, i.e., sets in the form {(a₁, b₁), (a2, b₂),..., (an, bn)} where a₁,..., an, b₁,..., bn € {1,2,..., 2n} are distinct. We have {(1,3), (2,4)} = {(2,4), (1,3)} and {(1,3), (2,4)} # {(3, 1), (4,2)}. Hint 2: Partition the set of sequences in part (b), where each partition contains sequences corresponding to the same set. How large is each partition? (e) (4 pts) Suppose the ordering of the groups does not matter, and the order of the two students within each group does not matter. You select a way to group the students uniformly at random among the set of all ways to group the students. Find the probability that Student 1 is grouped with Student 2.