[Tutor] Creating lists with definite (n) items without repetitions

[Oscar Benjamin]

On 5 September 2015 at 23:28, Mark Lawrence <breamoreboy at yahoo.co.uk> wrote:
> On 05/09/2015 10:09, Peter Otten wrote:
>>
>>> the 5 lists above do not match my task insofar as every of the 5 lists
>>> contains  'a' and 'b' which should occur only once, hence my count of a
>>> maximum of 301 lists, which might nor be correct 100%. My be one could
>>> put
>>> it in Python as follows:
>>>>
>>>> ('a', 'b', 'c') = True
>>>> ('a', 'b', 'd')= False
>>>> ('a', 'b', 'e')= False
>>>> ('a', 'b', 'f')= False
>>>> ('a', 'b', 'g')= False
>
> So for completeness it follows that:-
>
> ('a', 'c', 'd') == False
> ('b', 'c', 'd') == False
>
> yes?

I think so.

>>> I should probably tell you the real task are a series (maximum ~ 301)
>>> lists in which real names  of people are assigned to the items/letters
>>> for
>>> 2 people(golfers) can be in  the same list(flight)  only once for an
>>> extended period of time.
>>
>
>> It's probably a good idea to ask your question in a mathematics forum --
>> this problem looks common enough to have a name and some brain power spent
>> on it.
>>
>
> To me this is clearly an example of a Steiner Triple system
> associated with Balanced Incomplete Block Design.  Which means I found this
> http://mathforum.org/library/drmath/view/52263.html which got me to
> https://en.wikipedia.org/wiki/Steiner_system and also
> http://oeis.org/A137348/a137348.txt.  Just one minor little question, am I
> actually correct?

It sounds like the social golfer problem (or Kirkman's schoolgirl
problem, both of which Steiner systems):
http://mathworld.wolfram.com/SocialGolferProblem.html

The problem is that there are 26 people and they are divided into
groups of 3 each day. We would like to know if it is possible to
arrange it so that each player plays each other player exactly once
over some period of days.

It is not exactly possible to do this with 26 people in groups of 3.
Think about it from the perspective of 1 person. They must play
against all 25 other people in pairs with neither of the other people
repeated: the set of pairs they play against must partition the set of
other players. Clearly it can only work if the number of other players
is even.

I'm not sure but I think that maybe for an exact solution you need to
have n=1(mod6) or n=3(mod6) which gives:
n = 1, 3, 7, 9, 13, 15, 19, 21, 25, 27, ...

The formula for the number of triples if the exact solution exists is
n*(n-1)/6 which comes out as 26*25/6 = 108.33333 (the formula doesn't
give an integer because the exact solution doesn't exist).

The question is what do you want to do with the leftovers if it's not
possible for every player to play exactly once? Also what do you want
with these triples? Are you just trying to count them?

Are you interested to know which triples come out? It's not unique and
the number of possible sets of triples is massive.

--
Oscar