4
$\begingroup$

There are $n$ distinguishable students. In how many ways can they sign up to courses $A, B, C$ if each of the students can choose either $0$, $1$, $2$ or $3$ courses and also (*) none of the $7$ parts of Venn Diagram visualizing the problem are empty.

My solution:

I assumed that (*) is equivalent to simply having to subtract the number of possibilities where students didn't choose certain courses and I'll use that fact later in the solution.

Let's first count the total number of ways students can sign up to the courses. Let's consider a single student.

  1. If they choose to sign up to $0$ courses, they have $1$ possibility $=$ choosing $0$ courses.
  2. If they choose to sign up to $1$ course, they have $3$ posibilites $=$ $A$ or $B$ or $C$.
  3. If they choose to sign up to $2$ courses, they have $3$ possibilities $=$ not choosing $A$ or $B$ or $C$.
  4. If they choose to sign up to $3$ courses, they have $1$ possibility $=$ choosing $A$ and $B$ and $C$.

So there are $8$ options in total and since there are $n$ students, there are $8^n$ total possibilities.

Next step: we have to subtract the number of possibilities where students leave parts of the Venn Diagram empty. We're gonna use the inclusion-exclusion principle to calculate them. More precisely, we need to calculate $$|A'\cup B'\cup C'| = |A'| + |B'| + |C'| - |A'\cap B'| - |A'\cap C'| - |B'\cap C'| + |A'\cap B'\cap C'|$$ where $|A'\cup B'\cup C'|$ represents the total number of ways in which we can achieve an empty part in the Venn Diagramm and for example $|A'|$ is the total number of ways in which no student chose the course $A$.

Let's do something similar as in the beginning: what is the total number of ways $|A'|$ in which no student chose course $A$? Let's consider a single student.

  1. If they choose to sign up to $0$ courses, they have $1$ possibility.
  2. If they choose to sign up to $1$ course, they have $2$ posibilites $=$ choosing $B$ or $C$.
  3. If they choose to sign up to $2$ courses, they have $1$ possibility $=$ choosing $B$ and $C$.
  4. If they choose to sign up to $3$ courses, they have $0$ possibilities.

So in total, a single student has $4$ ways not to choose course $A$ and since there are $n$ students, there are $4^n$ ways to do so. This number is obviously the same for courses $B$ and $C$. So $|A'| = |B'| = |C'| = 4^n$.

Calculating the number of possibilities where no student chooses courses $A \cup B$ is very similar. The result I got is $2^n$ and $|A' \cup B'| = |A' \cup C'| = |B' \cup C'| = 2^n$

The number of ways in which every student can choose $0$ courses is just $1$.

Now, plugging in the numbers $|A'\cup B'\cup C'| = 3*4^n - 3*2^n + 1$, leaving the total answer equal to $$8^n - 3*4^n + 3*2^n - 1$$

I was told that my solution is far off. Any idea where I made a mistake?

EDIT: Alright, so to clarify there are $7$ Venn Diagram regions and students are distinguishable (I think it makes more sense after giving it some thought).

My alternate solution: Let's choose $7$ students first and place them into those $7$ Venn Diagram regions. Since they can be swapped around, let's multiply them by $7!$ to get $7!$ * $\binom{n}{7}$ total ways to place them into those $7$ regions.

We're left with $n-7$ students and from what I've counted in the first solution, it'd follow that there are $8^{n-7}$ ways for them to choose courses, leaving the final answer to be $$7! * \binom{n}{7} * 8^{n-7}$$

I've done it really fast and I'm not sure how correct it is, I'd appreciate any help from there.

$\endgroup$
6
  • 1
    $\begingroup$ Are the students indistinguishable? That is, if $n = 2$, do we distinguish Alice taking courses $A$ and $C$ and Bob taking courses $B$ and $C$ from Alice taking courses $B$ and $C$ and Bob taking courses $A$ and $C$? $\endgroup$
    – Brian Tung
    Feb 12 at 18:40
  • $\begingroup$ @BrianTung I assumed they aren't, however I think that it'd make more sense to consider them distinguishable and that's probably the reason why my answer is wrong. $\endgroup$ Feb 12 at 18:47
  • $\begingroup$ @BrianTung Not the outside, just the 7 inner regions. $\endgroup$ Feb 12 at 18:54
  • 1
    $\begingroup$ If students are distinguishable, then use PIE (on the 8 regions, not 3). If indistinguishable, then you have $ n \choose 7$ $\endgroup$
    – D S
    Feb 12 at 18:58
  • $\begingroup$ @DS: Yes that's my conclusion. Maybe write up your comment as an answer? $\endgroup$
    – Brian Tung
    Feb 12 at 19:00

2 Answers 2

4
$\begingroup$

Assuming indistinguishable students:
Then you're looking for integer solutions of $$x_1+x_2+ \ldots +x_8 = n$$where $x_i\ge 1$ for $1\le i\le7$ and $x_8\ge0$. So, we introduce a variable $y = x_8+1$ so that $$x_1+x_2+ \ldots +x_7+y = n+1$$By sticks and stones, this has $\binom{n}{7}$ solutions.


Assuming distinguishable students:
We use PIE. $8^n$ ways to place the students anyhow, $7^n$ where one is empty (we care about 7 such regions), $6^n$ where two are empty (we care about $\binom{7}{2}$ such pairs), $5^n$ where three are empty (we care about $\binom{7}{3}$ such triplets) and so on.
In the end, you will have $$\sum_{i=0}^7 (-1)^i\binom{7}{i}(8-i)^n$$

$\endgroup$
6
  • $\begingroup$ For $n = 7$, the sum gives $5040 = 7!$, but WA couldn't find a closed form for the general case. $\endgroup$
    – D S
    Feb 12 at 19:38
  • $\begingroup$ Do you think that your answer for the distinguishable case matching with my second answer for n = 7 is just a coincidence or could it be the general case solution after swapping some numbers? EDIT: Nevermind, after reading the other commenter I think my answer is just wrong. $\endgroup$ Feb 12 at 19:50
  • $\begingroup$ @neoxxx I wouldn't call it a coincidence per se. It's just the case where there are not many options due to constraints, so your answer matches $\endgroup$
    – D S
    Feb 12 at 19:57
  • $\begingroup$ "Stars and bars" has an unfortunate parallel meaning as the flag of the Confederacy, the pro-slavery faction in the US Civil War. Given that there are other common and catchy names, it's worth avoiding loaded phrases. (I summarized this in the comments on the edit but those are probably hard to find.) $\endgroup$ Feb 13 at 8:39
  • $\begingroup$ I didn't know that @GregMartin $\endgroup$
    – D S
    Feb 13 at 8:40
3
$\begingroup$

I found it difficult to follow through your solution. Not necessarily because it was wrong but because it was too complicated. It was too easy to miss something.

Here's something that could be among the problems leading to an incorrect answer.

It appears as if your solution is okay with the case where there is $1$ student attending each of the three courses but no student who is taking exactly $2$ courses (say, A and B only).

Remember, each region of the Venn diagram has to be non-empty.


Post OP's second solution

The problem with $\binom{n}{7} \cdot 7! \cdot 8^{n-7}$ is that it is over counting.

Consider this. In the first step when you place one student in each region, you place $S_1$ (student 1) in the region for "A only" and in the second step $S_2$ joins $S_1$. Lets call this arrangement 1.

Now in another arrangement, you place $S_2$ in "A only" in the first step and then $S_1$ voluntarily joins later. Let's call this arrangement 2.

If you think about it, everything else being constant, both arrangements are the same. But the solution counts them as $2$.

So, double counting.

$\endgroup$
6
  • 1
    $\begingroup$ I think we were supposed to assume there are $7$ regions in the Venn Diagram, not counting the universal set. I don't quite understand your solution yet, but I'm pretty sure the problem is not that hard after doing what you did, that is placing $7$ people in the region first and then proceeding. Gonna give it a try. $\endgroup$ Feb 12 at 18:50
  • $\begingroup$ I was thinking about that. In that case, we will make a small adjustment. It will be $\binom{n-1}{6}$. $\endgroup$
    – Haris
    Feb 12 at 18:52
  • $\begingroup$ Not necessarily double counting, $S_1$ could take up position $A$ in multiple comfigurations... $\endgroup$
    – D S
    Feb 12 at 19:31
  • $\begingroup$ Again, I think the answer would be $\binom{n}{7}$ in the indistinguishable case, see my answwer $\endgroup$
    – D S
    Feb 12 at 19:35
  • $\begingroup$ for example, when we have $n=8$, we can put $2$ in one region, $1$ in other regions (outer region is empty) (7 ways), and $1$ in all regions including the outer one (1 way). And $\binom{8}{7} = 8$ $\endgroup$
    – D S
    Feb 12 at 19:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .