A236921 Number of n-permutations which fix at least one odd prefix.

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

Offset

0,4

References

Warren D. Smith, Postings to Math Fun Mailing List, Feb 06 2014 - Feb 08 2014.

Links

Vaclav Kotesovec, Table of n, a(n) for n = 0..440

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,

and so on. [Warren D. Smith]

a(n) ~ (3+(-1)^n)/2 * (n-1)!. - Vaclav Kotesovec, Feb 15 2014

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 );
od; # From Warren D. Smith, Feb 12 2014

Crossrefs

Sequence in context: A329427 A004028 A263839 * A316644 A080668 A062453

Adjacent sequences: A236918 A236919 A236920 * A236922 A236923 A236924

Keyword

nonn

Author

N. J. A. Sloane, Feb 11 2014

Status

approved