A033815 Number of standard permutations of [ a_1..a_n b_1..b_n ] (b_i is not immediately followed by a_i, for all i).

1, 1, 14, 426, 24024, 2170680, 287250480, 52370755920, 12585067447680, 3854801333416320, 1465957162768492800, 677696237345719468800, 374281829360322587827200, 243388909697235614324812800, 184070135024053703140543027200, 160192129141963141211280644352000

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

Also turns up as the solution to Problem #18, p. 326 of Alan Tucker's Applied Combinatorics, 4th ed, Wiley NY 2002 [Tucker's `n' is the `2n' here]. - John L Leonard, Sep 15 2003

Number of acyclic orientations of the Turán graph T(2n,n). - Alois P. Heinz, Jan 13 2016

n-th term of the n-th forward differences of n!. - Alois P. Heinz, Feb 22 2019

References

• R. P. Stanley, Enumerative Combinatorics I, Chap.2, Exercise 10, p. 89.

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..200
• Leo Chao, Paul DesJarlais and John L Leonard, A binomial identity, via derangements, Math. Gaz. 89 (2005), 268-270.
• Ira Gessel, Enumerative applications of symmetric functions, Séminaire Lotharingien de Combinatoire, B17a (1987), 17 pp.

Crossrefs

Main diagonal of array in A068106 and of A047920.

Cf. A000142, A002119, A116854, A267383.

Column k=2 of A372326.

Programs

Haskell

a033815 n = a116854 (2 * n + 1) (n + 1)
-- Reinhard Zumkeller, Aug 31 2014

Maple

A033815 := proc(n) local i; add(binomial(n, i)*(-1)^i*(2*n - i)!, i = 0 .. n) end;
# second Maple program:
A:= proc(n, k) A(n, k):= `if`(k=0, n!, A(n+1, k-1) -A(n, k-1)) end:
a:= n-> A(n$2):
seq(a(n), n=0..23);  # Alois P. Heinz, Feb 22 2019

Mathematica

a[n_] := (2n)!*Hypergeometric1F1[-n, -2n, -1]; Table[a[n], {n, 0, 14}] (* Jean-François Alcover, Jun 13 2012, after Vladimir Reshetnikov *)

Formula

a(n) = A002119(n)*n!*(-1)^n.

D-finite with recurrence a(n) = 2n*(2n-1)*a(n-1) + n*(n-1)*a(n-2).

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

From John L Leonard, Sep 15 2003: (Start)

a(n) = Sum_{i=0..n} C(n, i)*(2n-i)!*Sum_{j=0..2n-i} (-1)^j/j!.

a(n) = n!*Sum_{i=0..n} C(n, i)*n!/(n-i)!*Sum_{j=0..n-i} (-1)^j*C(n-i, j)*(n-j)!/i!. (End)

a(n) = Sum_{k=0..n} binomial(n,k)*A000166(n+k). - Vladeta Jovovic, Sep 04 2006

a(n) = A116854(2*n+1,n+1). - Reinhard Zumkeller, Aug 31 2014

a(n) = A267383(2n,n). - Alois P. Heinz, Jan 13 2016

a(n) ~ sqrt(Pi) * 2^(2*n + 1) * n^(2*n + 1/2) / exp(2*n + 1/2). - Vaclav Kotesovec, Feb 18 2017

a(n) = n!*exp(-1/2)*((-1)^n * BesselI(n+1/2,1/2)*Pi^(1/2) + BesselK(n+1/2,1/2)/Pi^(1/2) ). - Mark van Hoeij, Jul 15 2022