W.S.B. Woolhouse in 1844 posed the following problem in the Lady's and Gentlemen's Diary:

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.

Readers were invited to send their solution. One solution was $\binom{n}{q}/\binom{p}{q}$ which was deemed wrong as it considered that all $q$-combinations appeared in some $p$-combination. (Source)

How was the incorrect solution obtained?


This answer gives an upper bound on the number of blocks (the subsets of size $p$). This upper bound is only sometimes achieved:

  • e.g., if we try $n=5$, $p=3$ and $q=2$, then the formula gives $$\frac{\binom{5}{2}}{\binom{3}{2}}=\frac{10}{3}$$ which is not even a whole number.

  • e.g., if we try $n=7$, $p=3$ and $q=2$, then the formula gives $$\frac{\binom{7}{2}}{\binom{3}{2}}=7$$ which is the number of blocks in the Steiner Triple System illustrated below (image source Wikipedia):

    enter image description here

Finding when the bound is achieved is still an active area of research in design theory (and I'd probably not be able to give it justice here).

  • $\begingroup$ Thanks, but this does not really answer my question. I want to know how the upper bound is derived. $\endgroup$ – Shahab Feb 2 '14 at 10:24
  • $\begingroup$ There are $\binom{n}{q}$ distinct $q$-subsets of an $n$-set and each block has size $p$, so covers $\binom{p}{q}$. $\endgroup$ – Rebecca J. Stones Feb 2 '14 at 10:51
  • $\begingroup$ Is the original problem as yet unsolved? $\endgroup$ – Shahab Feb 19 '14 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.