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 letter 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^{n} since each element is either included in the subset
or it isn't.

In the Object Server, 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_{2}b_{1} 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_{1},s_{2},...,s_{k}} of its elements.

The number of subsets of an *n*-set for
*n* = 0,1,2,...,10, is
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024.
These, of course, are the powers of 2.
This is sequence
**A000079**(M1129) in
Neil J. Sloane's
database
of integer sequences.

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 the towers of Hanoi puzzle, the problem is to move all disks from one peg to some other peg, subject to two rules. First, only one disk can move at each step. Secondly, a larger disk may not be placed atop a smaller disk.

Edouard Lucas invented the Towers of Hanoi in 1883.

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

Bitstringn···321 |
Subsets | Bitchanges | Towers of Hanoi | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

000 |
{} |
1 |
|||||||||||||

001 |
{1} |
2 |
|||||||||||||

011 |
{1,2} |
1 |
|||||||||||||

010 |
{2} |
3 |
|||||||||||||

110 |
{2,3} |
1 |
|||||||||||||

111 |
{1,2,3} |
2 |
|||||||||||||

101 |
{1,3} |
1 |
|||||||||||||

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 disk being
moved, with the convention that the smallest disk is 1, and the largest is
3 (and, in general, that the largest disk is *n*).

- Alexander Bogomolny's site on
Interactive Mathematics Miscellany and Puzzles
contains a java applet for solving the Towers of Hanoi puzzle for
2 <=
*n*<= 8 and contains a very clear explanation of why 2^{n}-1 is the least possible number of moves in any solution. - Eric's treasure trove of mathematics: contains definitions of Towers of Hanoi, Hanoi graph, Gray code.

Here we show a beautiful symmetric Venn diagram made from 5 congruent ellipses. Branko Grunbaum, a mathematician ot the University of Washington, was the first to show that there are symmetric Venn diagrams made from 5 congruent ellipses. The first diagram labels each region (except the very smallest, where the labels wouldn't fit) with the labels of all the ellipses that contain that region. On the right, the ellipses are colored according to the number of ellipses in which they are contained: grey = 0, yellow = 1, red = 2, blue = 3, green = 4, black = 5. Note that the number of regions colored with a given color corresponds to the appropriate binomial coefficient: #(grey) = #(black) = 1, #(yellow) = #(green) = 5, and #(red) = #(blue) = 10. For more on Venn diagrams see the Venn diagram page.

Programs available:

- Subsets in lexicographic order: Pascal program ; C program .
- Subsets in Gray code order: Pascal program ; C program .
- Product space in lexicographic order: Pascal program ; C program .
- Product space in Gray code order: Pascal program ; C program .

(Please note that the suffix XXXX must be removed from the preceeding email address.)

It was last updated Wednesday, 10-May-2006 10:32:13 PDT.

There have been 41110 visitors to this page since May 16, 2000 .

©Frank Ruskey, 1995-2003.