A159960 Number of permutations of the set 1,2,..., 2n such that at least one pair of adjacent numbers in the permutation differs by n.

1, 10, 292, 16152, 1443616, 189709600, 34420171584, 8241995095936, 2517637537094656, 955377719901439488, 440888939541736115200, 243144648530111594371072, 157920570527279020394569728, 119308432982412667510831095808, 103738687936577909824307104989184

Offset

1,2

Comments

IMO '89 problem 6 asks to show that a(n) > A002674(n)/2.

Links

G. C. Greubel, Table of n, a(n) for n = 1..220

IMO, International Mathematics Olympia, see 1989, problem 6.

Formula

a(n) = Sum_{k=1..n} (-1)^(k-1)*binomial(2*n-k, k)*binomial(n, k)*2^k*(2*n-2*k)!.

Recurrence: (6*n - 17)*a(n) = 2*(n-1)*(36*n^2 - 156*n + 151)*a(n-1) - 4*(n-1)*(72*n^4 - 636*n^3 + 2062*n^2 - 2909*n + 1511)*a(n-2) + 4*(n-2)*(n-1)*(96*n^5 - 1280*n^4 + 6704*n^3 - 17208*n^2 + 21596*n - 10569)*a(n-3) + 8*(n-3)*(n-2)*(n-1)*(2*n - 7)*(6*n - 11)*a(n-4). - Vaclav Kotesovec, Mar 15 2014

a(n) ~ (1-BesselJ(0,2)) * sqrt(Pi) * 4^n * n^(2*n+1/2) / exp(2*n). - Vaclav Kotesovec, Mar 15 2014

Maple

f := proc (n) add((-1)^(k-1)*binomial(2*n-k, k)*binomial(n, k)*2^k*factorial(2*n-2*k), k = 1 .. n) end proc;

Mathematica

a[n_] := (2*n)!*(1-HypergeometricPFQ[{-n}, {1, -2*n}, -2])/2; Table[a[n], {n, 1, 15}] (* Jean-François Alcover, Jan 27 2014 *)

Prog

(PARI) a(n)=sum(k=1, n, (-1)^(k-1)*binomial(2*n-k, k)*binomial(n, k)<<k*(2*n-2*k)!)/2 \\ Charles R Greathouse IV, Jun 19 2013

Crossrefs

Cf. A002674.

Sequence in context: A222672 A024295 A291658 * A258794 A239775 A059072

Adjacent sequences: A159957 A159958 A159959 * A159961 A159962 A159963

Keyword

easy,nice,nonn

Author

Ji Li (vieplivee(AT)hotmail.com), Apr 28 2009

Status

approved