Robert Baillie asks: << . . . the same 9 topics, in the same order, except with items 6 and 9 reversed. Let's assume that there are only these 9 topics to choose from. What is the probability that . . . ?

...

I'll answer the question I think was intended: Question: Given a random permutation of {1,...,9}, what is the probability that it moves at most 2 symbols? The # of perms. moving 0 symbols is 1. No perm. can move only 1 symbol. The number of pairs of symbols is 9*8/2 = 36. For each pair, the number of perms. interchanging the pair but moving no other symbols is 1. Thus the answer is 37/9! = 37/362880 = 1.01962+ x 10^(-4) or about 1 out of 10,000. ***************************************************** Statistics tries to address questions of the sort that can't really be answered, like "What is the probability that two permutations of {1,...,9} that differ in only 2 places were actually chosen independently?" The basic method is to define the "null hypothesis" as the assumption that the two perms. were in fact chosen independently. Then (before examining the data) an "N% confidence interval" is chosen to include events whose probability -- *assuming the null hypothesis* -- is at least N%. N is typically selected to be 5 or 1. The decision procedure is then to accept or reject the null hypothesis "at the N% confidence level" according as the event in question falls inside the N% confidence interval or not. This method was originally designed to deal with events having a normal distribution. In a different situation like this one, defining the "confidence interval" can be a bit of an art. Let d(k) be the number of derangements (perms without any fixed points) of k elements. According to A000166 of Neil Sloane's OEIS, d(n) for n = 0,...,9 is given by n | 0 1 2 3 4 5 6 7 8 9 d(n)| 1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496* The number of permutations of {1,...,9} moving exactly k elements, 0 <= k <= 9 is then #(k) = C(9,k)*d(k). My calculator tells me this sequence is k | 0 1 2 3 4 5 6 7 8 9 #(k) | 1 0 36 168 1134 5544 22260 66744 133497 133496 9-k | 9 8 7 6 5 4 3 2 1 0 (Here 9-k is the number of elements FIXED by #(k) different perms. of {1,...,9}.) Now, how to define an N% confidence interval? I'd start with the average number of fixed elements -- call it Favg -- and move outward to get an interval # fixed elements F lies in the interval I(t) = [Favg-t, Favg+t] for some real number t. The corresponding probabilities are of course #(9-F) for each F, and the P(t) := Prob(F lies in I(t)) = sum{F in I(t)} of #(9-F). Thus choose your confidence level of N% = c, say, and find the largest t such that P(t) <= 1-c. Call it t(c). Then I(t(c)) is your confidence interval at the N% level of confidence. --Dan __________________ * Had I checked, I'd have learned that this is part of A098825 of the OEIS *before* doing the calculation!