Skip to main content
2 of 3
added ref-req tag
Benjamin Dickman
  • 7.8k
  • 2
  • 47
  • 89

Enumerating subsets with no triple appearing together more than once

This question is motivated by a real-world application related to an art project that involves displaying images, but my search hit a dead end after finding the wikipage about Kirkman systems (other related terms include Steiner systems and the Social golfer problem) and looking over references linked there. A few people have written programs for this specific question that established lower bounds (so: more than $2100$) but none has found an exact answer.

The question is:

Given a set of $40$ elements, what is the maximum number of subsets that can be created such that no triple appears more than once?

(For example, if the set includes $A,B,C,D,E$ as elements, then one cannot include in the collection of subsets both $\{A,B,C,D\}$ and $\{A,B,C,E\}$ since, in this scenario, we would have the triple $A,B,C$ appearing more than once.)

As an excerpt from the History section of the aforelinked wikipage, there is under the first bullet point a question attributed to Wesley Woolhouse (1844):

"Determine the number of combinations that can be made out of $n$ symbols, $p$ symbols in each; with this limitation, that no combination of $q$ symbols, which may appear in any one of them shall be repeated in any other."

followed by the formula:

$$\frac{n!}{q!(n-q)!)} \div \frac{p!}{q!(p-q)!}$$

Unfortunately, one finds that this formula is false already for small examples (e.g. $n=5, p=4, q=3$) and, indeed, reading further on that page indicates that the formula only holds in certain scenarios.

Rephrased, I am looking for an answer to Woolhouse's question for the case of $n=40, p=4, q=3$ either by a counting argument, an effective program, or a reference. Please tag/retag as appropriate; thanks!

Benjamin Dickman
  • 7.8k
  • 2
  • 47
  • 89