How to solve combination?

Question

How would I solve the following problem?

I have 3 pairs of shoes, black, white and green.

I need to figure out how many possible patterns there are to wearing them for 10 days where you pick one color each day, you can't wear the same one 2 days in a row and the first and last day has to be different colors.

Thanks

Susie

Answer 1

If we didn't have to worry about the first and last matching, this would be fairly straight forward:

There would be 3 ways to pick the first pair and 2 ways to pick each successive pair so 3*2⁹

But now we have to account for the case where the first and the last match. In other words we need to subtract those cases out.

Let's look at the case where the first 9 do not match but the first and the last do match. So there are 3 * 2⁸ * 1 ways to do the first nine and only one way to choose the last, that is, it must match the first. We have to subtract this out: 3*2⁹ - 3*2⁸

But we have subtracted too much out now because I have subtracted out the case where the first and the ninth match so I have to add that back in 3 * 2⁷ * 1 for the first 8 then one way for the ninth.

Now we have: 3*2⁹ - 3*2⁸ + 3*2⁷

This proceeds and what we have is an alternating series looking like this: 3*∑(-1)^i-1 * 2^n-i for i from 1 to n-1.

Plugging 10 in for n we get 3 * [512 - 256 + 128 - 64 + 32 - 16 + 8 - 4 + 2] = 1026

It is advisable to spend some time thinking about this. Try the case when n = 4, then n = 5. Actually write out all the possibilities. Look for patterns. This is not easy stuff, and an online lesson might be advisable. [512, -256, 128, -64, 32, -16, 8, -4, 2][[512, -256, 128, -64, 32, -16, 8, -4, 2]512, -256, 128, -64, 32, -16, 8, -4, 2]