Question

A teacher has 30 project titles to be assigned to 7 students. A project can be assigned to any non-negative number of students and each student can be assigned any non-negative number of projects. Find the number of ways of assigning project titles to students if a) there is no additional conditions, b) each student receives at least one project, c) each project is assigned to at least one student, d) each project is assigned to exactly one student, e) each project is assigned to at exactly one student and each student receives at least one project, f) each project is assigned to at least one student and each student receives at least one project, g) each project is assigned to exactly two students and each student receives at least one project, h) each project is assigned to at most 5 students.

Answer 1

Name the projects as P1, P2, ...., P30 and name the students as x1, x2, ..., x7

a) Under no restriction, each project can choose from the 7 students in all possible ways. That is, each project decides whether or not to be assigned to each student. First, we need to count for each project how many ways it has. Consider P1 - it has 2 ways to decide about x1, 2 ways to decide about x2, .... 2 ways to decide about x7. Since events happen in succession, we multiply the idividual ways, hence P1 has 2 × 2 × ... × 2 = 27 ways

b) We need to invoke the Principle of Inclusion and Exclusion. From total ways obtained above, we need to subtract the cases where exactly one student receives no project. One student is left out, so each project shall have 64 instead of 128 ways to be assigned.  

Similarly following the Inclusion Exclusion rule, the required number of ways can be written as

c) If each project is assigned to at least one student, then each projects has 128 - 1 = 127 ways, because we have to remove the empty set. Hence

d) Now the projects do not have so many options! The problem can be stated in form of an equation. Let student x1, x2, ... xn receive n1, n2, ... n7 number of projects, where each value of 'n' is non-negative. Then

This equation has the standard result

Hence, for this case with N = 30 and k = 7 we get

e) This builds upon d) just one step further, so that each value of n is at least 1. Again we have standard result for this

f) Here we combine the logic of b) and c) i.e. apply inclusion exclusion principle in terms of assigning at least one project to each student, and remove the empty set in terms of assigning each project to at least one student. That is, we start from total ways = 12730. Then we remove the cases when no project is assigned to exactly one student, so ech project has 26 - 1 = 63 ways. Thus,

g) This build upon e) further, so that now each project is assigned to 2 students. This can be treated as simply as having to assign 60 projects, because name of the project does not matter at all. So with total 60 assignments with each value at least 1, we get

h) This one should be right down the alley by now. No of ways for each project is total ways i..e 27 minus the ways if the project is assigned to 6 or 7 students