0,4

Original definition: Number of permutations with no hits on 2 main diagonals. (Identical to definition of A000316.) - M. F. Hasler, Sep 27 2015

Card-matching numbers (Dinner-Diner matching numbers): A deck has n kinds of cards, 2 of each kind. The deck is shuffled and dealt in to n hands with 2 cards each. A match occurs for every card in the j-th hand of kind j. A(n) is the number of ways of achieving no matches. The probability of no matches is A(n)/((2n)!/2!^n).

Also, Penrice's Christmas gift numbers (see Penrice 1991).

a(n) is the maximal number of totally mixed Nash equilibria in games of n players, each with 3 pure options. - Raimundas Vidunas, Jan 22 2014

F. N. David and D. E. Barton, Combinatorial Chance, Hafner, NY, 1962, Ch. 7 and Ch. 12.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, pp. 174-178.

R. P. Stanley, Enumerative Combinatorics Volume I, Cambridge University Press, 1997, p. 71.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..100

Per Alexandersson and Frether Getachew, An involution on derangements, arXiv:2105.08455 [math.CO], 2021.

Shalosh B. Ekhad, Christoph Koutschan, and Doron Zeilberger, There are EXACTLY 1493804444499093354916284290188948031229880469556 Ways to Derange a Standard Deck of Cards (ignoring suits) [and many other such useful facts], arXiv:2101.10147 [math.CO], 2021.

F. F. Knudsen and I. Skau, On the Asymptotic Solution of a Card-Matching Problem, Mathematics Magazine 69 (1996), 190-197.

P. A. MacMahon, Combinatory Analysis Cambridge: The University Press 1915-1916

B. H. Margolius, The Dinner-Diner Matching Problem, Mathematics Magazine, 76 (2003), 107-118.

B. H. Margolius, Dinner-Diner Matching Probabilities

R. D. McKelvey and A. McLennan, The maximal number of regular totally mixed Nash equilibria, J. Economic Theory, 72:411--425, 1997.

L. I. Nicolaescu, Derangements and asymptotics of the Laplace transforms of large powers of a polynomial, New York J. Math. 10 (2004) 117-131.

S. G. Penrice, Derangements, permanents and Christmas presents, The American Mathematical Monthly 98 (1991), 617-620.

John Riordan and N. J. A. Sloane, Correspondence, 1974

R. Vidunas, Counting derangements and Nash equilibria, arXiv preprint arXiv:1401.5400 [math.CO], 2014-2016.

Raimundas Vidunas, Counting derangements and Nash equilibria Ann. Comb. 21, No. 1, 131-152 (2017).

Wikipedia, Permutations of multisets

a(n) = A000316(n)/2^n.

a(n) = Sum_{k=0..n} Sum_{m=0..n-k} (-1)^k * n!/(k!*m!*(n-k-m)!) * 2^(2*k+m-n) * (2*n-2*m-k)!. - Max Alekseyev, Oct 06 2016

G.f.: Sum_{j=0..n*k} coeff(R(x, n, k), x, j)*(t-1)^j*(n*k-j)! where n is the number of kinds of cards, k is the number of cards of each kind (2 in this case) and coeff(R(x, n, k), x, j) is the coefficient of x^j of the rook polynomial R(x, n, k) = (k!^2*sum(x^j/((k-j)!^2*j!))^n (see Riordan or Stanley).

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

a(n) = round(2^(n/2 + 3/4)*Pi^(-1/2)*exp(-2)*n!*BesselK(1/2+n,2^(1/2))). - Mark van Hoeij, Oct 30 2011

(2*n+3)*a(n+3)=(2*n+5)^2*(n+2)*a(n+2)+(2*n+3)*(n+2)*a(n+1)-2*(2*n+5)*(n+1)*(n+2)*a(n). - Vaclav Kotesovec, Aug 31 2012

Asymptotic: a(n) ~ n^(2*n)*2^(n+1)*sqrt(Pi*n)/exp(2*n+2), Vaclav Kotesovec, Aug 31 2012

a(n) = (1/2^n)*A000316(n) = int_{0..inf} exp(-x)*(1/2*x^2 - 2*x + 1)^n dx. Asymptotic: a(n) ~ ((2*n)!/2^n)*exp(-2)*( 1 - 1/(2*n) - 23/(96*n^2) + O(1/n^3) ). See Nicolaescu. - Peter Bala, Jul 07 2014

Let S = x_1 + ... + x_n. a(n) equals the coefficient of (x_1*...*x_n)^2 in the expansion of product {i = 1..n} (S - x_i)^2 (MacMahon, Chapter III). - Peter Bala, Jul 08 2014

Conjecture: a(n+k) - a(n) is divisible by k. - Mark van Hoeij, Nov 15 2023

There are 297 ways of achieving zero matches when there are 2 cards of each kind and 4 kinds of card so a(4)=297.

From Peter Bala, Jul 08 2014: (Start)

a(3) = 10: the 10 permutations of the multiset {1,1,2,2,3,3} that have no fixed points are

{2,2,3,3,1,1}, {3,3,1,1,2,2}

{2,3,1,3,1,2}, {2,3,1,3,2,1}

{2,3,3,1,1,2}, {2,3,3,1,2,1}

{3,2,1,3,1,2}, {3,2,1,3,2,1}

{3,2,3,1,1,2}, {3,2,3,1,2,1}

(End)

p := (x, k)->k!^2*sum(x^j/((k-j)!^2*j!), j=0..k); R := (x, n, k)->p(x, k)^n; f := (t, n, k)->sum(coeff(R(x, n, k), x, j)*(t-1)^j*(n*k-j)!, j=0..n*k); seq(f(0, n, 2)/2!^n, n=0..18);

RecurrenceTable[{(2*n+3)*a[n+3]==(2*n+5)^2*(n+2)*a[n+2]+(2*n+3)*(n+2)*a[n+1]-2*(2*n+5)*(n+1)*(n+2)*a[n], a[1]==0, a[2]==1, a[3]==10}, a, {n, 1, 25}] (* Vaclav Kotesovec, Aug 31 2012 *)

a[n_] := a[n] = n*(2*n-1)*a[n-1] + 2*n*(n-1)*a[n-2] - (2*n-1); a[0] = 1; a[1] = 0; a[2] = 1; Table[a[n], {n, 0, 14}] (* Jean-François Alcover, Mar 04 2013 *)

a[n_] := Sum[(2*(n-m))! / 2^(n-m) Binomial[n, m] Hypergeometric1F1[m-n, 2*(m - n), -4], {m, 0, n}]; Table[a[n], {n, 0, 16}] (* Peter Luschny, Nov 15 2023 *)

(Magma) I:=[0, 1]; [n le 2 select I[n] else n*(2*n-1)*Self(n-1)+2*n*(n-1)*Self(n-2)-(2*n-1): n in [1..30]]; // Vincenzo Librandi, Sep 28 2015

(PARI) a(n) = (2^n*round(2^(n/2+3/4)*Pi^(-1/2)*exp(-2)*n!*besselk(1/2+n, 2^(1/2))))/2^n;

vector(15, n, a(n))\\ Altug Alkan, Sep 28 2015

(PARI) { A000459(n) = sum(m=0, n, sum(k=0, n-m, (-1)^k * binomial(n, k) * binomial(n-k, m) * 2^(2*k+m-n) * (2*n-2*m-k)! )); } \\ Max Alekseyev, Oct 06 2016

Cf. A000166, A008290, A059056-A059071, A033581, A059073.

Row n=2 of A372307.

Sequence in context: A386965 A239775 A059072 * A125288 A217487 A173479

Adjacent sequences: A000456 A000457 A000458 * A000460 A000461 A000462

nonn,nice,easy

More terms and edited by Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Dec 22 2000

Edited by M. F. Hasler, Sep 27 2015

a(0)=1 prepended by Max Alekseyev, Oct 06 2016

approved