Really simple mistake in this combinatorics problem?

[tellmesomething]

TL;DR Summary

A combinatorics problem solved in a needless and agonizing way. Found clever alternate solutions but do not understand why and how it works.

Right, so i came across this problem

Eight runners wearing their favorite colored jerseys have just completed a 100m race and we know the following results.
The BLUE runner finished AHEAD of the TEAL runner The PINK runner finished AHEAD of the GREEN runner The PURPLE runner finished AHEAD of the ORANGE runner
The GREY runner finished AHEAD of the RED runner.
How many different ways can the eight runners finish the race?

My approach was uninteresting and not clever at all. I started making cases i had to make about 14 of them and while it didnt take long,i think it would have been very tedious for a bigger number say 16 players. But it was logical and i got my answer.

Smart approach: I found this

Each restriction divides the total number of permutations by 2. Since they are symmetric and independet, you have 8!/(2^4).

Can someone please explain whats happening here? I understand that 8! is the total number of ways to arrange the players if there were no restriction, but the dividing by 2^4 i do not get.

Thankyou.

 

[PeroK]

Of the total number, half have Blue ahead of Teal and half have Teal ahead of Blue. We can exclude half of these. Of the remaining ones, half of those have Pink ahead of Green and half Green ahead of Pink, so we can exclude half again. Then reduce by half twice more.

 

[tellmesomething]

Of the total number, half have Blue ahead of Teal and half have Teal ahead of Blue. We can exclude half of these. Of the remaining ones, half of those have Pink ahead of Green and half Green ahead of Pink, so we can exclude half again. Then reduce by half twice more.

Hm okay.. say if there were restrictions on 3 jerseys like pink ahead of teal teal ahead of gray.... something like this would it be divided by 3?

 

[PeroK]

Hm okay.. say if there were restrictions on 3 jerseys like pink ahead of teal teal ahead of gray.... something like this would it be divided by 3?

What do you think?

 

[PeroK]

Suppose there were three runners: pink, teal and gray. How many ways can they finish a race? How many ways if pink finishes ahead of teal and teal ahead of gray?

 

[tellmesomething]

Suppose there were three runners: pink, teal and gray. How many ways can they finish a race? How many ways if pink finishes ahead of teal and teal ahead of gray?

Total number of ways without restrictions would be 3!. But with the added restriction it would only be 1? So 3!/3!

 

[PeroK]

So, it was divided by $3!$ and not 3(!)

 

[tellmesomething]

So, it was divided by $3!$ and not 3(!)

I must learn learn LaTex soon. Thankyou.. if you have some time i posted a doubt on chemistry forum regarding thermodynamics

 

[PeroK]

I must learn learn LaTex soon. Thankyou.. if you have some time i posted a doubt on chemistry forum regarding thermodynamics

I know more about combinatorics than I do about thermodynamics!

 

[Vanadium 50]

Be careful. "Blue ahead of Teal and Pink Ahead of Gray" is not the same as "Blue ahead of Teal and Teal Ahead of Pink".

I would look at it this way. There are 8! possible outcomes. Half have Blue Ahead of Teal and the other half have Teal Ahead of Blue. So that constraint reduces this to 8!/2.

Half of the remaining ones have Pink Ahead of Gray and the other half have Gray ahead of Pink. So that reduces it to 8!/4.

And so on.

 

[tellmesomething]

I know more about combinatorics than I do about thermodynamics!

Makes sense. I would choose combinatorics over thermodynamics as well though i know very little of each!

 

[Vanadium 50]

Test to see if you get it. Suppose we make exactly one change to the problem - Teal comes in last. How many possibilities are there?

Spoiler

630
[/ISPOILER]

 

[tellmesomething]

Test to see if you get it. Suppose we make exactly one change to the problem - Teal comes in last. How many possibilities are there?

Spoiler

630
[/ISPOILER][/SPOILER

Sorry for the late reply. The only restriction is teal comes in last? And everything is allowed?

Or is this is an added restriction to my original problem?

 

[PeroK]

Sorry for the late reply. The only restriction is teal comes in last? And everything is allowed?

Or is this is an added restriction to my original problem?

Why not do both?

 

[tellmesomething]

Why not do both?

Sure then I think, if we are considering only the restriction that teal comes in last, we can basically fix its place in the last position and the number of ways to arrange the remaining players would be 7! ?

If we consider the restriction of teal coming last in addition to pink ahead of green , purple ahead of orange and grey ahead of red, we can first count the total arrangements with the only restriction that teal comes in last I.e 7!
Then i think we must eliminate the half of the arrangements where pink is ahead of green so (7!/2!)
Purple is ahead of orange (7!/2!*2!)
Grey ahead of red (7!/2!*2!*2!)
?

 

[Vanadium 50]

I think you have it.

If you want to apply it to a somewhat different situation: you're assigning the 8 runners to 8 lanes on a track. Blie must be next to Teal, Pink must be next to Green, Purple must be next to Orange, and Gray must be next to Red. How many ways to do this?

Spoiler

384

 

[tellmesomething]

I think you have it.

If you want to apply it to a somewhat different situation: you're assigning the 8 runners to 8 lanes on a track. Blie must be next to Teal, Pink must be next to Green, Purple must be next to Orange, and Gray must be next to Red. How many ways to do this?

Spoiler

384

We can maybe think of them as pairs of two which are tied to each other, so it looks like they are one
For eg
Blue and teal; 1 whole person (one cannot be without the other)
Pink and green: 1 whole person
Purple and orange: 1 whole person
Gray and red: 1 whole person

So we essentially have to arrange 4 whole persons/groups which can be done in 4! ways.

Within each group they can be arranged in 2! ways

So: 4!*2!*2!*2!*2!

 

[DrClaude]

Purple is ahead of orange (7!/2!*2!)
Grey ahead of red (7!/2!*2!*2!)
?

That should be 7!/(2!*2!) and 7!/(2!*2!*2!)

 

[Sargon38]

Be careful. "Blue ahead of Teal and Pink Ahead of Gray" is not the same as "Blue ahead of Teal and Teal Ahead of Pink".

I would look at it this way. There are 8! possible outcomes. Half have Blue Ahead of Teal and the other half have Teal Ahead of Blue. So that constraint reduces this to 8!/2.

Half of the remaining ones have Pink Ahead of Gray and the other half have Gray ahead of Pink. So that reduces it to 8!/4.

And so on.

One should nevertheless be careful if one has several of these restrictions.
The statement in the OP can not be correct if just taken as is: namely, "if you have n binary restrictions (A comes in after B) you divide by $2^n$.
There's namely a very simple counter example: consider 3 runners, a, b and c. In total, there are 3! ways of arriving. Now suppose that we have two binary conditions: a comes in before b, and b comes in before c. That would mean $2^2$. But 6 / 4 isn't an integer. There is actually only one outcome with these restrictions.
So I guess this is only correct if the pairwise conditions are independent (don't mention same participants twice).

The reason is that once you introduce the condition: a comes in before b, then a and b are not distributed uniformly anymore over the slots. a has tendency to be more "in the front" and b has tendency to be "more in the back". So next time there's a condition on a or b, you can't just say, "there are as many a in front of c as behind c".