choosing things, combinations and permutations

I can never get my head round these

Please Register or Log in to view the hidden image!

if you have a string of beads, for example... and this string of beads is made up of two colours, how many possible strings of beads can you have of length...

2? well counting them gives you an answer of 4
3? gives you 8
4 --> 16...

and so on, so

n ---> \( 2^n \)

but, what if i had 3 different colours, and asked the same question?

1 --> 3
2 ---> 9

again it looks like it's

n ---> \(3^n\)

but why is it so? and is it true for a string of length \(a\) beads, with \(n\) different colours, will always have \(a^n\) different possible arrangements?

 

Log in or Sign up to hide all adverts.

Almost. You just got your variables backwards in the formula: given \(c\) different colors of beads, there are \(c^n\) ways to arrange a string of \(n\) beads.

Think of it this way. If you just have a string of one bead, there are \(c\) ways to make it: one for each color the bead could be. Add a second bead, and each one-bead string can become one of \(c\) two-bead strings, depending on what color you add. This makes a total of \(c\times c=c^2\) possible strings. Same thing for a third bead: each two-bead string can be turned into one of \(c\) three-bead strings, making a total of \(c^2\times c=c^3\) possibilities. And so on, all the way up to \(c^n\) for \(n\) beads.

 

Log in or Sign up to hide all adverts.

Consider the fact that a string of one bead is therefore isomorphic, combinatorially, to a string of n beads if and only if the n beads are all the same (color).

Just sayin'

 

Log in or Sign up to hide all adverts.

If the head and tail of a string are indistinguishable, by what factor is the number of permutations reduced?

 

thank you, yes, i see... that is a rather nice way of explaining it. however i do fear that i will my mind will falter me, and this question will come back soon

Please Register or Log in to view the hidden image!

that is a good question. another question a have is... suppose you joined the tail to the head of the sting of beads, making a ring of beads. by then, what factor is it reduced?

 

By the no. of beads I think

 

If you have a string of beads all the same color, the head or tail is completely arbitrary and it doesn't matter if the head and tail are joined; the string has one element in it which is n beads.
Suppose you have a string of n beads such that the beads are not the same color, then you can identify where such a string starts and ends (and hence it still doesn't matter if the string is made into a loop). So using different colored beads means you can do something you can't do when the beads are all the same.

 

It's not just the number of beads. In the case of two beads and two colors (say, black and white), there are four combinations for the ordered necklace (BB, BW, WB, WW) and three for the unordered necklace (BB, BW, WW). The unordered case is a lot harder, and I'll have to give the solution some thought.

 

True. Now I've realized, reducing it by the no. of beads is only if you have a bunch of unique beads.

 

I think it still matters if you tie it into a loop. What if we don't tie it up, but make head and tail indistinguishable?

 

That case is easy enough. If the head and tail are indistinguishable, they can collectively be set up in \(c\) ways with matching colors or \({c \choose 2}=\frac{c(c-1)}{2}\) ways with non-matching colors, for a total of \(\frac{c^2+c}{2}\) ways. The rest of the beads are are still distinguishable, so they still contribute \(c^{n-2}\) to the permutations. The total then becomes (for \(n>1\)):

\(\frac{c^n+c^{n-1}}{2}=\frac{c+1}{2c}P_0\)

where \(P_0\) is the number of permutations with distinguishable ends.

 

Thanks! I'm not sure how you derived it though and it's more complicated than I expected. I find it interesting that the ratio does not depend on n.

 

Wait, I just realized something. When you said that the ends were indistinguishable, did you mean that there is no distinction between reading the string forwards or backwards? Because that answer would depend on n, although I'd have to think for a bit about the exact form. The problem I solved was an ordered, directional string but with the first and last beads interchangeable.

 

Yes, that's what I meant.

 

Suppose you have a loop of beads all the same color. Can you decide where you should cut the loop to make a string with a start and end? Does it make a difference if the beads have (at least two) different colors?

 

I was referring to the second part, where you said that we can find the start and hence tying into a loop makes no difference. But I think there is a difference as it affects the number of combos. I hope I haven't confused anything.

 

My bad! Your actual question makes more physical sense, anyway. If we want to know the number of combinations when there's no distinction between reading the string forwards or backwards, there are two kinds of strings we need to consider. Some strings are palindromes; they read the same forwards and backwards. They are only counted once in the original problem, so we count them the same for the symmetric problem. Non-palindromes, on the other hand, were originally counted twice: once for the forward configuration, and once for the backward configuration. These strings, then, should only count for half in the new problem.

\(P_{sym}=P_{pal}+\frac{P_{npal}}{2}\)

where \(P_{sym}\) is the number of permutations in the symmetric (ie. non-directional) case, \(P_{pal}\) is the number of palindrome permutations in the directional case, and \(P_{npal}\) is the number of non-palindrome permutations in the directional case. Since the palindrome and non-palindrome permutations collectively account for all permutations, we can make the following substitution, with \(P_0\) being the total number of permutations in the directional case:

\(\begin{align}P_0&=P_{pal}+P_{npal}\\ P_{sym}&=\frac{1}{2}(P_0+P_{pal})\end{align}\)

All that remains is to count the number of palindromes for a string of length \(n\). For even \(n\), all palindromes can be formed by defining the first \(n/2\) elements, since the last \(n/2\) elements are restricted to be their mirror images. Unlike whole strings, palindrome-defining half-strings are always directional; one end of the half-string will be connected to its mirror image, so the ends are distinguishable. Therefore, we can plug in the \(c^n\) result from before to find that there are \(c^{n/2}\) palindromes of even length \(n\).

The odd-\(n\) case is very similar. The only difference is that the string's middle bead won't have a mirror-image counterpart, so we can make it any color we like and still have a palindrome as long as the remaining \(n-1\) beads form a palindrome around it. Modifying the expression for the even case, there are \(c\times c^{(n-1)/2}=c^{(n+1)/2}\) palindromes for odd \(n\). Note that \((n+1)/2\) with an odd \(n\) is equivalent to taking \(n/2\) and rounding up. Therefore, we can unify the even and odd cases by introducing the ceiling function \(ceil(x)\) which just means "round up \(x\) to the nearest integer." This notation allows us to say that for any \(n\), \(P_{pal}=c^{ceil(n/2)}\)

Now we can plug back in \(P_0=c^n\) to get an expression for \(P_{sym}\) as a function of \(n\) and \(c\).

\(P_{sym}=\frac{1}{2}(c^n+c^{ceil(n/2)})=\frac{c^n}{2}(1+c^{ceil(n/2)-n})=\frac{1+c^{ceil(-n/2)}}{2}P_0\)

Whew! As a test example, let's look at a string of 5 beads in black and white. If we're considering the symmetric case, the twenty possible strings are:

WWWWW, BBBBB, WWBWW, BBWBB, WBWBW, BWBWB, WBBBW, BWWWB, WWWWB, BBBBW, WWWBW, BBBWB, WWWBB, BBBWW, WWBWB, BBWBW, WWBBW, BBWWB, WBWWB, BWBBW

Using our new formula,

\(P_{sym}=\frac{1+2^{ceil(-5/2)}}{2}2^5=\frac{1+2^{-2}}{2}32=\frac{5}{8}32=20\)

Success! Note that in the above list of strings, the first 8 are palindromes, while the remaining 12 are not. To get back to the directional case, we would have to add back in the reverses of all 12 non-palindrome strings, giving a total of \(8+2\times 12=32\), which was our original number.

 

Fednis, that was a great analysis. I'm only envious that you did it first, it looks quite fun.

 

Nice work! I tried solving this before, but I didn't think of using a ceiling function.

Now if only I could figure out how to input that into a TI-84...

 

Glad you liked it!

Please Register or Log in to view the hidden image!

If you're feeling left out, the "ring of beads" problem is still open, and I don't know how to approach it.

You don't really need the ceiling function, as long as you're willing to treat odd and even cases separately. But putting it into a TI-84 could be challenging. I haven't used one of those for a long time...