A371252 Number of derangements of a multiset comprising n repeats of a 4-element set.

1, 9, 297, 13833, 748521, 44127009, 2750141241, 178218782793, 11887871843817, 810822837267729, 56289612791763297, 3964402453931011233, 282558393168537751929, 20342533966643026042641, 1477174422125162468055897, 108064155440237168218117833, 7956914294959071176435002857

Offset: 0

Author

Jeremy Tan, Mar 16 2024

Keywords

• nonn

Comments

A deck has 4 suits of n cards each. The deck is shuffled and dealt into 4 hands of n cards each. A match occurs for every card in the i-th hand of suit i. a(n) is the number of ways of achieving no matches. The probability of no matches is a(n)/((4n)!/n!^4).

Examples

			There are a(13) = 20342533966643026042641 bridge deals where North, South, East and West are void in clubs, diamonds, hearts and spades, respectively.
		

Links

• Jeremy Tan, Table of n, a(n) for n = 0..200
• 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, recurrences and asymptotics 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.
• B. H. Margolius, The Dinner-Diner Matching Problem, Mathematics Magazine, 76 (2003), pp. 107-118.
• Index entries for sequences related to card matching

Crossrefs

Column k=0 of A059068. The analogous sequence with 3 suits is A000172 and that with 2 suits is A000012.

Column k=4 of A372307.

Cf. A008290, A059056-A059071.

Programs

Mathematica

Table[Integrate[Exp[-x] LaguerreL[n, x]^4, {x, 0, Infinity}], {n, 0, 16}]
(* or *)
rec = n^3(2n-1)(5n-6)(10n-13) a[n] == (8300n^6-37350n^5+66698n^4-60393n^3+29297n^2-7263n+738) a[n-1] - (n-1)(16300n^5-81500n^4+151553n^3-123364n^2+39501n-4338) a[n-2] + 162(n-2)^3(n-1)(5n-1)(10n-3) a[n-3];
RecurrenceTable[{rec, a[0] == 1, a[1] == 9, a[2] == 297}, a, {n, 0, 16}]

Python

def A371252(n):
    l = [1, 9, 297]
    for k in range(3, n+1):
        m1 = (((((8300*k-37350)*k+66698)*k-60393)*k+29297)*k-7263)*k+738
        m2 = (k-1)*(((((16300*k-81500)*k+151553)*k-123364)*k+39501)*k-4338)
        m3 = 162*(k-2)**3*(k-1)*(5*k-1)*(10*k-3)
        r = (m1*l[-1] - m2*l[-2] + m3*l[-3]) // (k**3*(2*k-1)*(5*k-6)*(10*k-13))
        l.append(r)
    return l[n]

Formula

a(n) = Integral_{x=0..oo} exp(-x)*L_n(x)^4 dx, where L_n(x) is the Laguerre polynomial of degree n (Even and Gillis).

D-finite with recurrence n^3*(2*n-1)*(5*n-6)*(10*n-13)*a(n) = (8300*n^6 - 37350*n^5 + 66698*n^4 - 60393*n^3 + 29297*n^2 - 7263*n + 738)*a(n-1) - (n-1)*(16300*n^5 - 81500*n^4 + 151553*n^3 - 123364*n^2 + 39501*n - 4338)*a(n-2) + 162*(n-2)^3*(n-1)*(5*n-1)*(10*n-3)*a(n-3) (Ekhad).

a(n) = [(w*x*y*z)^n] ((x+y+z)*(w+y+z)*(w+x+z)*(w+x+y))^n.

a(n) ~ 3^(4*n + 3) / (32 * Pi^(3/2) * n^(3/2)). - Vaclav Kotesovec, Mar 29 2024