lew@ihuxr.UUCP (08/30/83)
This really is an old problem. It even has a name - in French yet. It is the "problemes de recontres" (mangled I'm sure) or the "problem of recurrence". Euler solved it. It is described in Riordan's book on Combinatorics. He uses it as an example of the principle of inclusion and exclusion (like fortunately, unfortunately.) I remember that Riordan got in a little wit with the remark, "suppose that the letters are scattered at random by the wind, a small child, or some other demonic force." I got interested in this one because of "cryptoquote" puzzles. These permute the letters of the alphabet to make a code, except that no letter ever stands for itself. I got to wondering what fraction of the 26! permutations could still be used with this restriction. I went to incredible lengths to solve it. I wrote a recursive program to generate all the partitions of 26 which don't contain the number 1. (Each partition corresponds to an invariant subgroup of the permutations of 26 things.) The program generated a formula for the number of elements in each subgroup in dc fromat. I then piped the output through dc which evaluated the expressions and added them up. The answer looked kind of familiar, so I looked up Riordan's book and found out what I dummy I was. Lew Mammel, Jr. ihuxr!lew