%I M4750 N2032 #116 Aug 27 2024 14:52:39
%S 1,0,1,10,297,13756,925705,85394646,10351036465,1596005408152,
%T 305104214112561,70830194649795010,19629681235869138841,
%U 6401745422388206166420,2427004973632598297444857,1058435896607583305978409166,526149167104704966948064477665
%N Number of multiset permutations of {1, 1, 2, 2, ..., n, n} with no fixed points.
%C Original definition: Number of permutations with no hits on 2 main diagonals. (Identical to definition of A000316.) - _M. F. Hasler_, Sep 27 2015
%C 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).
%C Also, Penrice's Christmas gift numbers (see Penrice 1991).
%C 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
%D F. N. David and D. E. Barton, Combinatorial Chance, Hafner, NY, 1962, Ch. 7 and Ch. 12.
%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, pp. 174-178.
%D R. P. Stanley, Enumerative Combinatorics Volume I, Cambridge University Press, 1997, p. 71.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A000459/b000459.txt">Table of n, a(n) for n = 0..100</a>
%H Per Alexandersson and Frether Getachew, <a href="https://arxiv.org/abs/2105.08455">An involution on derangements</a>, arXiv:2105.08455 [math.CO], 2021.
%H Shalosh B. Ekhad, Christoph Koutschan, and Doron Zeilberger, <a href="https://arxiv.org/abs/2101.10147">There are EXACTLY 1493804444499093354916284290188948031229880469556 Ways to Derange a Standard Deck of Cards (ignoring suits) [and many other such useful facts]</a>, arXiv:2101.10147 [math.CO], 2021.
%H F. F. Knudsen and I. Skau, <a href="http://www.jstor.org/stable/2691467">On the Asymptotic Solution of a Card-Matching Problem</a>, Mathematics Magazine 69 (1996), 190-197.
%H P. A. MacMahon, <a href="https://openlibrary.org/books/OL23289465M/Combinatory_analysis">Combinatory Analysis</a> Cambridge: The University Press 1915-1916
%H B. H. Margolius, <a href="http://www.jstor.org/stable/3219303">The Dinner-Diner Matching Problem</a>, Mathematics Magazine, 76 (2003), 107-118.
%H B. H. Margolius, <a href="http://academic.csuohio.edu/bmargolius/homepage/dinner/dinner/cardentry.htm">Dinner-Diner Matching Probabilities</a>
%H R. D. McKelvey and A. McLennan, <a href="http://dx.doi.org/10.1006/jeth.1996.2214">The maximal number of regular totally mixed Nash equilibria</a>, J. Economic Theory, 72:411--425, 1997.
%H L. I. Nicolaescu, <a href="http://nyjm.albany.edu/j/2004/10-7.pdf">Derangements and asymptotics of the Laplace transforms of large powers of a polynomial</a>, New York J. Math. 10 (2004) 117-131.
%H S. G. Penrice, <a href="https://www.jstor.org/stable/2324927">Derangements, permanents and Christmas presents</a>, The American Mathematical Monthly 98 (1991), 617-620.
%H John Riordan and N. J. A. Sloane, <a href="/A003471/a003471_1.pdf">Correspondence, 1974</a>
%H R. Vidunas, <a href="http://arxiv.org/abs/1401.5400">Counting derangements and Nash equilibria</a>, arXiv preprint arXiv:1401.5400 [math.CO], 2014-2016.
%H Raimundas Vidunas, <a href="https://doi.org/10.1007/s00026-017-0344-2">Counting derangements and Nash equilibria</a> Ann. Comb. 21, No. 1, 131-152 (2017).
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation#Permutations_of_multisets">Permutations of multisets</a>
%H <a href="/index/Ca#cardmatch">Index entries for sequences related to card matching</a>
%F a(n) = A000316(n)/2^n.
%F 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
%F 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).
%F 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.
%F 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
%F (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
%F Asymptotic: a(n) ~ n^(2*n)*2^(n+1)*sqrt(Pi*n)/exp(2*n+2), _Vaclav Kotesovec_, Aug 31 2012
%F 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
%F 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
%F Conjecture: a(n+k) - a(n) is divisible by k. - _Mark van Hoeij_, Nov 15 2023
%e 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.
%e From _Peter Bala_, Jul 08 2014: (Start)
%e a(3) = 10: the 10 permutations of the multiset {1,1,2,2,3,3} that have no fixed points are
%e {2,2,3,3,1,1}, {3,3,1,1,2,2}
%e {2,3,1,3,1,2}, {2,3,1,3,2,1}
%e {2,3,3,1,1,2}, {2,3,3,1,2,1}
%e {3,2,1,3,1,2}, {3,2,1,3,2,1}
%e {3,2,3,1,1,2}, {3,2,3,1,2,1}
%e (End)
%p 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);
%t 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 *)
%t 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 *)
%t 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 *)
%o (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
%o (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;
%o vector(15, n, a(n))\\ _Altug Alkan_, Sep 28 2015
%o (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
%Y Cf. A000166, A008290, A059056-A059071, A033581, A059073.
%Y Row n=2 of A372307.
%K nonn,nice,easy
%O 0,4
%A _N. J. A. Sloane_
%E More terms and edited by Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Dec 22 2000
%E Edited by _M. F. Hasler_, Sep 27 2015
%E a(0)=1 prepended by _Max Alekseyev_, Oct 06 2016