# Math Help - Permutations and combinations

1. ## 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?

2. Originally Posted by roshanhero
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

$
\binom{n}{k} = \frac{n!}{k!(n-k)!}
$

Alternatively, we can use the following notions:

$
_{n}C_k=C(n,k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}
$

3. 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

$
_{6}C_4=C(6,4) = \binom{6}{4} =\frac{6!}{4!(6-4)!}
$
,

whereby "!" denotes the factorial operation.

-Andy

4. 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.

5. 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$

6. Originally Posted by Dinkydoe
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

7. 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 . . .

8. 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.

9. 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)