Newsgroups: sci.math.num-analysis
From: coe@vitsemi.com (Tim Coe)
Subject: Re: groups, subgroups and combinations
Date: Fri, 9 Feb 1996 19:35:26 GMT

In article <163212365wnr@ncc1701.demon.co.uk> STeve@ncc1701.demon.co.uk writes:
>Can anyone assist in this recreational math problem I am attempting to 
>solve? 
>
>I have a collection of n objects. My knowledge of math tells me that I 
>can extract nCr combinations of r objects from this group.
>
>From this group of n I wish to select a subgroup of s objects. From 
>this subsgroup I can extract sCr combinations of r objects.
>
>It's after this point that my mathematical knowledge begins to falter.
>
>Is there a way of calculating the minimum number of such subgroup 
>selections required in order to ensure that, between them, they contain
>*all* nCr combinations. Obviously some subgroups may share one or more
>combinations with the others.
>
>If this can be calculated is there an algorithm which will allow me to
>optimally choose the contents of each subgroup in order to achieve this
>minimum?
>
>As I'm sure my description is probably not totally clear here is a 
>worked example:
>
>n = 10;r = 2;s = 6
>
>Contents of n group: ABCDEFGHIJ
>
>subgroup 1 : ABCDEF
>subgroup 2 : ABCDGH
>subgroup 3 : ABCDIJ
>subgroup 4 : EFGHIJ
>
>Between the above 4 subgroups all combinations of 2 objects
>have been generated.
>
>My math education did not extend beyond high school and I have been 
>knocking my head against walls over this one for several weeks, so 
>any help will be appreciated.
>
>Thanks.
>-- 
>STeve
>
What you have just defined is known as a Steiner System.  Over
the past 100 years there has been extensive mathematical research
done relating to them.  If you are feeling ambitious you can
backtrack references relating to this subject from John Conway's
book "Sphere Packings, Lattices, and Groups".

Off the top of my head I don't know what general results have
been determined but the following five Steiner Systems are
particularly interesting:

n = 11;r = 4;s = 5   66 blocks (this is the name given to your subgroups)
n = 12;r = 5;s = 6   132 blocks
n = 22;r = 3;s = 6   77 blocks
n = 23;r = 4;s = 7   253 blocks
n = 24;r = 5;s = 8   759 blocks

The reason these are interesting is that the automorphisms of
these Steiner Systems drives you deep into that realm of pure
mathematics known as group theory.

Have a happy day,

-Tim Coe          coe@vitsemi.com