|
%I #19 Feb 15 2014 07:51:07
%S 0,0,1,2,10,32,232,992,10096,53408,727360,4569536,79501696,578101376,
%T 12337163008,101945840384,2582987522560,23913303638528,
%U 701604503968768,7194776722623488,239847438803052544,2698941227297687552,100744097104231198720,1234263151585971974144,50993324690816940089344
%N Number of n-permutations which fix at least one odd prefix.
%D Warren D. Smith, Postings to Math Fun Mailing List, Feb 06 2014 - Feb 08 2014.
%H Vaclav Kotesovec, <a href="/A236921/b236921.txt">Table of n, a(n) for n = 0..440</a>
%F a(0)=a(1)=0; a(n) = Sum_(k=1,3,5,..., whichever is odd among {n-1, n-2}) (k!-a(k))*(n-k)!.
%F To see why this recurrence holds, enumerate all the a(n) permutations of {1,2,3,...,n} which fix an odd prefix. They are:
%F perms of form their count
%F 1... (n-1)!
%F (123)... (3!-2)*(n-3)! where we count only the ones not of the preceding form; that is, (3!-a(3))*(n-3)!
%F (12345)... (5!-a(5))*(n-5)! where again count only those not of preceding two forms,
%F and so on. [_Warren D. Smith_]
%F a(n) ~ (3+(-1)^n)/2 * (n-1)!. - _Vaclav Kotesovec_, Feb 15 2014
%p F := array(1..66);F[1] := 0;
%p F[2] := 1;
%p for n from 3 to 66 do
%p F[n] := sum( ((2*j+1)! - F[2*j+1]) * (n-(2*j+1))!, j=0 .. (n-2)/2 );
%p od; # From _Warren D. Smith_, Feb 12 2014
%K nonn
%O 0,4
%A _N. J. A. Sloane_, Feb 11 2014
|
