Problem:
Determine the number of ways to select a sequence of 8 sets , such that each is a subset (possibly empty) of , and contains if divides .
Solution
Solution:
Consider an arbitrary , and let us consider the number of ways for to be in some of the sets so that the constraints are satisfied. We divide into a few cases:
- Case: . Then cannot be in any of the sets. So there is one possibility.
- Case: but . Then the only other sets that could be in are , and could be in some collection of them. There are 8 possibilities in this case.
- Case: . Then automatically. There are 4 independent choices to be make here: (1) whether ; (2) whether ; (3) whether , and if yes, whether ; (4) whether , and if yes, whether . There are choices here.
Therefore, there are ways to place into some of the sets. Since the choices for and are made independently, we see that the total number of possibilities is .