A371252 -id:A371252 - cp's OEIS frontend

A372307 Square array read by antidiagonals: T(n,k) is the number of derangements of a multiset comprising n repeats of a k-element set.

1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 9, 10, 1, 0, 1, 1, 44, 297, 56, 1, 0, 1, 1, 265, 13756, 13833, 346, 1, 0, 1, 1, 1854, 925705, 6699824, 748521, 2252, 1, 0, 1, 1, 14833, 85394646, 5691917785, 3993445276, 44127009, 15184, 1, 0, 1

Offset: 0

Jeremy Tan, Apr 26 2024

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

T(n,k) is the maximal number of totally mixed Nash equilibria in games of k players, each with n+1 pure options.

			Square array T(n,k) begins:
  1, 1, 1,      1,            1,                   1, ...
  1, 0, 1,      2,            9,                  44, ...
  1, 0, 1,     10,          297,               13756, ...
  1, 0, 1,     56,        13833,             6699824, ...
  1, 0, 1,    346,       748521,          3993445276, ...
  1, 0, 1,   2252,     44127009,       2671644472544, ...
  1, 0, 1,  15184,   2750141241,    1926172117389136, ...
  1, 0, 1, 104960, 178218782793, 1463447061709156064, ...

Jeremy Tan, Antidiagonals n = 0..32, flattened
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.
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.
Jeremy Tan, Python program
Raimundas Vidunas, MacMahon's master theorem and totally mixed Nash equilibria, 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

Rows 0-5 give A000012, A000166, A000459, A059073, A059074, A123297.
Columns 0-4 give A000012, A000007, A000012, A000172, A371252.
Main diagonal gives A375778.

A:= (n, k)-> (-1)^(n*k)*int(exp(-x)*orthopoly[L](n, x)^k, x=0..infinity):
seq(seq(A(n, d-n), n=0..d), d=0..10);  # Alois P. Heinz, Aug 27 2024

Table[Abs[Integrate[Exp[-x] LaguerreL[n, x]^(s-n), {x, 0, Infinity}]], {s, 0, 9}, {n, 0, s}] // Flatten

Python
```
# See link.
```

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

T(n,k) ~ A089759(n,k)/exp(n).

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

Original entry on oeis.org

1, 0, 1, 346, 748521, 3993445276, 45131501617225, 964363228180815366, 35780355973270898382001, 2158610844939711892526650456, 201028342764877992289387752167601, 27708893753238763155350683269145066450, 5459844285803153226360263675364357481841881

Offset: 0

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

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]

			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.

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).
Index entries for sequences related to card matching

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

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

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

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)

Name changed by Jeremy Tan, Apr 25 2024

cp's OEIS Frontend

A372307 Square array read by antidiagonals: T(n,k) is the number of derangements of a multiset comprising n repeats of a k-element set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula