0
$\begingroup$

With both of the parents working, Thomas, Stuart, and Craig must handle 8 weekly chores among themselves.

(a) In how many ways can they divide up the work so that everyone is responsible for at least one chore?

(b) In how many ways the chores be assigned if Thomas, as the eldest, must at least mow the lawn and clean the bathroom (two of the eight weekly chores) and no one is allowed to be idle?

For part a)

I assume that we want to find a surjective functions such that a function that goes from m to n.

In part A) m = 8 (The weekly Chores) and n = 3(the number of people)

Let S(m,n)

So Probably we should have S(8,3)

But for part b)

The idling part confused me a little bit. Like there are 2 cases such that,

Case 1: Thomas has at most 2 chores and no more

Case 2: Thomas has 2 chores and more ( Thomas has at least 2 chores)

So I believe that the solution is like Case 1 + Case 2 : S(6,2) + S(6,3)

But in this case, is that mean no one idling ? Or do we have to assign chores them ? Like, S(4,2) we left with 4 because we assigned fixed 2 jobs to 2 people so that they wont be idle. Similirlay S(4,3)

S(4,2) + S(4,3) or S(6,2) + S(6,3) Which one is correct for the part b ?

$\endgroup$
  • $\begingroup$ Can you please add the definition of $T(x,y)$ to your post? And while you're at it, please also use MathJax $\endgroup$ – Ertxiem Apr 18 at 18:51
  • $\begingroup$ Thank you for your reply, I edited definition of S but I dont think mathjax is neccessary for this question.(T has been replaced by beter notation that fits Stirling Numbers which is S(m,n) But i will edit in MathJax format asap. $\endgroup$ – Scott Apr 18 at 19:57
2
$\begingroup$

Your intuition is right.

Using the Stirling numbers of the second kind, part a) is indeed $S(8,3) = 966$ corresponding to the non-empty partitions of $8$ elements through $3$ sets.

Part b) is $S(6,3) + S(6,2) = 90 + 31 = 121$, corresponding to dividing the remaining $6$ tasks through the $3$ brothers with Thomas having at least $3$ tasks plus the case where the $6$ remaining tasks are divided among Stuart and Craig, i.e., Thomas will only have to mow the lawn and to clean the bathroom.

So, by using the Stirling numbers of the second kind, it means that everyone will have at least one task, hence, none of the $3$ brothers will idle while the others work.

Note that this approach assumes that it doesn't matter who gets each set of tasks. See more on the edit below.


I initially thought about a second approach, but it gives different results and I not being able to see the problem.

If you want to compute it directly instead of using the Stirling numbers, for part a) we have the following: $$ \sum_{t=1}^{6} \sum_{s=1}^{7-t} \sum_{c=1}^{8-t-s} \frac{8!}{t! \cdot s! \cdot c!} = 5796 $$ where $t$, $s$ and $c$ are the number of tasks assigned to Thomas, Stuart and Craig. The fraction represents the number of ordered sequences with $8$ symbols repeating "T" $t$ times, "S" $s$ times and "C" $c$ times. So, if we organize the tasks in a given order, if the letter "T" is in first position, it means that the first task is attributed to Thomas.

And for part b), using a similar notation, we have: $$ \sum_{t=0}^{4} \sum_{s=1}^{5-t} \sum_{c=1}^{6-t-s} \frac{6!}{t! \cdot s! \cdot c!} = 602 $$ note that Thomas already has 2 tasks and may end up with 2 to 6 tasks in the end.


Edit:

Mike Earnest commented that the different results in the approaches is linked to considering that it does not matter who gets the tasks, only which set is being distributed (in the first case); or considering that it matters who gets the tasks (in the second approach). The results coincide if we multiply the number of permutations among the brothers with the corresponding Stirling number (previously I had a typo in my formula and I wrote the wrong result in the second approach for case b) ).

Therefore, we can obtain the results in the second part using Stirling numbers with the formulas:

Part a) $$ 3! \cdot S(8,3) = 6 \times 966 = 5796 $$

Part b) $$ 3! \cdot S(6,3) + 2! \cdot S(6,2) = 6 \times 90 + 2 \times 31 = 602 $$

$\endgroup$
  • $\begingroup$ Well, thank you for your answer. But the results being different, confuses me a lot. How could they be different overall we are doing the same calculation? I hope someone can answer this. $\endgroup$ – Scott Apr 18 at 19:55
  • 2
    $\begingroup$ Stirling numbers does not distinguish between different reorderings of the partitions, but here it seems like that would matter. As in, Thomas does the chores in the first part, Craig does the chores in the second part, etc. So you need to multiply by $3!$ for (a), e.g. $\endgroup$ – Mike Earnest Apr 18 at 20:37
  • 2
    $\begingroup$ Also, this explains the difference between your two computations. The first does not account for order, the second does. Indeed $966\times 3!=5796$. $\endgroup$ – Mike Earnest Apr 18 at 20:40
  • $\begingroup$ I see, thank you for the help. $\endgroup$ – Scott Apr 18 at 21:44
  • $\begingroup$ Thanks @MikeEarnest. You solved it. And while I looked again to the results for the second approach I spotted a typo on my code that lead me to an incorrect result, that is now corrected. $\endgroup$ – Ertxiem Apr 18 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.