|
We have shown only two ways in which
the dots might be organized. In fact, there are many possible
ways. There are 10 dots in this example. If we think of these
10 dots as being members of a set, then what we have called a
grouping is simply a partition of this set. The number of possible
partitions of a set of n items is given by something called
a Stirling number, and these numbers can get large very rapidly.
To get some idea of why this is the case, consider something
called the power set. The power set is simply the set of all
possible subsets of a set. For example, the power set of the
the set {x,y,z} is the set { {x,y,z}, {x,y}, {x,z}, {y,z}, {x},
{y}, {z}, {} }. Note that a set is a subset of itself and every
set has the empty set, {}, as a subset. Now, a partition of a
set is simply a selection of a set of subsets such that no element
occurs in more than one of the subsets selected and each element
occurs in one of the selected subsets. For example [ {x,z} ,{y}
] is a partition. Note that there are 8 sets in the power set
of this set of three elements. In general, a set of size n
has 2 to the n subsets. The set of 10 dots below has 2
to the 10 subsets, and then there are all the ways to choose
from these 1024 subsets to form partitions! In case your interested
in seeing a list of the power set of the 10 element set {a,b,c,d,e,f,g,h,i,j},
click here.
The
next example below is similar except that now the dots are arranged
in a diagonal. Again, two of the many possible groupings are
shown with the one that we are biased to use appearing on the
lower left.
|