$5$ people needs to preform $4$ different tasks in pairs.
each pair is allowed to preform more then 1 task (it's possible that 1 pair preforms all 4 tasks).
Find the number of all possible pairs exists to preform the tasks exists?
Find the number of all possible pairs exists to preform all tasks, as each person must preform at least 1 task. Use inclusion and exclusion.
My Attempt:
-
There are $5$ people and $4$ tasks, so for each task we have $\binom{5}{2}$ possibilities, in total, there are $\binom{5}{2}^4$ combinations.
-
Let the number of all pairs preforming all tasks be $A$, and let $B$ be the set of all pairs preforming the tasks as all $5$ people must be participating in at least one task.
that means that:
If $3$ people are preforming $2$ tasks, then $3$ people are preforming $1$ tasks
If $2$ people are preforming $3$ tasks, then $3$ people are preforming $1$ tasks
If $1$ person is preforming $4$ tasks, then $4$ people are preforming $1$ tasks.
I don't understand how to convert that into math.
For section (1) I did:
$x_1 + x_2 +x_3 +x_4 = 5$, therefore the number of all natural solutions for that is equals to $\binom{5}{2}^4$.
that does that means that for section (2) I'd have to find all natrual solutions for the equation, such that $\forall x \in {x_1, x_2, x_3, x_4}: x \neq 0$?
Best Answer
Let us number the tasks by $1,2,3,4$ and the persons by $1,2,3,4,5$.
In the first part we actually calculate the number of functions: $$\left\{ 1,2,3,4\right\} \to \left\{ \left\{ i,j\right\} \mid i,j\in\left\{ 1,2,3,4,5\right\} \text{ and }i\neq j\right\} $$
Denote this set of functions by $F$.
For $i=1,2,3,4,5$ let $F_{i}\subseteq F$ denote the subset of functions corresponding with person $i$ doing no task.
That means that: $$F_{i}=\left\{ f\in F\mid i\notin f\left(1\right)\cup f\left(2\right)\cup f\left(3\right)\cup f\left(4\right)\right\} $$
Then to be found is: $$\left|\bigcap_{i=1}^{5}F_{i}^{\complement}\right|=\left|F\right|-\left|\bigcup_{i=1}^{5}F_{i}\right|=\binom{5}{2}^{4}-\binom{5}{1}\left|F_{1}\right|+\binom{5}{2}\left|F_{1}\cap F_{2}\right|-\binom{5}{3}\left|F_{1}\cap F_{2}\cap F_{3}\right|$$
Here $F_1\cap F_2\cap F_3\cap F_4$ and $F_1\cap F_2\cap F_3\cap F_4\cap F_5$ are both empty because for a task you need at least $2$ person.
Can you take it from here?