Math Is Fun Forum

Tomm

Member

Registered: 2010-01-14

Posts: 2

Counting number of combinations

I would like help for the following problem.
4 staff that can all do different tasks, Some can perform more than one task, but not at the same time
I would like to find a formula that tells me how many different ways the staff can be organized (rostered) to complete the four different tasks

TASK1      TASK2   TASK3       
*****      Alice       Alice
Betty       Betty      Betty
Carol       Carol      *****
Dianne     *****    *****

I know the answer is 7.
The 7 combinations are
Betty, Carol and Alice
Carol, Alice and Betty
Carol Betty and Alice
Denise Alice and Betty
Denise Bett and Alice
Denise Carol and Alice
Denice Carol and Betty

I want to get and Excel spread sheet to calculate the answer 7.

My Bigger problem contains 20 names and 12 Tasks so i have to careful not to over complicate the solution.

Thank you

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Counting number of combinations

Hi Tomm;

Yes, the answer is 7 as is seen from the expansion of:

Where a = Alice, b = Betty, c = Carol, d = Dianne:

Now you just keep the homogenous terms:

The sum of the coefficients tells you the total number of ways = 7. While each term tells you how many of each, for instance the 3 a b c shows that there are 3 arrangements of Alice Betty and Carol. I don't know how on earth to do this using excel but it is a way to get the answer.

Can you post your bigger problem of 20 names and 12 tasks?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Tomm

Member

Registered: 2010-01-14

Posts: 2

Re: Counting number of combinations

Thank you, your a genius! I will get back to you in regards to the bigger challenge once I have absorbed your answer.

Regards.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Counting number of combinations

Hi Tomm;

Thank you, your a genius!

I am glad to help, but please leave out the incredible statements.

once I have absorbed your answer.

Do not absorb it. It is hideous in every sense of the word. It is an impromptu solution that demonstrates my ignorance. If it was possible to discern my head from a peach pit I would have been able to form the generating function. That would be a beautiful answer. Hurry up and post the big problem.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Counting number of combinations

Bobby's method is valid, but I'd say it's using a cannon to kill a mosquito.

I'd do it by systematically counting.

Betty is the first person listed who can do task 1, so we'll assign her to that.
Now the list for task 2 contains Alice and Carol. We can try assigning Alice to task 2, but that leads us to a dead end. But if we assign Carol to it then we can give task 3 to Alice. One combination found!

Now go back and do the same thing, but with Carol doing task 1.
This time we can give task 2 to Alice and 3 to Betty, or 2 to Betty and 3 to Alice.
2 more combinations.

Finally, see what happens when we give task 1 to Dianne.
This doesn't affect the task 2 list since Dianne since she couldn't do that anyway.
Task 2 has three choices, and it turns out that they give rise to one, one and two choices respectively for task 3.
ie. (Alice, Betty); (Betty, Alice); (Carol, Alice); (Carol, Betty)

And that has systematically found all seven combinations possible.

With the bigger problem, it becomes unfeasible to reason it out by hand, but counting combinations like that is the kind of thing a computer loves.

Edit: Here's an example of a code that would solve the simpler problem (in MATLAB, since that's the only language I know ):

comb = 0;
A = [2,3,4];
B = [1,2,3];
C = [1,2];

for i = A
  for j = setdiff(B,i)
    comb = comb + length(setdiff(C,[i,j]));
  end
end

comb

---

Why did the vector cross the road?
It wanted to be normal.