Count Chocula thinks he has a different method to count partitions of the set [n
ID: 3142755 • Letter: C
Question
Count Chocula thinks he has a different method to count partitions of the set [n] into k undistinguishable parts where one part is of size n1, one is of size n2, and so on. For example, one such partition of [6] with n1 = 1, n2 = 2, n3 = 3 is {{1}, {3, 5}, {2, 4, 6}}.
6, Count Chocula thinks he has a different method to count partitions of the set into k undistinguishable parts where one part is of size ni, one is of size n2, and so on. For example, one such partition of [6] with = 1, n2 = 2, n3 = 3 is 11), 13,5), {2,4,6]) He reasons as follows: Choose the part that contains 1. There are (1) ways to do this. Next choose the part that contains the least element that wasn't in the first part. There are ( ways to do this. Next choose the part that contains the least element that was in neither of the first two parts. There are (- ways to do this. Continue until done choosing parts. Multiply each of these numbers together to obtain the answer. Show an example where Count Chocula's method gives the wrong answer. Why doesn't Count Chocula's method work, other than that it gives the wrong answers?Explanation / Answer
n = 6, n1 = 1, n2 = 2, n3 = 3
Count Chocula' s method
C (6-1,1-1) * C (6-1-1, 2-1) * C (6-1-2-1, 3-1)
= C (5,0) * C (4,1) * C(2,2)
= 1*4*1
= 4
real answer
C (6,1) * C (6-1, 2) * C (6-1-2, 3)
= 6*10*1
= 60
Count Chocula chooses (n1 - 1) from (n-1) in the first step, which means he has already put1 element into first bucket but has not counted it in no. of combinations.
Similary for second bucket, again 1 element has already been put into it without choosing it.