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

Author

Jeremy Tan, Apr 26 2024

Keywords

• nonn
• tabl

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.

Examples

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

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

Crossrefs

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

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

Main diagonal gives A375778.

Programs

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

Python

# See link.

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