The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A000459 Number of multiset permutations of {1, 1, 2, 2, ..., n, n} with no fixed points. (Formerly M4750 N2032) 14
 1, 0, 1, 10, 297, 13756, 925705, 85394646, 10351036465, 1596005408152, 305104214112561, 70830194649795010, 19629681235869138841, 6401745422388206166420, 2427004973632598297444857, 1058435896607583305978409166, 526149167104704966948064477665 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS 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 REFERENCES 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). LINKS 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. Vidunas, Raimundas Counting derangements and Nash equilibria Ann. Comb. 21, No. 1, 131-152 (2017). Wikipedia, Permutations of multisets FORMULA 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 EXAMPLE 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) MAPLE 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); MATHEMATICA 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 *) PROG (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 CROSSREFS Cf. A000166, A008290, A059056-A059071, A033581, A059073. Sequence in context: A258794 A239775 A059072 * A125288 A217487 A173479 Adjacent sequences: A000456 A000457 A000458 * A000460 A000461 A000462 KEYWORD nonn,nice,easy AUTHOR EXTENSIONS 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 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified March 31 14:48 EDT 2023. Contains 361663 sequences. (Running on oeis4.)