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

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A059074 Number of derangements of a multiset comprising 4 repeats of an n-element set. 2
 1, 0, 1, 346, 748521, 3993445276, 45131501617225, 964363228180815366, 35780355973270898382001, 2158610844939711892526650456, 201028342764877992289387752167601, 27708893753238763155350683269145066450, 5459844285803153226360263675364357481841881 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS Previous name was: Card-matching numbers (Dinner-Diner matching numbers). A deck has n kinds of cards, 4 of each kind. The deck is shuffled and dealt in to n hands with 4 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)/((4n)!/4!^n). Number of fixed-point-free permutations of n distinct letters (ABCD...), each of which appears 4 times: 1111, 11112222, 111122223333, 1111222233334444, etc. If there is only one letter of each type we get A000166 - Zerinvary Lajos, Nov 05 2006 a(n) is the maximal number of totally mixed Nash equilibria in games of n players, each with 5 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. R.D. McKelvey and A. McLennan, The maximal number of regular totally mixed Nash equilibria, J. Economic Theory, 72:411-425, 1997. S. G. Penrice, Derangements, permanents and Christmas presents, The American Mathematical Monthly 98(1991), 617-620. 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. LINKS Michael De Vlieger, Table of n, a(n) for n = 0..100 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. Shalosh B. Ekhad, Terms and recurrences for multiset derangements. S. Even and J. Gillis, Derangements and Laguerre polynomials, Mathematical Proceedings of the Cambridge Philosophical Society, Volume 79, Issue 1, January 1976, pp. 135-143. F. F. Knudsen and I. Skau, On the Asymptotic Solution of a Card-Matching Problem, Mathematics Magazine 69 (1996), 190-197. Barbara H. Margolius, The Dinner-Diner Matching Problem, Mathematics Magazine, 76 (2003), 107-118. Barbara H. Margolius, Dinner-Diner Matching Probabilities Raimundas Vidunas, MacMahon's master theorem and totally mixed Nash equilibria, arXiv preprint arXiv:1401.5400 [math.CO], 2014. Raimundas Vidunas, Counting derangements and Nash equilibria Ann. Comb. 21, No. 1, 131-152 (2017). Index entries for sequences related to card matching FORMULA G.f.: sum(coeff(R(x, n, k), x, j)*(t-1)^j*(n*k-j)!, j=0..n*k) where n is the number of kinds of cards, k is the number of cards of each kind (3 in this case) and R(x, n, k) is the rook polynomial given by R(x, n, k)=(k!^2*sum(x^j/((k-j)!^2*j!))^n (see Stanley or Riordan). coeff(R(x, n, k), x, j) indicates the coefficient for x^j of the rook polynomial. From Jeremy Tan, Apr 25 2024: (Start) a(n) = Integral_{x=0..oo} exp(-x)*L_4(x)^n dx, where L_n(x) is the Laguerre polynomial of degree n (Even and Gillis). D-finite with recurrence 3*(128*n^3 - 560*n^2 + 840*n - 537)*a(n) - n*(4096*n^6 - 24064*n^5 + 62720*n^4 - 92992*n^3 + 75248*n^2 - 38670*n + 4179)*a(n-1) - 2*n*(n-1)*(18432*n^5 - 99072*n^4 + 197120*n^3 - 191776*n^2 + 144568*n - 92531)*a(n-2) + 48*n*(n-1)*(n-2)*(768*n^4 - 2976*n^3 + 3104*n^2 - 2438*n + 1583)*a(n-3) + 288*n*(n-1)*(n-2)*(n-3)*(128*n^3 - 176*n^2 + 104*n - 129)*a(n-4) = 8192*n^6 - 28672*n^5 + 23680*n^4 - 7904*n^3 + 1416*n^2 + 14382*n - 1611 (Ekhad). a(n) ~ A014608(n)/exp(4) ~ n^(4*n)*(32/3)^n*sqrt(8*Pi*n)/exp(4*n+4). (End) EXAMPLE There are 346 ways of achieving zero matches when there are 4 cards of each kind and 3 kinds of card so A(3)=346. 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, 4)/4!^n, n=0..18); MATHEMATICA 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[Coefficient[r[x, n, k], x, j]*(t - 1)^j*(n*k - j)!, {j, 0, n*k}]; Table[f[0, n, 4]/4!^n, {n, 0, 18}] // Flatten (* Jean-François Alcover, Oct 21 2013, after Maple *) Table[Integrate[Exp[-x] LaguerreL[4, x]^n, {x, 0, Infinity}], {n, 0, 16}] (* Jeremy Tan, Apr 25 2024 *) rec = 3*(128*n^3 - 560*n^2 + 840*n - 537)*a[n] - n*(4096*n^6 - 24064*n^5 + 62720*n^4 - 92992*n^3 + 75248*n^2 - 38670*n + 4179)*a[n-1] - 2*n*(n-1)*(18432*n^5 - 99072*n^4 + 197120*n^3 - 191776*n^2 + 144568*n - 92531)*a[n-2] + 48*n*(n-1)*(n-2)*(768*n^4 - 2976*n^3 + 3104*n^2 - 2438*n + 1583)*a[n-3] + 288*n*(n-1)*(n-2)*(n-3)*(128*n^3 - 176*n^2 + 104*n - 129)*a[n-4] == 8192*n^6 - 28672*n^5 + 23680*n^4 - 7904*n^3 + 1416*n^2 + 14382*n - 1611; RecurrenceTable[{rec, a[0] == 1, a[1] == 0, a[2] == 1, a[3] == 346}, a, {n, 0, 16}] (* Jeremy Tan, Apr 25 2024 *) PROG (Python) def A059074(n): l = [1, 0, 1, 346] for k in range(4, n+1): num = (((((8192*k-28672)*k+23680)*k-7904)*k+1416)*k+14382)*k-1611 \ + k*((((((4096*k-24064)*k+62720)*k-92992)*k+75248)*k-38670)*k+4179)*l[-1] \ + 2*k*(k-1)*(((((18432*k-99072)*k+197120)*k-191776)*k+144568)*k-92531)*l[-2] \ - 48*k*(k-1)*(k-2)*((((768*k-2976)*k+3104)*k-2438)*k+1583)*l[-3] \ - 288*k*(k-1)*(k-2)*(k-3)*(((128*k-176)*k+104)*k-129)*l[-4] r = num // (3*(((128*k-560)*k+840)*k-537)) l.append(r) return l[n] # Jeremy Tan, Apr 25 2024 CROSSREFS Cf. A000166, A008290, A059056-A059071, A371252. Sequence in context: A225934 A287700 A281163 * A273805 A142907 A052163 Adjacent sequences: A059071 A059072 A059073 * A059075 A059076 A059077 KEYWORD nonn,nice AUTHOR Barbara Haas Margolius (margolius(AT)math.csuohio.edu) EXTENSIONS Name changed by Jeremy Tan, Apr 25 2024 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 June 20 23:53 EDT 2024. Contains 373535 sequences. (Running on oeis4.)