Results 1 to 9 of 9

Math Help - Permutations and combinations

  1. #1
    Member roshanhero's Avatar
    Joined
    Aug 2008
    Posts
    179

    Permutations and combinations

    A craftsperson has a six different kinds of seashells. How many different bracelets can be constructed if only four shells are to be used in any one bracelet?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Mar 2008
    From
    Pennsylvania, USA
    Posts
    269
    Thanks
    37
    Quote Originally Posted by roshanhero View Post
    A craftsperson has a six different kinds of seashells. How many different bracelets can be constructed if only four shells are to be used in any one bracelet?

    The number of k-combinations from a set with n elements is given by the binomial coefficient

    <br />
\binom{n}{k} = \frac{n!}{k!(n-k)!}<br />


    Alternatively, we can use the following notions:

    <br />
_{n}C_k=C(n,k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}<br />
    Last edited by abender; January 13th 2010 at 11:50 AM. Reason: latex
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Mar 2008
    From
    Pennsylvania, USA
    Posts
    269
    Thanks
    37
    So, to clarify some if this still confuses you.

    You want to know the number of possible 4 element combinations chosen from a set of 6 distinct elements.

    So, k=4 and n=6.

    Thus, your solution is given by

    <br />
_{6}C_4=C(6,4) = \binom{6}{4} =\frac{6!}{4!(6-4)!}<br />
,

    whereby "!" denotes the factorial operation.

    -Andy
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    I think the question is a little more subtle:

     {n \choose k} is the amount of sets we can compose of length k out of a set of n objects.
    (think of it as choosing different colour combinations)

    However the question is how many bracelets can we make: Then we should count some permutations too!

    Let's denote the set sea-shells {A,B,C,D,E,F}.
    We can choose 4 seashells: For example: {A,B,C,D}

    A bracelet might look like this for example: *-A-B-C-D-*
    (the little * are connected)
    This bracelet if ofcourse the same as: *-D-A-B-C-*
    But not the same as: *A-C-B-D* while we used the same sea-shells.

    For example: we could argue that 2 bracelets are the same if and only if they can be turned into eachother by rotating.

    So for every choice of 4 sea-shells we must count the amount of "real " permutations \sigma \in S_4.
    We need some algebra for that.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    Ok. So I hope I'm correct:

    We have 4! permutations in the group S_4
    Observe that the bracelet is invariant under rotating in the 4 symmetry -axis of the bracelet, and invariant under cyclic permutation.
    Thus the bracelet is invariant under the permutations of D_4


    A - B
    C - D

    Let \sigma\in S_4. Observe that for any \tau_1,\tau_2\in D_4 we have \tau_1\sigma\leftrightarrow \tau_2\sigma .

    Since D_4 \subset S_4 is a sub-group with 8 elements we have |S_4/D_4| = 3.

    So the amount of "real different" permutations is 3 and the amount of "real different" bracelets is 3\cdot {6\choose 4} = 45
    Last edited by Dinkydoe; January 15th 2010 at 08:58 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Mar 2008
    From
    Pennsylvania, USA
    Posts
    269
    Thanks
    37
    Quote Originally Posted by Dinkydoe View Post
    I think the question is a little more subtle:

     {n \choose k} is the amount of sets we can compose of length k out of a set of n objects.
    (think of it as choosing different colour combinations)

    However the question is how many bracelets can we make: Then we should count some permutations too!

    Let's denote the set sea-shells {A,B,C,D,E,F}.
    We can choose 4 seashells: For example: {A,B,C,D}

    A bracelet might look like this for example: *-A-B-C-D-*
    (the little * are connected)
    This bracelet if ofcourse the same as: *-D-A-B-C-*
    But not the same as: *A-C-B-D* while we used the same sea-shells.

    For example: we could argue that 2 bracelets are the same if and only if they can be turned into eachother by rotating.

    So for every choice of 4 sea-shells we must count the amount of "real " permutations \sigma \in S_4.
    We need some algebra for that.
    This is a good point. It was not specified in the problem, but if I had given this a little more thought, I would have reasoned that the set of all possible bracelets is equivalent to the set of all permutations with n=6 and r=4. If I had given it even more thought, I might have also had the sense to eliminate "duplicate bracelets" from the set of permutations. I responded in too much haste to this question. Good pick up. Rep +1 + 1
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,683
    Thanks
    615
    Hello, roshanhero!

    "Bracelet" problems are always tricky.
    I've only started on the solution . . .


    A craftsperson has a six different types of seashells.
    How many different bracelets can be made if four shells are used in any one bracelet?
    NOTE: It did not say that four different types of shells are used.
    . . . . . This further complicates the problem.


    Case 1

    Four different shells: WXYZ


    There are: _6C_4 \:=\:15 choices for the types of shells.

    The four shells can be placed in a circle in: . 3! \,=\,6 ways.


    But a bracelet can be turned over.

    That is: . \begin{array}{ccc}&W& \\ Z&&X \\ &Y \end{array} . is the same bracelet as: . \begin{array}{ccc}&W& \\ X&&Z\\ &Y& \end{array}


    Therefore, there are: . \frac{15\cdot6}{2} \:=\:45 different bracelets
    . . which have four different types of shells.


    I'll let you work out the other cases . . .

    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    Soroban is right.

    Even I did assume that 4 different shells were used but it becomes even more complicated considering we don't have to use different shells.

    This is actually quite a difficult problem:

    For every Choice of sea-shells we must figure out under wich permutations in S_4 the bracelet is invariant.

    I think without Algebra and the formula of William Burnside this problem is difficult.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    Ok, so this is how we do it:

    the number we must calculate is:

    number different bracelets = {6 \choose 1}k_1+ {6\choose 2}k_2+{6\choose 3}k_3+{6\choose 4}k_4

    Where k_i is the number of different ways we can permutate the shells such that it can not be obtained by rotation.

    We allready know k_1 = 1, k_4 = 3 and we have k_2 = 2. Can you figure out k_3?

    (I calculated 101 different bracelets)
    Last edited by Dinkydoe; January 15th 2010 at 01:28 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. combinations and permutations
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: June 1st 2010, 02:49 PM
  2. I need help in Permutations and Combinations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 23rd 2010, 03:04 PM
  3. combinations of permutations?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 10th 2009, 06:21 PM
  4. Permutations and Combinations
    Posted in the Statistics Forum
    Replies: 1
    Last Post: May 12th 2008, 10:07 AM
  5. Combinations and permutations
    Posted in the Statistics Forum
    Replies: 2
    Last Post: March 18th 2008, 04:10 PM

Search Tags


/mathhelpforum @mathhelpforum