A combination lock requires three selections of numbers, each from 1 through 38. Suppose the lock is constructed in such a way that no number may be used twice in a row but the same number may occur both first and third. For example, 20 13 20 would be acceptable, but 20 20 13 would not. How many different combinations are possible?

Sol 1. We have to select three numbers. For the first number, there is no restriction. So the number of choices is 39. The second number must be different from the first one. So the number of choices is 38. Finally, the last number has to be different from the second one. So there are 38 possibilities. Therefore, the total number of acceptable combinations is 39 * 38 * 38 = 56316.

Sol 2. Let U be the set of all possible combinations regardless it is acceptable or not. Then |U| = 393 = 59319. Let A be the set of combinations whose first two numbers are same, and let B be the set of combinations whose last two numbers are same. Then the set of non-acceptable combinations is precisely |A∪B|. |A| = |B| = 392. A∩B is the set of combinations whose three numbers are all same. So |A ∩ B| = 39. Therefore |A ∪ B| = |A| + |B| - |A ∩ B| = 392 + 392 - 39 = 3003.

So the number of acceptable combinations is 59319 - 3003 = 56316.