0,4

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]

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.

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).

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)

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.

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);

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 *)

(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

Cf. A000166, A008290, A059056-A059071, A371252.

Sequence in context: A225934 A287700 A281163 * A273805 A142907 A052163

Adjacent sequences: A059071 A059072 A059073 * A059075 A059076 A059077

nonn,nice

Barbara Haas Margolius (margolius(AT)math.csuohio.edu)

Name changed by Jeremy Tan, Apr 25 2024

approved