|
|
A236921
|
|
Number of n-permutations which fix at least one odd prefix.
|
|
1
|
|
|
0, 0, 1, 2, 10, 32, 232, 992, 10096, 53408, 727360, 4569536, 79501696, 578101376, 12337163008, 101945840384, 2582987522560, 23913303638528, 701604503968768, 7194776722623488, 239847438803052544, 2698941227297687552, 100744097104231198720, 1234263151585971974144, 50993324690816940089344
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
REFERENCES
|
Warren D. Smith, Postings to Math Fun Mailing List, Feb 06 2014 - Feb 08 2014.
|
|
LINKS
|
|
|
FORMULA
|
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)!.
To see why this recurrence holds, enumerate all the a(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 we count only the ones not of the preceding form; that is, (3!-a(3))*(n-3)!
(12345)... (5!-a(5))*(n-5)! where again count only those not of preceding two forms,
|
|
MAPLE
|
F := array(1..66); F[1] := 0;
F[2] := 1;
for n from 3 to 66 do
F[n] := sum( ((2*j+1)! - F[2*j+1]) * (n-(2*j+1))!, j=0 .. (n-2)/2 );
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|