Permutations (with repetitions) problem

In summary, the conversation discusses a problem involving assigning 6 jobs to 5 people. The question asks for the number of different arrangements under certain conditions. The conversation includes formulas for calculating permutations and combinations, and two different approaches to the problem are presented. The correct answer is determined to be 4! * nCr(6,2) = 360, which takes into account the possibility of one person doing 2 jobs and the others doing 1 job each.
  • #1
NatFex
26
3
Moved from a technical forum, so homework template missing

Homework Statement


[/B]
The question is phrased in the following way:

There are 6 jobs to be assigned to 5 people. Each job is assigned only to one person, and each person must have at least one job. How many different arrangements are there?

Homework Equations



In general, I would approach a selection of k objects from a total of n in the following way:

Permutations without repetition: n!/(n-k)!
Permutations with repetition: nk
Combinations without repetition: n!/((n-k)!k!) – I express this as nCr(n,k) below.

The Attempt at a Solution



Given those conditions, then it stands to reason that 4 people will have 1 job and someone will have 2.

I approached the problem by thinking about the number of possible employees for every job then multiplying it all out:

Job 1: 5 (all of them)
Job 2: 4
Job 3: 3
Job 4: 2
Job 5: 1
Job 6: 5 (allocated to someone who also did another job above)

5*4*3*2*1*5 = 5! * 5 = 600

This seemed to me like it should logically work. The job numbering is obviously arbitrary so this should take into account any assortment/ordering

However, the correct answer turned out to be 4! * nCr(6,2) = 360. The reasoning behind this revolves around splitting the problem into the first 4 jobs (hence the 4!), then, for the last 2 jobs, working out how many ways there are to select 2 jobs out of 6 for 1 person to do (hence 6 choose 2.)

This makes a little bit of sense, but not as much as my initially proposed solution. Can someone explain exactly where this succeeds and where mine falls short? Why is my number larger? What are the 'excess' possibilities it's counting? Thanks
 
Last edited:
Physics news on Phys.org
  • #2
The problem with your counting method is that jobs 1 & 2 could be done by the same person.

That said, I don't agree with the "correct" answer.
 
  • #3
PeroK said:
The problem with your counting method is that jobs 1 & 2 could be done by the same person.

That said, I don't agree with the "correct" answer.
Does it really matter if I arranged it as 5*4*3*2*1*5 or 5*5*4*3*2*1? (In the case of the latter, jobs 1 & 2 can be done by the same person, but given that multiplication is commutative and that, as I've said, the job numbering is arbitrary, does it make a difference?)

I would like to see your take on the correct answer, if you don't mind.

Thanks
 
  • #4
NatFex said:
Does it really matter if I arranged it as 5*4*3*2*1*5 or 5*5*4*3*2*1? (In the case of the latter, jobs 1 & 2 can be done by the same person, but given that multiplication is commutative and that, as I've said, the job numbering is arbitrary, does it make a difference?)

I would like to see your take on the correct answer, if you don't mind.

Thanks
I would do it for 3 jobs and 2 people. It's easy to count them all. Then you can check whether your formula works.
 
  • #5
PeroK said:
I would do it for 3 jobs and 2 people. It's easy to count them all. Then you can check whether your formula works.
Indeed it doesn't! Formula yields 4 whereas there are 6 countable solutions. However, all I'm alerted to is the fact that I'm wrong and not how/why. I realize this is much to ask, so any input is appreciated.
 
  • #6
NatFex said:
Indeed it doesn't! Formula yields 4 whereas there are 6 countable solutions. However, all I'm alerted to is the fact that I'm wrong and not how/why. I realize this is much to ask, so any input is appreciated.
You must label the jobs and the people before you start. Then, you exclude the option of jobs 1 & 2 being done by the same person.

To help you, my starting point was to think that one person must do 2 jobs and the other 4 people must do 1 job each.
 
  • Like
Likes NatFex

Related to Permutations (with repetitions) problem

1. What is a permutation with repetitions problem?

A permutation with repetitions problem refers to a mathematical concept where the order of a set of objects is rearranged while allowing for repeated elements. This means that each element can appear more than once in the permutation. The number of possible permutations with repetitions is calculated using a specific formula.

2. How is a permutation with repetitions different from a regular permutation?

In a regular permutation, the elements cannot be repeated, which means each element can only appear once in the permutation. However, in a permutation with repetitions, the elements can be repeated, allowing for a larger number of possible permutations.

3. What is the formula for calculating the number of permutations with repetitions?

The formula for calculating the number of permutations with repetitions is n^r, where n is the number of objects and r is the number of elements in each permutation. This means that for a set of 5 objects with 3 elements in each permutation, there would be 5^3 or 125 possible permutations.

4. What are some real-life applications of permutations with repetitions?

Permutations with repetitions are commonly used in fields such as computer science, statistics, and genetics. In computer science, they are used in algorithms for finding solutions to problems. In statistics, they are used in probability calculations. In genetics, they are used to analyze and understand the different combinations of genes in an organism.

5. What are some strategies for solving permutation with repetitions problems?

One strategy for solving permutation with repetitions problems is to list out all the possible combinations systematically. This can be done by using a tree diagram or creating a table. Another strategy is to use the formula n^r to calculate the number of possible permutations. Additionally, understanding the problem and identifying any patterns or restrictions can also help in finding the solution.

Similar threads

  • Calculus and Beyond Homework Help
Replies
8
Views
967
  • Calculus and Beyond Homework Help
Replies
1
Views
297
  • Calculus and Beyond Homework Help
Replies
3
Views
595
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
12
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
Back
Top