I found the recurrence which had been eluding me. Let F(n) be the number of n-permutations which fix at least one odd-prefix. Start with F(0)=F(1)=0. Then I claim: F(n) = SUM(k=1,3,5,..., whichever is odd among{n-1, n-2})OF (k!-F(k))*(n-k)! is the magic recurrence from which all counts F(n), for every n>1, arise. Checking the first few cases manually: F(0)=0 F(1)=0 F(2)=1 F(3)=2 F(4)=6+4=10 F(5)=24+4*2=32 F(6)=120+4*6+88=232 F(7)=720+4*24+88*2=992 and those all indeed do agree with my computer counts. To see why this recurrence holds, enumerate all the F(n) permutations of {1,2,3,...,n} which fix an odd prefix. They are: perms of form their count 1... (n-1)! (123)... (3!-2)*(n-3)! where only counting the ones not of preceding form; that is, (3!-F(3))*(n-3)! (12345)... (5!-F(5))*(n-5)! where again only counting the ones not of preceding two forms and so on.