What is the number of combinations for assigning 10 people to 5 tasks?

[lfdahl]

Hi there,

here´s my (unsolved) problem. I´d really appreciate a thorough answer.

10 different persons are to be assigned to 5 different tasks:

Every person must have exactly one assignment, and a task can (of course) be assigned to more than one person. A possible combination could be:

task no 1: 3 persons
task no 2: 1 person
task no 3: 4 persons
task no 4: 1 person
task no 5: 1 person
Here: All 10 persons have exactly one assignment.But: not all tasks need be assigned: For example task no. 3 can be assigned to all 10 persons, leaving 0 persons for the other 4 tasks. So another possible combination is:

task no 1: 0 persons
task no 2: 0 persons
task no 3: 10 persons
task no 4: 0 persons
task no 5: 0 persons

How many possible combinations are there?

Thankyou in advance for any help on this.Lars/lfdahl

 

[Jameson]

Re: # combinations?

This is an interesting problem that I haven't encountered before. It's essentially putting 10 people into 5 groups, but there are no restrictions on the size of a group as long as the total doesn't exceed 10.

I think of it like this: \(\displaystyle \sum \left[ \binom{10}{i_1}+\binom{10-i_1}{i_2}+\binom{10-i_1-i_2}{i_3}+\binom{10-i_1-i_2-i_3}{i_4}+\binom{10-i_1-i_2-i_3-i_4}{i_5} \right]\)

where $i_1+i_2+i_3+i_4+i_5=10$. Not sure how to do this but will keep thinking and I hope someone else has an idea.

 

[MarkFL]

I would look at this as a partitioning problem. We have 10 objects that are to be partitioned into 5 groups. This means there are 11 places in which to put each of the 4 partitions.

edit: Upon further reflection, this does not seem correct, as it assumes an ordering of the 10 people. I am now thinking it would be better to observe that for each of the 10 people, there are 5 choices of tasks to which they could be assigned.

 

[Opalg]

I would look at this as a partitioning problem. We have 10 objects that are to be partitioned into 5 groups. This means there are 11 places in which to put each of the 4 partitions.

edit: Upon further reflection, this does not seem correct, as it assumes an ordering of the 10 people. I am now thinking it would be better to observe that for each of the 10 people, there are 5 choices of tasks to which they could be assigned.

I don't think that this method assumes an ordering of the 10 people, but it does have a different defect.

To illustrate the situation, represent the 10 people by 10 bullet points in a row, with spaces between them and also a space at each end (11 spaces in all). Split the 10 dots into five groups by inserting partitions in four of the spaces. For example,

   • •|• • •|•|• • • •|
    1    2   3    4    5

In that example, group 1 gets 2 members, group 2 gets 3 members, group 3 gets 1 member, group 4 gets 4 members, group 5 gets 0 members. There are 4 dividing lines and 11 places in which to put them, giving \(\displaystyle {11\choose 4}\) partitions.

The defect with that solution is that it is not good at allocating empty groups. In the above example, group 5 is empty because we can put a divider in the space at the end of the row. Group 1 could also be empty for the same reason. But to get any of the other groups empty, we would need to put a double (or triple, or quadruple) divider into some space or spaces. For example, suppose we wanted to modify the above example to put an extra member into group 2 and to leave group 3 empty, we would need to partition the groups as follows:

   • •|• • • •||• • • •|
    1     2   3   4     5

To do that we need dividers of the form $\|\ |\ |$ instead of $|\ |\ |\ |$. This time, there are only three dividers, but one of them is a double one. There are 3 ways of ordering the dividers (depending on where the double one comes) and, for each of those choices, \(\displaystyle {11\choose 3}\) ways of inserting them.

Other possibilities that have to be considered are: two double dividers; a triple divider and a single one; a quadruple divider.

Adding up all the possible combinations, I get the total number of ways of allocating the people into the groups as $${11\choose 4} + 3{11\choose 3} + {11\choose 2} + 2{11\choose 2} + {11\choose 1}.$$

This is a good example of an apparently straightforward combinatorial problem that is actually not as simple as it seems. I hope that somebody else will find a better way of attacking this tricky counting problem.

 

[lfdahl]

One formal approach would be:

https://www.physicsforums.com/attachments/1696

with the restriction:

sum(n_i) = 10.

But this requires a systematic partitioning ...

 

[Opalg]

This is a continuation of my previous comment #4.

In each case, we have ten persons and four dividers, and these can be placed in any order. So we can regard this as a row of 14 symbols, comprising 4 dividers and 10 persons. This is completely described if we specify which of the 14 positions in the row are occupied by dividers, and there are ${14\choose 4}$ ways of doing this. So the answer to the problem is ${14\choose 4} = 1001.$ That agrees with my previous answer, but is a good deal simpler to compute.

 

[Plato2]

10 different persons are to be assigned to 5 different tasks:
Every person must have exactly one assignment, and a task can (of course) be assigned to more than one person. A possible combination could be: How many possible combinations are there?l

Although I have carefully read all replies, I can honestly say that I don't understand what is being counted.
When I first read the OP, the word different in both places drew my attention.
I thought at the answer was \(\displaystyle 5^{10}\). The number of functions from a set ten to a set of five.
That does have each person assigned to exactly one task.

But of course, that means that some tasks may not have anyone assigned to do it.
It seems perfectly reasonable to have each task covered.
Then we could count the number of surjections from a set of ten to a set of five.
$$\sum\limits_{k = 0}^4 {{{\left( { - 1} \right)}^k}\binom{5}{k}{{\left( {5 - k} \right)}^{10 - k}}}$$

As I said that is considering difference: person A assigned task I is different from person A assigned task II.
If that is not what the question means, then I understand why some worry about the number of partitions.
How should the OP be read?

 

[Opalg]

Although I have carefully read all replies, I can honestly say that I don't understand what is being counted.
When I first read the OP, the word different in both places drew my attention.
I thought at the answer was \(\displaystyle 5^{10}\). The number of functions from a set ten to a set of five.
That does have each person assigned to exactly one task.

But of course, that means that some tasks may not have anyone assigned to do it.
It seems perfectly reasonable to have each task covered.
Then we could count the number of surjections from a set of ten to a set of five.
$$\sum\limits_{k = 0}^4 {{{\left( { - 1} \right)}^k}\binom{5}{k}{{\left( {5 - k} \right)}^{10 - k}}}$$

As I said that is considering difference: person A assigned task I is different from person A assigned task II.
If that is not what the question means, then I understand why some worry about the number of partitions.
How should the OP be read?

The way I understood the question, the tasks can be distinguished, but the persons cannot. The tasks are numbered, from 1 to 5, which indicates that each one has a label on it. The persons, on the other hand, are not individually identified. We are not interested in them as individuals, only in the number of them assigned to each group.

You are right to emphasise the importance of the wording of the question. If my interpretation is wrong then the answer would be very different. For example, if we could identify two of the persons as Person A and Person B, and if we wanted to distinguish the situation in which Person A was allocated to Group1 and Person B to Group 2 from the situation in which Person B was in Group 1 and Person A in Group 2, then that would greatly increase the number of possible combinations.

 

[Plato2]

The way I understood the question, the tasks can be distinguished, but the persons cannot. The tasks are numbered, from 1 to 5, which indicates that each one has a label on it. The persons, on the other hand, are not individually identified. We are not interested in them as individuals, only in the number of them assigned to each group.

Well under that reading we have a multi-selection.
Select \(\displaystyle K\) items from \(\displaystyle N\) different types: \(\displaystyle \binom{K+N-1}{K}\)

 

[lfdahl]

The way I understood the question, the tasks can be distinguished, but the persons cannot. The tasks are numbered, from 1 to 5, which indicates that each one has a label on it. The persons, on the other hand, are not individually identified. We are not interested in them as individuals, only in the number of them assigned to each group.

You are right to emphasise the importance of the wording of the question. If my interpretation is wrong then the answer would be very different. For example, if we could identify two of the persons as Person A and Person B, and if we wanted to distinguish the situation in which Person A was allocated to Group1 and Person B to Group 2 from the situation in which Person B was in Group 1 and Person A in Group 2, then that would greatly increase the number of possible combinations.

Yes, the persons also can be distinguished, like the tasks. Sorry, if my original question did not point this out clearly ...(Speechless)

 

[Opalg]

Well under that reading we have a multi-selection.
Select \(\displaystyle K\) items from \(\displaystyle N\) different types: \(\displaystyle \binom{K+N-1}{K}\)

Exactly. We have to select (or assign) $K=10$ persons to go to $N=5$ types of group. So we get ${10+5-1\choose 10} = {14\choose10} = {14\choose4}$ ways of doing it (but it took me a while to recognise that it is that sort of problem).

- - - Updated - - -

Yes, the persons also can be distinguished, like the tasks. Sorry, if my original question did not point this out clearly ...(Speechless)

In that case, the answer is $5^{10}$, as Plato said in #7. (For each of the 10 persons there are $5$ choices of group.)

 

[lfdahl]

Number of combinations solved...(?)

#combinations = 5¹⁰

 

[lfdahl]

Thankyou so much everyone for clearing up the matter!

/lfdahl