Very nice! Could you enter it in the OEIS? Neil On Sat, Feb 8, 2014 at 1:47 PM, Warren D Smith <warren.wds@gmail.com> wrote:
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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Dear Friends, I have now retired from AT&T. New coordinates: Neil J. A. Sloane, President, OEIS Foundation 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com