Coding Four of Six

[From the notes of Herb Wilf, transcribed by Emily Moore. Modified and extended by Sam Rebelsky.]

A Gray code ordering of a set of subsets is a listing of the subsets so that a subset can be created from the immediately previous subset by replacing exactly one of the elements. For instance, A:{1,2,3,4} could be next to B:{1,3,4,5} since to get from A to B, we simply replace the 2 with a 5. Similarly, both A:{1,2,3,4} and B:{1,3,4,5} could be next to C:{1,3,4,6} since we can get from A to C by replacing the 2 with a 6 and from B to C by replacing the 5 with a 6. However, A:{1,2,3,4} and D:{3,4,5,6} are not next to each other since we would need to replace two elements in A in order to read D.

In this problem, you will work with four-element subsets of S:{1,2,3,4,5,6}.

A. List all of the potential neighbors of {1,2,3,4}.

B. How many such neighbors are there?

C. Is there a subset with fewer neighbors? More?

D. Find a Gray code listing of all of the four-element subsets of S:{1,2,3,4,5,6}.