Pre-Cal 40S (Winter 2009): Permutations of Non-Distinguishable Objects and Circular Permutations

Hello everyone, today we learned about Permutations of Non-Distinguishable Objects and Circular Permutations. Mr. K started the class by splitting everyone into groups and he gave us a problem to solve.

How many four-digit even numbers are there if the same digit cannot be used twice?

We ended up with the answer 2, 290. Now, you're probably wondering how we got this number. Because the same digit cannot be used twice, we have to consider the fact that we cannot have zero as our first digit number. Having zero as our first digit number would give us a three digit number rather than four. So we looked at two different ways, one having the zero at the end, and another not having zero as our last digit number.
If we had zero as our last digit number, that would leave us with 9 different digits to choose from for our first digit number, then 8 for the second digit number, and 7 for the third.
If we multiply these numbers together we would end up with 504 ways of re-arranging the digits to make a four-digit even number if we used zero as our last digit.
Now, If we didn't use zero as our last digit number, we are left with 4 different digits to choose from. Those digits are 2, 4, 6, and 8.
For the first digit number, because we had taken one digit from the ten we originally had, that leaves us with nine choices, but remember that we cannot have zero as our first digit, so now we are left with eight choices for our first digit. For the second digit we will still have eight, because now, we can use zero, and we've only used two out of the ten choices, and as for the third digit, we would have seven choices.
Like what we did previously, we have to multiply these numbers together, and we would end up with 1792 ways of re-arranging the digits to make a four-digit even number, if we didn't use zero as our last digit number.
After, we added the two ways of re-arranging the digits to make a four-digit even number together, we end up with 2296 ways.

NOW, what if the same digit can be repeated?

Because we can use the same digit repeatedly, we don't have to do the same thing we did for the previous question.
For the last digit, there will be five different digits to choose from. Those digits are 0, 2, 4, 6, and 8. These are the only digits we can choose from as our last digit, because the four digit number has to be even.
For our first digit, we only have nine choices, because we exclude zero, for reasons we had stated earlier. For the second and 3rd digit, we can use any of the numbers, so we have ten choices for both. If we multiply these numbers together, we end up with 4500 different ways to re-arrange a four-digit number.
Now, why do we multiply the number of choices for each digit to solve for the number of ways we could re-arrange a four-digit number? It is because of The Fundamental Principle of Counting. The Fundamental Principle of Counting states that if you have M ways of doing one thing, and N ways to do a second thing, then you have MxN ways of doing both things.
Something Mr. K pointed out while we were solving the question above. Make sure to write an explanation as to why you are doing what you're doing.

How many ways can 8 books be arranged on a shelf, if 3 particular books must be together?

Mr. K explained to us that we should look at the 3 books that must be together as one object. So the way he explained it was that you can take those 3 books, and put them in a bag. Now, you have 5 books plus 1 bag, which leaves you with 6 objects. We can solve for all the different ways we can re-arrange those 6 objects. We end up with:
6!
That's not the answer though, remember the 3 books you put in a bag? Well, once we've found a place to put the bag, we're going to have to take the books out of the bag and find the different ways we can re-arrange them. So now, we end up with:
3!
Using The Fundamental Principle of Counting, we can put those two together, and we end up with:
6!3! = 4320

Permutations of Non-Distinguishable Objects

How many different 4 letter "words" can you make from the letters in the word BOOK?

Well, the answer is 12.
You're probably wondering why the answer is 12, when 4! is 24. Well, the word BOOK, has two O's in it. The two O's are NON-DISTINGUISHABLE, in other words, we can't tell apart. The only way we would be able to tell them apart is by writing the O's in different colors.

It is obvious that there are two copies of each word, but the O's had been switched. If those O's were of the same color, we would have two of each words, and we would only count one of the two.
After that, Mr. K gave us a different scenario. What if the word was BOOO, instead of BOOK? Well, if the word was BOOO, we would only be able to make four "words" out of it. That was when we were given this rule:

That is, the number of ways we can re-arrange the object, divided by the number of ways we can re-arrange the non-distinguishable objects.

CIRCULAR PERMUTATIONS
How many distinguishable ways can 3 people be seated around a circular table?

As you can see from the diagram above, the answer is two. The reason is because, when we are arranging with a circle, it has no beginning or end. Whatever is placed first, wherever we place them, or however we place them doesn't matter, we just start arranging around them.

How many distinguishable ways can 3 beads be arranged on a circular bracelet?

Now, a bracelet question is a special case. This is because, it depends on how we put on the bracelet.

Using the table diagram again, we can see that if the table at the top left hand corner was flipped horizontally, it would be the same as the blue table beside it. So that leaves us with only one way of arranging the objects.