Permutations with Restriction

K

kilowatt219

New member
Joined
Jul 28, 2019
Messages
3
Hello all, I am not a student, but I came across a simple probability question which was worded ambiguously:

You are fishing in a pond that has 3 Carp, 4 Bass, and 5 Trout. You catch fish at random and place the caught fish into a bucket. What is the probability that you catch a Carp then a Trout?

Obviously the answer the question wants is:

[MATH]\frac{3}{12} * \frac{5}{11} = \frac{5}{44} \approx 11.36\%[/MATH]

However, I was interested in finding what is the probability of catching a Carp then a Trout at any point while fishing? I.E. how many of the ways can you order the fish which contain a Carp followed by a Trout? (An easy enough question to answer, so I thought, but its been bugging me for a week now and I'm out of ideas)

So to find the number total number ways to order the fish, I used restricted permutations. There are 12 total fish, 3 Carp, 4 Bass, and 5 Trout, therefore:

[MATH]\frac{12!}{3!*4!*5!} = 27,720[/MATH] total combinations

And to find the number of combinations in which a Carp is followed by a Trout, I thought to think of there being 11 fish: C, C, B, B, B, B, T, T, T, T, CT. (2 Carp, 4 Bass, 4 Trout, and 1 Carp-Trout combo fish). Finding the number of ways this can be ordered:

[MATH]\frac{11!}{2!*4!*4!*1!} = 34,650[/MATH] combinations with a Carp followed by a Trout

But this is greater than the number of total combinations of the 12 fish.

My question is where am I going wrong? Am I not thinking about the restriction of the Carp followed by a Trout properly?

Thanks in advance for any help you can offer!
 
My first thought is that the pond may NOT only contain 3 Carp, 4 Bass, and 5 Trout! But I am sure that is what the author of the question wanted.
Now onto your question. Your 2nd calculation is wrong! (It is NOT 34,640)
You really need to say that the Trout is immediately after the Carp.
All in all your work is fine,just re-compute that last calculation
 
One problem is that in your first calculation you are considering all the fish of a given type indistinguishable, while in the second you are singling out one carp and one trout to be, as it were, tied together. When more are distinguished, there are more possibilities.

EDIT: Also, you are overcounting, since that particular pair CT may not be in a permutation, but another pair might! You might even have CT C T C T ... as one permutation, and C T CT C T ... and C T C T CT ... as others, all counted separately.

But I think you have to distinguish the fish to do a probability calculation.

(A problem in the exercise itself is that they are forcing you to assume that each fish is equally likely to be caught; why might you not be using bait that only carp, say, like?)

I have to think more about what would be the correct calculation.
 
Last edited:
Jomo said:
Now onto your question. Your 2nd calculation is wrong! (It is NOT 34,640)
You really need to say that the Trout is immediately after the Carp.
All in all your work is fine,just re-compute that last calculation
Click to expand...

Plugging it into Wolfram to double check my math I get the same result...

13085

Dr.Peterson said:
One problem is that in your first calculation you are considering all the fish of a given type indistinguishable, while in the second you are singling out one carp and one trout to be, as it were, tied together. When more are distinguished, there are more possibilities.
Click to expand...

I thought that it would be okay cause I've used it for example in finding the number of ways to order B,A,N,A,N,A where the Ns are not next to each other.

Finding all the ways you can arrange the letters:

[MATH]\frac{6!}{1!*3!*2!} = 60[/MATH]
Subtracting the arrangements where the Ns are together, i.e. when you have: B, A, A, A, NN

[MATH]\frac{5!}{1!*3!*1!} = 20[/MATH] and therefore there are 40 ways to arrange the letters where the Ns are not adjacent. I assumed a similar method could be used here.
 
kilowatt219 said:
I thought that it would be okay cause I've used it for example in finding the number of ways to order B,A,N,A,N,A where the Ns are not next to each other.

Finding all the ways you can arrange the letters:

[MATH]\frac{6!}{1!*3!*2!} = 60[/MATH]
Subtracting the arrangements where the Ns are together, i.e. when you have: B, A, A, A, NN

[MATH]\frac{5!}{1!*3!*1!} = 20[/MATH] and therefore there are 40 ways to arrange the letters where the Ns are not adjacent. I assumed a similar method could be used here.
Click to expand...
But in the BANANA case, you have only the two N's; you don't have any rogue N's wandering around that may or may not be next to the two N's you are focusing on. It would be more like the current problem if you asked about arrangements of BANANA with no two A's together.

Also, probability can be a little different from merely counting ways for something to happen; you have to be sure that what you are counting are equally likely. I'm probably wrong that you have to use permutations rather than combinations, but I'd feel more confident starting out that way. (Note: I don't do anything in combinatorics/probability because "I thought it would be okay"! The best of us make mistakes if we do that too often.)

Let's assume that we do want to count the ways to arrange CCCBBBBTTTTT with at least one CT somewhere. My current thought (which came to me sometime during the night, but I haven't pursued it) is that subtraction would be easiest: first find the number of ways with T never immediately to the right of C. Consider all ways to arrange CCCBBBB, e.g. BCBBCCB, and then place T's so that none is to the right of a C -- so the 5 T's must go in one of these blanks: _B_CB_B_CCB_. You'll have to check whether the number of available spaces depends on the arrangement, but if so, you may be able to take it case by case. At the moment, it looks like this will be far easier than I was imagining!
 
Thats an excellent way of going about it!

The number of ways to order C,C,C,B,B,B,B:

[MATH]\frac{7!}{3!*4!} = 35[/MATH] ways

I also noticed that no matter what, there are always 5 "blanks" where you could insert Ts so that they do not follow a C.

1.) _CCCB_B_B_B_ (Triple Cs)
2.) _B_CCB_CB_B_ (Solo C + Double C)
3.) _CB_CB_CB_B_ (Solo Cs)
4.) _B_B_B_B_CCC (ending with C)

So I found the number of ways you could place the 5 Ts into the 5 empty spaces (where some could be 0). I couldn't find a way to do this nicely, so I did a bit of brute force and found 126 ways it could be done.

Therefore there are

[MATH]35 * 126 = 4,410[/MATH] ways to order the fish in which T never follows C.

And there are [MATH]27,270 - 4,410[/MATH] ways in which T does follow C. Which is [MATH]84.\overline{09}\%[/MATH]
This lines up perfectly with a program I wrote to try to help me get closer to the solution (it also returns 84.09%).

Thank you! I don't think I would have ever thought about looking about "blank insertion spots" without you. I can finally rest.
 
I start by agreeing with you that the question is badly worded. Your initial answer is correct if the intended question is "What is the probability that the first fish caught is a trout and the second fish caught is a carp". But your initial answer does not address the question if we suppose that what the intended question is asking is "What is the probability that the first carp caught is caught after the first trout is caught" or "What is the probability that the first carp caught is caught immediately after the first trout is caught."

And even those questions cannot be answered without knowing how many fish are caught before you stop fishing.

It is a masterpiece of ambiguous writing. It should win a prize.
 
kilowatt219 said:
The number of ways to order C,C,C,B,B,B,B:

[MATH]\frac{7!}{3!*4!} = 35[/MATH] ways

I also noticed that no matter what, there are always 5 "blanks" where you could insert Ts so that they do not follow a C.

1.) _CCCB_B_B_B_ (Triple Cs)
2.) _B_CCB_CB_B_ (Solo C + Double C)
3.) _CB_CB_CB_B_ (Solo Cs)
4.) _B_B_B_B_CCC (ending with C)

So I found the number of ways you could place the 5 Ts into the 5 empty spaces (where some could be 0). I couldn't find a way to do this nicely, so I did a bit of brute force and found 126 ways it could be done.

Therefore there are

[MATH]35 * 126 = 4,410[/MATH] ways to order the fish in which T never follows C.

And there are [MATH]27,270 - 4,410[/MATH] ways in which T does follow C. Which is [MATH]84.\overline{09}\%[/MATH]
This lines up perfectly with a program I wrote to try to help me get closer to the solution (it also returns 84.09%).

Thank you! I don't think I would have ever thought about looking about "blank insertion spots" without you. I can finally rest.
Click to expand...

Excellent. Yes, "blank insertion spots" (nice term) is one of my favorite tricks, well worth remembering.

I had initially assumed there would be several cases to consider, but as you found, there will always be an insertion spot at the left, and one after each of the 4 B's, so there are always 5 places to put the 5 T's.

The next step, I was thinking was easier, because I was picturing putting only one T in each blank, forgetting that, unlike some problems, we don't mind having T's together. After some additional faulty attempts, I realized we can use my absolute favorite trick instead of your brute force: stars and bars. Are you familiar with it?

Here's what we do: We want to put 5 T's in 5 spaces like _CCCB_B_B_B_ or whatever, with any number (even 0) of T's in any one space. We can isolate the spaces from the letters and just think of them as separated by bars, _|_|_|_|_; so a choice of places for the T's looks like |TT|T||TT, where I put none in the first blank, 2 in the second, 1 in the third, none in the fourth, and 2 in the fifth. How many ways can this be done? In as many ways as you can arrange 4 bars and 5 T's (in the typical problem, "stars"). That is [MATH]\frac{9!}{4!5!} =126[/MATH]. There's your number!

So you've got it.
 
You must log in or register to reply here.
Top