Concept
Kirkman's schoolgirl problem is a problem in combinatorics proposed by Thomas Penyngton Kirkman in 1850 as Query VI in The Lady's and Gentleman's Diary (pg.48). The problem states: Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk twice abreast. A solution to this problem is an example of a Kirkman triple system, which is a Steiner triple system having a parallelism, that is, a partition of the blocks of the triple system into parallel classes which are themselves partitions of the points into disjoint blocks. Such Steiner systems that have a parallelism are also called resolvable. There are exactly seven non-isomorphic solutions to the schoolgirl problem, as originally listed by Frank Nelson Cole in Kirkman Parades in 1922. The seven solutions are summarized in the table below, denoting the 15 girls with the letters A to O. From the number of automorphisms for each solution and the definition of an automorphism group, the total number of solutions including isomorphic solutions is therefore: The problem has a long and storied history. This section is based on historical work done at different times by Robin Wilson and by Louise Duffield Cummings. The history is as follows: In 1844, Wesley Woolhouse, the editor of The Lady's and Gentleman's Diary at the time, asked the general question: "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." Only two answers were received, one incorrect and the other correctly answering the question with . As the question did not ask for anything more than the number of combinations, nothing was received about the conditions on n, p, or q when such a solution could be achieved. In 1846, Woolhouse asked: "How many triads can be made out of n symbols, so that no pair of symbols shall be comprised more than once among them?".
