We want to line up our six children for a photograph, but we can’t put Sally and John next to one another because they fight. In how many ways can we arrange the photo with this constraint?
|SelectClick for Answer>|
Solving this directly would require finding all the arrangements in which Sally and John are not side by side — 10 different cases, as it turns out.
But another way is to consider the opposite problem: What if Sally and John are required to stand side by side? That amounts to treating them as one child, though we must remember that there are two ways to “attach” them, Sally & John or John & Sally. Five children can be arranged in 5 × 4 × 3 × 2 × 1 = 5! = 120 ways, so there are 2 × 120 = 240 ways to arrange the six children so that Sally and John will be side by side.
Going back to the original problem, there would be 6 × 5 × 4 × 3 × 2 × 1 = 720 ways to arrange the six children if there were no constraints at all, so there must be 720 – 240 = 480 ways to line them up if Sally and John are to be kept apart.
(Shawn Godin, “Pólya’s Paragon: Au Contraire, Mon Ami,” Crux Mathematicorum 30:1 [February 2004], 13-15.)
02/09/2020 UPDATE: Remarkably, Marin Mersenne addressed the same question in his 1636 musical treatise Harmonie universelle. Reader Jon Wild explains that in a section on combinatorics, Mersenne asks how many ways there are of forming non-repeating melodies from the six notes of the hexachord ut-re-mi-fa-sol-la, then asks how many are “good,” which for him means they do not contain the interval (ascending or descending) of a major sixth, found between “ut” and “la.” He follows the same reasoning to the same answer, that 240 of the 720 melodies must be ruled out.
He actually writes out all 720 permutations, then explains that some of them are bad because they contain “ut la” or “la ut” (which is disagreeable, hard to sing, and painful to the ear, and whose frequency ratios are objectionable on numerological grounds). 120 of the listed permutations include the major sixth ascending and 120 descending; subtracting these from the 720 listed permutations leaves 480 good melodies.
(Marin Mersenne, Harmonie universelle, 1636, Proposition 9 from the “Deuxième livre des chants” [second book on Melody].) (Thanks, Jon.)