My Math Forum  

Go Back   My Math Forum > High School Math Forum > Probability and Statistics

Probability and Statistics Basic Probability and Statistics Math Forum


Thanks Tree1Thanks
  • 1 Post By romsek
Reply
 
LinkBack Thread Tools Display Modes
February 21st, 2019, 12:15 PM   #1
Newbie
 
Joined: Feb 2019
From: London

Posts: 7
Thanks: 0

Cyclic Permutation?

A chain is to contain links of eight different types of material. There are going to be nine links. Eight have a circular shape with two links made of the same material while the rest are made of different materials. The ninth link has a figure of eight shape. The two links made of the same element must not connect together. In how many different ways could we assemble the chain?(Hints. Think about how you put an asymmetric ring on your finger or link your thumbs and forefingers.)

$\displaystyle \frac{(9-1)!}{2} - \frac{(8-1)!}{2}$

I basically eliminated all the permutations where the links made of same material are next to each other from the total number of permutations.

I'm not sure whether this is circular permutation, since not all the links have the same shape? Did I do this right?

Also, how would I take into account the "figure of 8 shape" of one of the links?

My assumption would be that the links adjacent to this one can be linked in different ways... For example, horizontally like all the other links, vertically in 2 ways where one of the "o" of the "8" will be used to connect with the adjacent links...

Last edited by skipjack; February 21st, 2019 at 07:59 PM.
Kieran1 is offline  
 
February 21st, 2019, 09:39 PM   #2
Senior Member
 
romsek's Avatar
 
Joined: Sep 2015
From: USA

Posts: 2,549
Thanks: 1399

are the links connected into a circular chain or are they left as a entire length of chain?
romsek is offline  
February 21st, 2019, 10:18 PM   #3
Newbie
 
Joined: Feb 2019
From: London

Posts: 7
Thanks: 0

Quote:
Originally Posted by romsek View Post
are the links connected into a circular chain or are they left as a entire length of chain?
It seems i forgot to mention the most important part. The links are connected in a circular chain.
Kieran1 is offline  
February 21st, 2019, 10:51 PM   #4
Senior Member
 
romsek's Avatar
 
Joined: Sep 2015
From: USA

Posts: 2,549
Thanks: 1399

Ok so to distill this problem down.

We have 9 total links forming a circular chain.

Two of the links are indistinguishable, the other 7 are distinct.

One way or another these links are attached to two neighbors each.

It is stipulated that the two links of the same material cannot be neighbors.

This sound right or is there some further property of the figure 8 link I'm missing?
romsek is offline  
February 21st, 2019, 11:08 PM   #5
Newbie
 
Joined: Feb 2019
From: London

Posts: 7
Thanks: 0

Quote:
Originally Posted by romsek View Post
This sound right or is there some further property of the figure 8 link I'm missing?
No, you got everything.

Since they didn't specifically mention whether the figure 8 link can be linked with adjacent links in different ways... i guess i was overcomplicating things.
Kieran1 is offline  
February 22nd, 2019, 12:45 AM   #6
Senior Member
 
romsek's Avatar
 
Joined: Sep 2015
From: USA

Posts: 2,549
Thanks: 1399

Ignoring the rule about the 2 indistinct links not being adjacent for a moment there are a total of

$n_t = \dfrac{\dbinom{9}{2}7!}{9}= 20160$ arrangements possible.

There will be $n_2=\dfrac{9 \cdot 7!}{9} = 7! = 5040$ arrangements that violate the rule

So there are $n_{ok} = 20160 - 5040 = 15120$ acceptable arrangements
romsek is offline  
February 22nd, 2019, 10:14 AM   #7
Newbie
 
Joined: Feb 2019
From: London

Posts: 7
Thanks: 0

Quote:
Originally Posted by romsek View Post
Ignoring the rule about the 2 indistinct links not being adjacent for a moment there are a total of

$n_t = \dfrac{\dbinom{9}{2}7!}{9}= 20160$ arrangements possible.

There will be $n_2=\dfrac{9 \cdot 7!}{9} = 7! = 5040$ arrangements that violate the rule

So there are $n_{ok} = 20160 - 5040 = 15120$ acceptable arrangements

Thanks! So was I wrong on the circular/cyclic permutation part? Also could you explain how you came up with the arrangements?
Kieran1 is offline  
February 22nd, 2019, 01:22 PM   #8
Senior Member
 
romsek's Avatar
 
Joined: Sep 2015
From: USA

Posts: 2,549
Thanks: 1399

Quote:
Originally Posted by romsek View Post
Ignoring the rule about the 2 indistinct links not being adjacent for a moment there are a total of

$n_t = \dfrac{\dbinom{9}{2}7!}{9}= 20160$ arrangements possible.

There will be $n_2=\dfrac{9 \cdot 7!}{9} = 7! = 5040$ arrangements that violate the rule

So there are $n_{ok} = 20160 - 5040 = 15120$ acceptable arrangements
Quote:
Originally Posted by Kieran1 View Post
Thanks! So was I wrong on the circular/cyclic permutation part? Also could you explain how you came up with the arrangements?
The denominator of 9 in both cases is due to rotational symmetry.

In the first case we note that we can first choose 2 slots of 9 for the
indistinguishable links.

Then we can fill the remaining 7 slots however and that's the 7!

Then for the unacceptable cases we note there are 9 pairs of adjacent links.
1 and 9 are considered adjacent. We fill those with the indistinguishable links and can choose the remaining 7 links 7! ways.

We then take the difference to determine the number of acceptable arrangements.
Thanks from Kieran1
romsek is offline  
Reply

  My Math Forum > High School Math Forum > Probability and Statistics

Tags
cyclic, permutation



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
cyclic group Jas17 Pre-Calculus 3 October 17th, 2015 11:30 AM
Cyclic Quadrilaterals Jet1045 Algebra 6 October 12th, 2013 01:15 PM
No cyclic group. yotastrejos Abstract Algebra 2 September 3rd, 2013 08:56 PM
cyclic group wtdf0201 Abstract Algebra 2 September 4th, 2010 05:08 PM
Cyclic Extensions.... TTB3 Abstract Algebra 0 April 2nd, 2009 10:41 AM





Copyright © 2019 My Math Forum. All rights reserved.