# An old counting problem in combinatorics

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?

## 1 Answer

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):

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).

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