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,12

Comments

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.

Links

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

Formula

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

Example

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

Maple

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

Mathematica

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

Prog

(Python) # See link.

Crossrefs

Rows 0-5 give A000012, A000166, A000459, A059073, A059074, A123297.

Columns 0-4 give A000012, A000007, A000012, A000172, A371252.

Main diagonal gives A375778.

Sequence in context: A129634 A266825 A066438 * A279291 A051126 A168120

Adjacent sequences: A372304 A372305 A372306 * A372308 A372309 A372310

Keyword

nonn,tabl

Author

Jeremy Tan, Apr 26 2024

Status

approved