[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}.

Source text last modified Tue May 5 08:49:54 1998.

This page generated on Thu May 7 14:25:03 1998 by SiteWeaver.

Contact our webmaster at rebelsky@math.grin.edu