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

%I #20 Aug 27 2024 14:58:15

%S 1,9,297,13833,748521,44127009,2750141241,178218782793,11887871843817,

%T 810822837267729,56289612791763297,3964402453931011233,

%U 282558393168537751929,20342533966643026042641,1477174422125162468055897,108064155440237168218117833,7956914294959071176435002857

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

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

%H Jeremy Tan, <a href="/A371252/b371252.txt">Table of n, a(n) for n = 0..200</a>

%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 Shalosh B. Ekhad, <a href="https://sites.math.rutgers.edu/~zeilberg/tokhniot/oMultiDer2.txt">Terms, recurrences and asymptotics for multiset derangements</a>.

%H S. Even and J. Gillis, <a href="https://doi.org/10.1017/S0305004100052154">Derangements and Laguerre polynomials</a>, Mathematical Proceedings of the Cambridge Philosophical Society, Volume 79, Issue 1, January 1976, pp. 135-143.

%H B. H. Margolius, <a href="http://www.jstor.org/stable/3219303">The Dinner-Diner Matching Problem</a>, Mathematics Magazine, 76 (2003), pp. 107-118.

%H <a href="/index/Ca#cardmatch">Index entries for sequences related to card matching</a>

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

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

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

%F a(n) ~ 3^(4*n + 3) / (32 * Pi^(3/2) * n^(3/2)). - _Vaclav Kotesovec_, Mar 29 2024

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

%t Table[Integrate[Exp[-x] LaguerreL[n, x]^4, {x, 0, Infinity}], {n, 0, 16}]

%t (* or *)

%t 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];

%t RecurrenceTable[{rec, a[0] == 1, a[1] == 9, a[2] == 297}, a, {n, 0, 16}]

%o (Python)

%o def A371252(n):

%o l = [1, 9, 297]

%o for k in range(3, n+1):

%o m1 = (((((8300*k-37350)*k+66698)*k-60393)*k+29297)*k-7263)*k+738

%o m2 = (k-1)*(((((16300*k-81500)*k+151553)*k-123364)*k+39501)*k-4338)

%o m3 = 162*(k-2)**3*(k-1)*(5*k-1)*(10*k-3)

%o r = (m1*l[-1] - m2*l[-2] + m3*l[-3]) // (k**3*(2*k-1)*(5*k-6)*(10*k-13))

%o l.append(r)

%o return l[n]

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

%Y Column k=4 of A372307.

%Y Cf. A008290, A059056-A059071.

%K nonn

%O 0,2

%A _Jeremy Tan_, Mar 16 2024