Information on Subsets of a Set

Description of the Problem

How did the concept of number arise? Imagine explaining the number "three" to a two year old. You would take collections of three oranges, three crayons, three blocks, and three cookies, and then try to get them to see the common feature of each of those collections of objects. Each of those collections is a set, a set containing three elements. Mathematicians also use sets to define the number concept. One of the most useful operations on sets is to take all of its subsets, each possible sub-collection of the original collection. AMOF can list all subsets of a finite set in a variety of ways.

A set is a collection of objects, and a subset is a sub-collection of those objects. For example if the collection consists of the three letters A, B, and C, written as {A,B,C}, then the possible subcollections are {}, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, and {A,B,C}. The number of subsets of an n element set is 2ⁿ since each element is either included in the subset or it isn't. For n = 0,1,2,...,10, the value of 2ⁿ is 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. These, of course, are the powers of 2.

Gray Codes

In Gray code order successive subsets differ by exactly one element. There are many such Gray codes; the one we use is called The Binary Reflected Gray Code (or BRGC). The transition sequence of the BRGC is the sequence of positions of the bits that change. For n = 3 it is 1,2,1,3,1,2,1. Inductively, the sequence is defined as T(n+1) = T(n),n+1,T(n), with T(1) = 1. It is this sequence that is output when "transposition or bit change" output is selected.

Towers of Hanoi

In the Towers of Hanoi puzzle, the problem is to move all discs from one peg to one of the two other pegs, subject to two rules. First, only one disc can move at each step. Secondly, a larger disc may not be placed atop a smaller disc. It is also desirable that the least number of moves be used in moving all discs from one peg to the other peg.

There is a surprising connection between the BRGC and optimal (least number of moves) solutions to the Towers of Hanoi problem.

Example

This is the output of Gray Code order with n = 3 and all output options selected.

000

{}

001

{1}

011

{1,2}

010

{2}

110

{2,3}

111

{1,2,3}

101

{1,3}

100

{3}

This correspondence is best illustrated by looking at an example, such as the table above. Note that the number in the bitchange column corresponds to the the disc being moved, with the convention that the smallest disc is 1, and the largest is 3 (and, in general, that the largest disc is n).

A Brief History

Counting in Binary

The famous mathematician, Baron Gottfried Wilhelm von Leibnitz thought that he had invented the binary number system late in the 17th century. However, he was very surprised to learn that in the 11th century the Chinese scholar Fu Hsi had arranged the 64 hexagrams of the I Ching in lexicographic order. You get this same list that AMOF produces when bitstrings are output and n=6.

The Chinese also knew of "Pascal's Triangle" before Pascal. In Chu Shih-chieh's Precious Mirror of the Four Elements (1300) there is a diagram that is clearly the first part of Pascal's triangle.

Hindu mathematicians also knew of the triangle, well before Pascal.

The Binary Reflected Gray Code

In the 1940's, Frank Gray, an American engineer at Bell Laboratories, developed a method for "pulse code communication" whose key idea was a way of listing all strings of 0's and 1's of a given length so that successive strings differed by only one bit. Such an encoding was used to help minimize the effect of errors that could arise in transmitting signals in electronic communication systems. Gray published the code in his 1953 patent. He used the term "reflected code" for the first time in this patent, and hence the name "Binary Reflected Gray Code".

There were earlier applications of what is now known as the Gray code in the late nineteenth century. In 1872, the code was applied to solve a classic puzzle known as the Chinese rings. Also in the late 1800's, a French engineer, Emile Baudot, applied the code to telegraphy.

The Towers of Hanoi Puzzle

Towers of Hanoi Puzzle was invented in 1883 by Edouard Lucas, a French mathematician. This puzzle was originally sold as a toy, and was described as a simplified version of the "Tower of Brahma."

The legend has it that the mythical Tower of Brahma, in the Indian city of Benares, has a post with 64 gold discs stacked in decreasing sizes. These discs are said to be moved, one at a time, by the priests of the Hindu temple from the original post to one of the other two posts, with a larger disc never being placed on top of a smaller disc. It was said that by the time all 64 discs have been transferred to another post in the original order, the temple will crumble to dust and the earth would disappear.

At the rate of moving 1 disc per second around the clock, it is estimated to take about 585 billion years to complete the transfer of the gold discs in the Tower of Brahma. This was calculated using the formula: X = 2ⁿ - 1, where X is the number of moves required and where n is the number of discs to be moved.

Applications to Mathematics and Other Areas

Sets and subsets permeate the fabric of mathematics. Mathematics is the science of patterns and subsets are one of the most fundamental of all patterns. It is not surprising, therefore, that subsets occur in most of mathematics. A knowledge of sets and subsets is necessary for understanding basic concepts of any branch of mathematics.

Counting in Binary

The binary number system is of fundamental importance in todays digital world, and one of the easiest ways to become acquainted with it is to learn to count in binary. This is exactly what AMOF does when you generate subsets in lexicographic order (with bitstring output).

The Binary Reflected Gray Code

The Gray code has many applications. Its primary application is in greatly increasing the accuracy of counting scales of analog-to-digital converters. An odometer in the car is an example of a analog-to-digital converter. There is little chance of error in converting an odometer reading to digital form because the wheels move slowly. However, there are other examples, such as wind-tunnel simulations of airplanes and guided missiles, and position detection of rotating shafts, where the variables being measured fluctuate rapidly and must be translated almost instantly into a digital output signal. Counting by Gray code significantly reduces the likelihood of errors by changing only one digit of the counter by only one unit at each step.

Towers of Hanoi

The Towers of Hanoi is often used to illustrate recursion, an important capability of all modern programming languages.

Explanation of AMOF implementation

In AMOF, the set from which subsets are made is always the set [n] of the first n positive integers (i.e., [n] = {1,2,...,n}). If bitstring output is selected, then each subset S is listed as a bitstring b_n��b₂b₁ where b_i = 1 if i is in S and b_i = 0 if i is not in S. If subset output is selected, then each subset S (say of size k) is output as an ordered list ${s$ ₁,s₂,...,s_k} of its elements.

For lex (lexicographic) order, the algorithm used is well-known, and amounts to simply counting in binary. Far more interesting is Gray code order.

In AMOF you select either to generate in lexicographic order or in Gray code order. The only input parameter in either case is n. Output can be a list of elements of the subsets and/or the equivalent bitstring representation. If Gray code order is selected then you may also ask for the transition sequence or Towers of Hanoi to be output. However, you must limit n to less than 8 when requesting Towers of Hanoi output. There is a current limit of 200 solutions, and n=8 requires more than 200 moves. This is particularly important to remember when requesting output in Towers of Hanoi because it takes a long time for many browsers to render solutions with a large number of gifs in a table, and it might be a while before you get a message saying that you have exceeded the current limit of 200 solutions.

The actual implementation consists of two similar recursive procedures, one for lex order and one for Gray code order. Below we show the algorithm used for lex order.

proc gen( n )
  if n = 0 then PrintIt
  else {
     A[n] = 0;  gen( n-1 );
     A[n] = 1;  gen( n-1 );
  }

In the Classroom

If there is any single concept that underlies all of mathematics, it is the set concept. It is important that students learn to work with sets and subsets at all levels of the curriculum. In [NCTM] an exploration of set concepts is advocated in the chapter entitled "Strengthening a K-8 Mathematics Program".

The Towers of Hanoi puzzle is an obvious choice for a manipulative to use in the classroom. But different size coins or blocks may be used instead of the discs, and three sheets of paper or three circles drawn on a piece of paper to indicate the three pegs.

Try solving the puzzle. Count the number of moves required to complete the transfer. Then calculate the minimum number of moves required using the formula: X = 2ⁿ - 1 , where X is the number of moves, and where n is the number of discs. The puzzle becomes more difficult and takes many more moves the more discs you have.

In a book written for elementary school teachers of mathematics, this puzzle using three coins is given as a problem solving activity that can be done in the classroom. It also asks the solution to the Tower of Brahma problem, i.e., how long would it take to transfer all 64 discs at a rate of one move per second? The solution can be found using the above formula, as we have already done in the section on History. You can use the formula, and with the help of a calculator, try to find a solution for n=64 or for any value of n. In [NCTM] the Towers of Hanoi puzzle is used to illustrate concepts of recursion.

You can use AMOF to generate solutions for different numbers of discs. It not only returns the minimum number of total moves required to solve the puzzle, but also generates the actual configuration at each move and can displays the corresponding subsets. Remember that n can be at most 8 when displaying the Towers of Hanoi in AMOF.

Chinese Rings puzzle is another possible choice for a manipulative to use in the classroom to learn how the Binary Reflected Gray Code works, since the Gray code solves this puzzle.

Questions for discussion:

Why are the number of subsets containing an even number of elements equal in number to those containing an odd number of elements?

Links to Other Relevant Sites and Sources of Information

The Object Server allows you to generate not only subsets but some of their generalizations and contains further material on subsets.
Combinatorics Topics for K-8 Teachers: a set of course notes discussing the number of subsets of a set.
A short explanation of Venn Diagrams.
Another page about John Venn and Venn Diagrams.
A short discussion of the mathematics of the Chinese Rings Puzzle.
A short discussion on Gray Codes
A photo of a puzzle which has a Gray Code solution.
A Towers of Hanoi solver written in java (requires java enabled browser).
Another Towers of Hanoi solver in java. This one allows you to move the discs with the mouse.