Question

How many permutations of the digits 1; 2; 3; 4; 5, have at least one digit in its
own spot? In other words, a 1 in the rst spot, or a 2 in the second, etc.

Answer 1

Best way to do this, is to find all possible permutations, and subtract those that have no digits in their own spot.

Can you tell me how many total permutations there are?

Answer 2

total permutations...5*(9^5)?

Answer 3

sorry, 5*5^5

Answer 4

The total permutations should just be \(5!\) since you have 5 choices for the first spot, 4 for the second, and so on.

Answer 5

yes, I see, only using the set given, not numbers 1-5...continue

Answer 6

Now we need to figure out how many arrangements don't have a 1 in the first place, a 2 in the second, a 3 in the third, and so on. This is a little bit trickier.

Answer 7

I'm not sure how to begin...

Answer 8

We could do a case by case analysis, but I'm trying to see if there's an easier way to do it.

Answer 9

5*4!

Answer 10

sounds right

Answer 11

It may be \(5\cdot4!\) can you explain how instead of giving the answer out?

Answer 12

But it was same as 5! . Now it is confusing

Answer 13

It was same as total number of permutations. It should be less than those

Answer 14

Right, so clearly \(5\cdot 4!\) is not correct. However, I do think it's closely related to \(4!\).

Answer 15

First, we have to choose a number to put in the first place. It must be one of {2,3,4,5}. So we have 4 possibilities (multiply by 4). Now, suppose we put 4 in the first place.

Now let's find what goes in the fourth place. It must be one of {1,2,3,5}. Once again, 4 choices, so we multiply by 4 again. Here we have two cases:
Case 1: 1 is put in the fourth place. Here, we move to another open place and continue except our problem is reduced to three numbers instead of 5. With three numbers we can easily enumerate all possibilities. There are exactly 2.

Case 2: We don't put 1 in the fourth place. In this case we continue as were were doing previously.

Answer 16

Case 2 (cont.)

If we continue with case 2, let's say we put 2 in the fourth place. Now we move to the second place. We can put {1,3,5} there. So we multiply by 3. Again, we have a case where we put 1 there, or we don't put 1 there.

1 there: problem is reduced to {3,5}, and there is one solution.

1 not there: 2 possibilities, lets say we put 3 there. That means we move to the third spot, and we have {1,5} as choices. Notice that if we put 1 there, 5 must go in the fifth spot, so there is only one possibility.

Answer 17

Give me a minute to look through this and see how this all adds up...

Answer 18

thank you for explaining, i'll have to read you explanation a few more times before it sticks

Answer 19

professor actually gave us the answer of 76, but requires that we show how we got there

Answer 20

I believe you should get \[4(1(2)+3(1+2))=44\]

Answer 21

says that it's not too hard if done cleverly.

Answer 22

Then you subtract them, you get 120-44=76.

I'll see if I can get a more clever way.

Answer 23

so, 5! - 44 = 76...

Answer 24

Since there are 44 permutations that we don't want, we subtract 44 from 5!

Answer 25

and your equation provided earlier, follows the same lines as your dialogue explainning it...

Answer 26

Right, it's a little difficult to see where I got the formula from, but if you're careful enough, that's what you get.

Answer 27

George, is it possible to explain the equation more concisely in dialogue...I'm on the verge of grasping.

Answer 28

I can try.

Answer 29

You first multiply by 4 since you have 4 numbers to choose from. The next step I explained the least clearly. You have 4 numbers to choose from, but it depends on what you choose. So your equation should look like \[4(1(x)+3(y))\]where \(x,y\) are what we calculate latr based on the case.

Answer 30

For \(x\), we replace it with 2 since this corresponds to the reduced case of {1,2,3}. Since there are 2 ways to place numbers {1,2,3} in three places such that they are all not in their own place we replace it with a 2.

Answer 31

For \(y\), we replace it with an expression that looks like \[1(a)+2(b)\]Since we now have 3 choices of numbers to place.

We find \(a=1\) since this is corresponding to the {1,2} case, and we only have a single solution there.

We find \(b=1\) as well since that was after we had reduced to the placing {1,5} in the third and fifth place, and there is only one way to do that.

Answer 32

so by you saying that we multiply by 4 "again", this is a distribution across two cases?

Answer 33

Yes. I was a little misleading when I typed that.

Answer 34

thanks, much clearer, closing and moving on...

Answer 35

The number of permutations with no number in its own spot is given by the recurrence relation \[S(n)=(n-1)\left(S(n-1)+S(n-2)\right)\]with base cases \(S(1)=0\) and \(S(2)=1\).

Answer 36

In fact, these are exactly the derangement numbers. I feel stupid for not remembering this immediately. http://en.wikipedia.org/wiki/Derangement