I'm would like some help solving this combinatoric problem.
4 customers booked appointments at a dental clinic in a given week. Each appointment is on 1 of the 5 working days (some appointments may be arranged during the same day).
i) How many ways can one assign each of the four appointments to a day of the week?
Solution:
$\binom{4}{4} + \binom{4}{3} + \binom{4}{2} + \binom{4}{1} + \binom{4}{0} = 16$
ii) How many arrangements from (i) are such that no day has more than one appointment?
Solution:
$5 * [\binom{4}{1} + \binom{4}{0}] = 25$
iii) How many arrangements from (i) are such that no day has more than two appointment?
Solution:
$5 * [\binom{4}{2} + \binom{4}{1} + \binom{4}{0}] = 55$
iv) How many arrangements from (i) are such that there is at least one appointment on Monday?
Solution:
$5 * [\binom{3}{3} + \binom{3}{2} + \binom{3}{1} + \binom{3}{0}] = 40$
v) How many arrangements from (i) are such that there are at least one appointment on both Monday and Tuesday?
Solution:
$5 * [\binom{2}{2} + \binom{2}{1} + \binom{2}{0}] = 20$
vi) How many arrangements from (i) have exactly 3 days taken for appointments?
Solution:
$3 * (\binom{4}{4} + \binom{4}{3} + \binom{4}{2} + \binom{4}{1}) + (2 * \binom{4}{0}) = 47$
vii) Let ($x_1,x_2,x_3,x_4,x_5$) denote the workload profile, where $x_i$ is the number of appointments on day $i$. How many different workload profiles are there for 4 appointments?
viii) How many workload profiles from (vii) are such that no day has more than 2 appointments?
I'm not entirely sure how to complete (vii) and (viii) and would like to see if my approach for (i) to (vi) is correct. Any help would be greatly appreciated. Thanks!
Best Answer
You did the problems you attempted incorrectly since you have not accounted for the fact that it matters which customer is assigned to which appointment.
There are five choices for which day each of the four customers will have an appointment. Hence, there are $5^4$ ways to assign each of the four appointments to a day of the week.
The four customers must have appointments on four different days. Choose which four of the five days the customers will have appointments and arrange the four appointments on those four days, which can be done in $\binom{5}{4}4! = 5!$ ways.
Since \begin{align*} 4 & = 2 + 2\\ & = 2 + 1 + 1\\ & = 1 + 1 + 1 + 1 \end{align*} there are three possible distributions of appointments: two customers each on two different days, two customers on one day and one customer each on two other days, or one customer each on four of the days.
Two customers each on two different days: Choose which two of the five days the appointments will be scheduled. Choose which two of the four customers will have appointments on the first of those days. The other two customers must have appointments on the other selected day. Hence, there are $$\binom{5}{2}\binom{4}{2}$$ ways to assign two customers each to two different days of the week.
If we care about the order of the appointments, we would multiply by $2!$ for each of the two ways we could arrange the appointments within a day for each of the two days, giving $$\binom{5}{2}\binom{4}{2}2!2!$$ possible schedules.
Two customers on one day and one customer each on two other days: Choose which of the five days will have two appointments. Choose which two of the four customers will have appointments that day. Choose which two of the other four days will each have a single appointment. Choose which of the two remaining customers will receive an appointment on the earlier of those days. The other customer must have an appointment on the later of those days. Hence, there are $$\binom{5}{1}\binom{4}{2}\binom{4}{2}\binom{2}{1}$$ assignments of customers to days.
If we care about the order of appointments, we must multiply by the $2!$ orders in which the two customers who have an appointment on the same day could be scheduled, giving $$\binom{5}{1}\binom{4}{2}\binom{4}{2}\binom{2}{1}2!$$ such assignments.
One customer each on four days: As we saw above, we can assign the customers to have appointments on four different days in $5! = \binom{5}{4}4!$ ways.
Since these three cases are mutually exclusive and exhaustive, there are $$\binom{5}{2}\binom{4}{2} + \binom{5}{1}\binom{4}{2}\binom{4}{2} + 5!$$ ways to assign customers to days so that no more than two customers have an appointment on the same day.
If we take the order of the appointments into account, we obtain $$\binom{5}{2}\binom{4}{2}2!2! + \binom{5}{1}\binom{4}{2}\binom{4}{2}2! + 5!$$ possible schedules in which no day has more than two customers.
We subtract the number of ways of assigning appointments that exclude Monday from the total number of ways of assigning appointments. If Monday is excluded, there are four choices for each customer rather than five, so there are $4^4$ ways to assign appointments without scheduling at least one customer to an appointment on Monday. Since there are $5^4$ ways to assign days without restriction, there are $5^4 - 4^4$ ways to assign customers to days of a work week if at least one customer has an appointment on Monday.
We subtract the number of ways assigning appointments that do not include at least one customer on both Monday and Tuesday from the total number of appointments.
There are $4^4$ ways to schedule the appointments if no customer receives an appointment on Monday and $4^4$ ways to schedule the appointments if no customer receives an appointment on Tuesday.
However, if we subtract $2 \cdot 4^4$ from the total, we will have subtracted those assignments in which no appointments occur on Monday and no appointments occur on Tuesday twice, once for each way we could have excluded one of those two days from receiving an appointment. We only want to subtract those cases once, so we must add them back.
Since there are $3^4$ ways to assign the four customers to have appointments on the remaining three days, there are $$5^4 - \binom{2}{1}4^4 + 3^4$$ ways to assign the four customers to days of a work week so that at least one appointment occurs on both Monday and Tuesday.
Since there are four customers, the only way exactly three days can be taken for appointments is to assign exactly two of the customers to one day and one customer each to two of the other days. We showed above that this can be done in $$\binom{5}{1}\binom{4}{2}\binom{4}{2}\binom{2}{1}$$ ways if we only care about assigning customers to days and $$\binom{5}{1}\binom{4}{2}\binom{4}{2}\binom{2}{1}2!$$ ways if we also care about the order of appointments.
Since there are four customers, $$x_1 + x_2 + x_3 + x_4 + x_5 = 4 \tag{1}$$ which is an equation in the nonnegative integers. A particular solution of equation 1 corresponds to the placement of $5 - 1 = 4$ addition signs in a row of four ones. For instance, $$1 + + 1 1 + 1 +$$ corresponds to the solution $x_1 = 1$, $x_2 = 0$, $x_3 = 2$, $x_4 = 1$, $x_5 = 0$. The number of possible solutions is the number of ways we can place four addition signs in a row of four ones, which is $$\binom{4 + 5 - 1}{5 - 1} = \binom{8}{4}$$ since we must choose which four of the eight positions required for four ones and four addition signs will be filled with addition signs.
We must determine the number of nonnegative integer solutions of equation 1 subject to the restrictions that $x_i \leq 2$ for $1 \leq i \leq 5$. Since there are only four customers, at most one day could have more than two appointments since $2 \cdot 3 = 6 > 4$.
We saw above that equation 1 has $\binom{8}{4}$ solutions in the nonnegative integers. From these, we must subtract those solutions in which three or more appointments are assigned to the same day. There are five ways to choose a day with at least three appointments. Say it is day 1. Then $x_1' = x_1 - 3$ is a nonnegative integer. Substituting $x_1' + 3$ for $x_1$ in equation 1 yields \begin{align*} x_1' + 3 + x_2 + x_3 + x_4 + x_5 & = 4\\ x_1' + x_2 + x_3 + x_4 + x_5 & = 1 \end{align*} which is an equation in the nonnegative integers with five solutions. Hence, there are $$\binom{5}{1}\binom{1 + 5 - 1}{5 - 1} = \binom{5}{1}\binom{5}{1}$$ ways to place more than two appointments on the same day.
Hence, the number of ways of assigning the workload so that no day has more than two appointments is $$\binom{8}{4} - \binom{5}{1}\binom{5}{1}$$