A059071 -id:A059071 - cp's OEIS frontend

A059056 Penrice Christmas gift numbers, Card-matching numbers (Dinner-Diner matching numbers): Triangle T(n,k) = number of ways to get k matches for a deck with n cards, 2 of each kind.

1, 0, 0, 1, 1, 0, 4, 0, 1, 10, 24, 27, 16, 12, 0, 1, 297, 672, 736, 480, 246, 64, 24, 0, 1, 13756, 30480, 32365, 21760, 10300, 3568, 970, 160, 40, 0, 1, 925705, 2016480, 2116836, 1418720, 677655, 243360, 67920, 14688, 2655, 320, 60, 0, 1

Offset: 0

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

This is a triangle of card matching numbers. A deck has n kinds of cards, 2 of each kind. The deck is shuffled and dealt in to n hands with 2 cards each. A match occurs for every card in the j-th hand of kind j. Triangle T(n,k) is the number of ways of achieving exactly k matches (k=0..2n). The probability of exactly k matches is T(n,k)/((2n)!/2^n).
Rows are of length 1,3,5,7,... = A005408(n). [Edited by M. F. Hasler, Sep 21 2015]
Analogous to A008290. - Zerinvary Lajos, Jun 10 2005

			There are 4 ways of matching exactly 2 cards when there are 2 different kinds of cards, 2 of each in each of the two decks so T(2,2)=4.
Triangle begins:
1
"0", 0, 1
1, '0', "4", 0, 1
10, 24, 27, '16', "12", 0, 1
297, 672, 736, 480, 246, '64', "24", 0, 1
13756, 30480, 32365, 21760, 10300, 3568, 970, '160', "40", 0, 1
925705, 2016480, 2116836, 1418720, 677655, 243360, 67920, 14688, 2655, '320', "60", 0, 1
Diagonal " ": T(n,2n-2) = 0, 4, 12, 24, 40, 60, 84, 112, 144, ... equals A046092
Diagonal ' ': T(n,2n-3) = 0, 16, 64, 160, 320, 560, 896, 1344, ... equals A102860

F. N. David and D. E. Barton, Combinatorial Chance, Hafner, NY, 1962, Ch. 7 and Ch. 12.
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.

F. F. Knudsen and I. Skau, On the Asymptotic Solution of a Card-Matching Problem, Mathematics Magazine 69 (1996), 190-197.
Barbara H. Margolius, Dinner-Diner Matching Probabilities
B. H. Margolius, The Dinner-Diner Matching Problem, Mathematics Magazine, 76 (2003), 107-118.
S. G. Penrice, Derangements, permanents and Christmas presents, The American Mathematical Monthly 98(1991), 617-620.
Index entries for sequences related to card matching

Cf. A059056-A059071, A008290.

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);
for n from 0 to 7 do seq(coeff(f(t,n,2),t,m)/2^n,m=0..2*n); od;

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[ Coefficient[ f[t, n, 2]/2^n, t, m], {n, 0, 6}, {m, 0, 2*n}] // Flatten
(* Jean-François Alcover, Sep 17 2012, translated from Maple *)

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 (here k is 2) 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 j-th coefficient on x of the rook polynomial.

Additional comments from Zerinvary Lajos, Jun 18 2007

Edited by M. F. Hasler, Sep 21 2015

A000459 Number of multiset permutations of {1, 1, 2, 2, ..., n, n} with no fixed points.

Original entry on oeis.org

1, 0, 1, 10, 297, 13756, 925705, 85394646, 10351036465, 1596005408152, 305104214112561, 70830194649795010, 19629681235869138841, 6401745422388206166420, 2427004973632598297444857, 1058435896607583305978409166, 526149167104704966948064477665

Offset: 0

N. J. A. Sloane

Original definition: Number of permutations with no hits on 2 main diagonals. (Identical to definition of A000316.) - M. F. Hasler, Sep 27 2015
Card-matching numbers (Dinner-Diner matching numbers): A deck has n kinds of cards, 2 of each kind. The deck is shuffled and dealt in to n hands with 2 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)/((2n)!/2!^n).
Also, Penrice's Christmas gift numbers (see Penrice 1991).
a(n) is the maximal number of totally mixed Nash equilibria in games of n players, each with 3 pure options. - Raimundas Vidunas, Jan 22 2014

			There are 297 ways of achieving zero matches when there are 2 cards of each kind and 4 kinds of card so a(4)=297.
From _Peter Bala_, Jul 08 2014: (Start)
a(3) = 10: the 10 permutations of the multiset {1,1,2,2,3,3} that have no fixed points are
{2,2,3,3,1,1}, {3,3,1,1,2,2}
{2,3,1,3,1,2}, {2,3,1,3,2,1}
{2,3,3,1,1,2}, {2,3,3,1,2,1}
{3,2,1,3,1,2}, {3,2,1,3,2,1}
{3,2,3,1,1,2}, {3,2,3,1,2,1}
(End)

F. N. David and D. E. Barton, Combinatorial Chance, Hafner, NY, 1962, Ch. 7 and Ch. 12.
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.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..100
Per Alexandersson and Frether Getachew, An involution on derangements, arXiv:2105.08455 [math.CO], 2021.
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.
F. F. Knudsen and I. Skau, On the Asymptotic Solution of a Card-Matching Problem, Mathematics Magazine 69 (1996), 190-197.
P. A. MacMahon, Combinatory Analysis Cambridge: The University Press 1915-1916
B. H. Margolius, The Dinner-Diner Matching Problem, Mathematics Magazine, 76 (2003), 107-118.
B. H. Margolius, Dinner-Diner Matching Probabilities
R. D. McKelvey and A. McLennan, The maximal number of regular totally mixed Nash equilibria, J. Economic Theory, 72:411--425, 1997.
L. I. Nicolaescu, Derangements and asymptotics of the Laplace transforms of large powers of a polynomial, New York J. Math. 10 (2004) 117-131.
S. G. Penrice, Derangements, permanents and Christmas presents, The American Mathematical Monthly 98 (1991), 617-620.
John Riordan and N. J. A. Sloane, Correspondence, 1974
R. Vidunas, Counting derangements and Nash equilibria, arXiv preprint arXiv:1401.5400 [math.CO], 2014-2016.
Raimundas Vidunas, Counting derangements and Nash equilibria Ann. Comb. 21, No. 1, 131-152 (2017).
Wikipedia, Permutations of multisets
Index entries for sequences related to card matching

Cf. A000166, A008290, A059056-A059071, A033581, A059073.

Row n=2 of A372307.

I:=[0,1]; [n le 2 select I[n] else n*(2*n-1)*Self(n-1)+2*n*(n-1)*Self(n-2)-(2*n-1): n in [1..30]]; // Vincenzo Librandi, Sep 28 2015

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,2)/2!^n,n=0..18);

RecurrenceTable[{(2*n+3)*a[n+3]==(2*n+5)^2*(n+2)*a[n+2]+(2*n+3)*(n+2)*a[n+1]-2*(2*n+5)*(n+1)*(n+2)*a[n],a[1]==0,a[2]==1,a[3]==10},a,{n,1,25}] (* Vaclav Kotesovec, Aug 31 2012 *)
a[n_] := a[n] = n*(2*n-1)*a[n-1] + 2*n*(n-1)*a[n-2] - (2*n-1); a[0] = 1; a[1] = 0; a[2] = 1; Table[a[n], {n, 0, 14}] (* Jean-François Alcover, Mar 04 2013 *)
a[n_] := Sum[(2*(n-m))! / 2^(n-m) Binomial[n, m] Hypergeometric1F1[m-n, 2*(m - n), -4], {m, 0, n}]; Table[a[n], {n, 0, 16}] (* Peter Luschny, Nov 15 2023 *)

a(n) = (2^n*round(2^(n/2+3/4)*Pi^(-1/2)*exp(-2)*n!*besselk(1/2+n,2^(1/2))))/2^n;
vector(15, n, a(n))\\ Altug Alkan, Sep 28 2015

{ A000459(n) = sum(m=0,n, sum(k=0,n-m, (-1)^k * binomial(n,k) * binomial(n-k,m) * 2^(2*k+m-n) * (2*n-2*m-k)! )); } \\ Max Alekseyev, Oct 06 2016

a(n) = A000316(n)/2^n.
a(n) = Sum_{k=0..n} Sum_{m=0..n-k} (-1)^k * n!/(k!*m!*(n-k-m)!) * 2^(2*k+m-n) * (2*n-2*m-k)!. - Max Alekseyev, Oct 06 2016
G.f.: Sum_{j=0..n*k} coeff(R(x, n, k), x, j)*(t-1)^j*(n*k-j)! where n is the number of kinds of cards, k is the number of cards of each kind (2 in this case) and coeff(R(x, n, k), x, j) is the coefficient of x^j of the rook polynomial R(x, n, k) = (k!^2*sum(x^j/((k-j)!^2*j!))^n (see Riordan or Stanley).
D-finite with recurrence a(n) = n*(2*n-1)*a(n-1)+2*n*(n-1)*a(n-2)-(2*n-1), a(1) = 0, a(2) = 1.
a(n) = round(2^(n/2 + 3/4)*Pi^(-1/2)*exp(-2)*n!*BesselK(1/2+n,2^(1/2))). - Mark van Hoeij, Oct 30 2011
(2*n+3)*a(n+3)=(2*n+5)^2*(n+2)*a(n+2)+(2*n+3)*(n+2)*a(n+1)-2*(2*n+5)*(n+1)*(n+2)*a(n). - Vaclav Kotesovec, Aug 31 2012
Asymptotic: a(n) ~ n^(2*n)*2^(n+1)*sqrt(Pi*n)/exp(2*n+2), Vaclav Kotesovec, Aug 31 2012
a(n) = (1/2^n)*A000316(n) = int_{0..inf} exp(-x)*(1/2*x^2 - 2*x + 1)^n dx. Asymptotic: a(n) ~ ((2*n)!/2^n)*exp(-2)*( 1 - 1/(2*n) - 23/(96*n^2) + O(1/n^3) ). See Nicolaescu. - Peter Bala, Jul 07 2014
Let S = x_1 + ... + x_n. a(n) equals the coefficient of (x_1*...*x_n)^2 in the expansion of product {i = 1..n} (S - x_i)^2 (MacMahon, Chapter III). - Peter Bala, Jul 08 2014
Conjecture: a(n+k) - a(n) is divisible by k. - Mark van Hoeij, Nov 15 2023

More terms and edited by Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Dec 22 2000
Edited by M. F. Hasler, Sep 27 2015
a(0)=1 prepended by Max Alekseyev, Oct 06 2016

A059073 Card-matching numbers (Dinner-Diner matching numbers).

Original entry on oeis.org

1, 0, 1, 56, 13833, 6699824, 5691917785, 7785547001784, 16086070907249329, 47799861987366600992, 196500286135805946117201, 1082973554682091552092493880, 7797122311868240909226166565881

Offset: 0

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

A deck has n kinds of cards, 3 of each kind. The deck is shuffled and dealt in to n hands with 3 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)/((3n)!/3!^n).
Number of fixed-point-free permutations of n distinct letters (ABCD...), each of which appears thrice. If there is only one letter of each type we get A000166. - Zerinvary Lajos, Oct 15 2006
a(n) is the maximal number of totally mixed Nash equilibria in games of n players, each with 4 pure options. - Raimundas Vidunas, Jan 22 2014

			There are 56 ways of achieving zero matches when there are 3 cards of each kind and 3 kinds of card so a(3)=56.

F. N. David and D. E. Barton, Combinatorial Chance, Hafner, NY, 1962, Ch. 7 and Ch. 12.
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.
F. F. Knudsen and I. Skau, On the Asymptotic Solution of a Card-Matching Problem, Mathematics Magazine 69 (1996), 190-197.
Barbara H. Margolius, Dinner-Diner Matching Probabilities
Barbara H. Margolius, The Dinner-Diner Matching Problem, Mathematics Magazine, 76 (2003), 107-118.
R. D. McKelvey and A. McLennan, The maximal number of regular totally mixed Nash equilibria, J. Economic Theory, 72 (1997), 411-425.
S. G. Penrice, Derangements, permanents and Christmas presents, The American Mathematical Monthly 98(1991), 617-620.
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, A000459, A008290, A059056-A059071.

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,3)/3!^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, 3]/3!^n, {n, 0, 12}] (* Jean-François Alcover, May 21 2012, translated from Maple *)

G.f.: Sum_{j=0..n*k} coeff(R(x, n, k), x, j)*(t-1)^j*(n*k-j)! 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.

A059058 Card-matching numbers (Dinner-Diner matching numbers).

Original entry on oeis.org

1, 0, 0, 0, 1, 1, 0, 9, 0, 9, 0, 1, 56, 216, 378, 435, 324, 189, 54, 27, 0, 1, 13833, 49464, 84510, 90944, 69039, 38448, 16476, 5184, 1431, 216, 54, 0, 1, 6699824, 23123880, 38358540, 40563765, 30573900, 17399178, 7723640

Offset: 0

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

This is a triangle of card matching numbers. A deck has n kinds of cards, 3 of each kind. The deck is shuffled and dealt in to n hands with 3 cards each. A match occurs for every card in the j-th hand of kind j. Triangle T(n,k) is the number of ways of achieving exactly k matches (k=0..3n). The probability of exactly k matches is T(n,k)/((3n)!/(3!)^n).
Rows have lengths 1,4,7,10,...
Analogous to A008290 - Zerinvary Lajos, Jun 22 2005

			There are 9 ways of matching exactly 2 cards when there are 2 different kinds of cards, 3 of each in each of the two decks so T(2,2)=9.

F. N. David and D. E. Barton, Combinatorial Chance, Hafner, NY, 1962, Ch. 7 and Ch. 12.
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.

Vincenzo Librandi, Rows n = 1..30, flattened
F. F. Knudsen and I. Skau, On the Asymptotic Solution of a Card-Matching Problem, Mathematics Magazine 69 (1996), 190-197.
Barbara H. Margolius, Dinner-Diner Matching Probabilities
B. H. Margolius, The Dinner-Diner Matching Problem, Mathematics Magazine, 76 (2003), 107-118.
S. G. Penrice, Derangements, permanents and Christmas presents, The American Mathematical Monthly 98(1991), 617-620.
Index entries for sequences related to card matching

Cf. A008290, A059056-A059071, A008290.

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);
for n from 0 to 6 do seq(coeff(f(t,n,3),t,m)/3!^n,m=0..3*n); od;

p[x_, k_] := k!^2*Sum[ x^j/((k-j)!^2*j!), {j, 0, k}]; f[t_, n_, k_] := Sum[ Coefficient[ p[x, k]^n, x, j]*(t-1)^j*(n*k-j)!, {j, 0, n*k}]; Flatten[ Table[ Coefficient[ f[t, n, 3], t, m]/3!^n, {n, 0, 6}, {m, 0, 3n}]] (* Jean-François Alcover, Jan 31 2012, after Maple *)

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 (here k is 3) 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 j-th coefficient on x of the rook polynomial.

A000489 Card matching: Coefficients B[n,3] of t^3 in the reduced hit polynomial A[n,n,n](t).

Original entry on oeis.org

1, 16, 435, 7136, 99350, 1234032, 14219212, 155251840, 1628202762, 16550991200, 164111079110, 1594594348800, 15235525651840, 143518352447680, 1335670583147400, 12301278983461376, 112264111607438906, 1016361486936571680, 9136254276320346046

Offset: 1

N. J. A. Sloane

nonn

The definition uses notations of Riordan (1958), except for use of n instead of p. - M. F. Hasler, Sep 22 2015

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 193.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Cf. A000279, A000535.
Cf. A059056 - A059071.
Cf. A001181.

[1, 16] cat [&+[3*Binomial(n, 3)*Binomial(n, k+3)*Binomial(n, k)*Binomial(n-3, k) + 6*n*Binomial(n, 2)*Binomial(n, k+1)*Binomial(n-1, k+2)*Binomial(n-2, k): k in [0..n-3]] + &+[n^3*Binomial(n-1, k)^3: k in [0..n-1]]: n in [3..20]]; // Vincenzo Librandi, Sep 22 2015

a[n_] := 3*Binomial[n, 3]*Sum[Binomial[n, k + 3]*Binomial[n, k]*Binomial[n - 3, k], {k, 0, n - 3}] + 6 n*Binomial[n, 2]*Sum[Binomial[n, k + 1]*Binomial[n - 1, k + 2]*Binomial[n - 2, k], {k, 0, n - 3}] + n^3*Sum[Binomial[n - 1, k]^3, {k, 0, n - 1}]; Table[a[n], {n, 20}] (* T. D. Noe, Jun 20 2012 *)

A000489(n)={3*binomial(n, 3)*sum(k=0,n-3,binomial(n, k+3)*binomial(n, k)*binomial(n-3, k))+6*n*binomial(n, 2)*sum(k=0,n-3,binomial(n, k+1)*binomial(n-1, k+2)*binomial(n-2, k))+n^3*sum(k=0,n-1,binomial(n-1, k)^3)} \\ M. F. Hasler, Sep 20 2015

a(n) = 3*binomial(n, 3)*sum(binomial(n, k+3)*binomial(n, k)*binomial(n-3, k), k=0..n-3) + 6n*binomial(n, 2)*sum(binomial(n, k+1)*binomial(n-1, k+2)*binomial(n-2, k), k=0..n-3) + n^3*sum(binomial(n-1, k)^3, k=0..n-1).
Recurrence: (n+3)*(243*n^7 - 1701*n^6 + 4239*n^5 - 4671*n^4 + 6042*n^3 - 17352*n^2 + 25032*n - 12016)*(n-1)^2*a(n) = n*(1701*n^9 - 6804*n^8 + 270*n^7 + 19116*n^6 + 35085*n^5 - 203640*n^4 + 324384*n^3 - 246736*n^2 + 75440*n - 5440)*a(n-1) + 8*n*(243*n^7 - 864*n^5 - 486*n^4 + 4233*n^3 - 5274*n^2 + 2460*n - 184)*(n-1)^2*a(n-2). - Vaclav Kotesovec, Aug 07 2013
a(n) ~ 3*sqrt(3)*n^2*8^(n-1)/Pi. - Vaclav Kotesovec, Aug 07 2013
a(n) = n^2*((27*n^3+54*n^2-57*n+8)*(n+2)*A001181(n)-(189*n^3+189*n^2-30*n+16)*(n-1)*A001181(n-1))/96. - Mark van Hoeij, Nov 14 2023

More terms from Vladeta Jovovic, Apr 26 2000
More terms from Emeric Deutsch, Feb 19 2004
Definition made more precise by M. F. Hasler, Sep 22 2015

A059060 Card-matching numbers (Dinner-Diner matching numbers).

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 1, 0, 16, 0, 36, 0, 16, 0, 1, 346, 1824, 4536, 7136, 7947, 6336, 3936, 1728, 684, 128, 48, 0, 1, 748521, 3662976, 8607744, 12880512, 13731616, 11042688, 6928704, 3458432, 1395126, 453888, 122016, 25344, 4824, 512, 96, 0, 1, 3993445276

Offset: 0

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

This is a triangle of card 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. Triangle T(n,k) is the number of ways of achieving exactly k matches (k=0..4n). The probability of exactly k matches is T(n,k)/((4n)!/(4!)^n).
Rows have lengths 1,5,9,13,...
Analogous to A008290 - Zerinvary Lajos, Jun 22 2005

			There are 16 ways of matching exactly 2 cards when there are 2 different kinds of cards, 4 of each so T(2,2)=16.
From _Joerg Arndt_, Nov 08 2020: (Start)
The first few rows are
1
0, 0, 0, 0, 1
1, 0, 16, 0, 36, 0, 16, 0, 1
346, 1824, 4536, 7136, 7947, 6336, 3936, 1728, 684, 128, 48, 0, 1
748521, 3662976, 8607744, 12880512, 13731616, 11042688, 6928704, 3458432, 1395126, 453888, 122016, 25344, 4824, 512, 96, 0, 1
3993445276, 18743463360, 42506546320, 61907282240, 64917874125, 52087325696, 33176621920, 17181584640, 7352761180, 2628808000, 790912656, 201062080, 43284010, 7873920, 1216000, 154496, 17640, 1280, 160, 0, 1 (End)

F. N. David and D. E. Barton, Combinatorial Chance, Hafner, NY, 1962, Ch. 7 and Ch. 12.
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.

F. F. Knudsen and I. Skau, On the Asymptotic Solution of a Card-Matching Problem, Mathematics Magazine 69 (1996), 190-197.
Barbara H. Margolius, Dinner-Diner Matching Probabilities
B. H. Margolius, The Dinner-Diner Matching Problem, Mathematics Magazine, 76 (2003), 107-118.
S. G. Penrice, Derangements, permanents and Christmas presents, The American Mathematical Monthly 98(1991), 617-620.
Index entries for sequences related to card matching

Cf. A008290, A059056-A059071.

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);
for n from 0 to 5 do seq(coeff(f(t,n,4),t,m)/4!^n,m=0..4*n); od;

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[ Coefficient[f[t, n, 4], t, m]/4!^n, {n, 0, 5}, {m, 0, 4*n}] // Flatten (* Jean-François Alcover, Feb 22 2013, translated from Maple *)

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 (here k is 4) 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 j-th coefficient on x of the rook polynomial.

A093772 a(n) is the smallest integer at which the value of the "truncated Mertens function" (= A088004) equals n.

Original entry on oeis.org

1, 6, 10, 14, 15, 21, 22, 26, 34, 35, 38, 39, 51, 55, 57, 58, 62, 65, 77, 85, 86, 87, 91, 93, 94, 95, 119, 122, 123, 129, 134, 142, 143, 145, 146, 158, 159, 161, 185, 202, 203, 205, 206, 209, 210, 213, 214, 215, 217, 218, 219, 221, 253, 254, 265, 278, 299, 301, 302

Offset: 1

Labos Elemer, Apr 28 2004

nonn

Truncated Mertens function = summatory Moebius when argument runs through nonprimes.

Cf. A002321, A008682, A059071, A088004, A093773.

mer[x_] :=mer[x]=mer[x-1]+MoebiusMu[x]; mer[0]=0;$RecursionLimit=1000; t=Table[mer[w]+PrimePi[w], {w, 1, 1000}] Table[Min[Flatten[Position[t, j]]], {j, 1, 200}]

A093773 a(n) is the smallest integer at which the value of the "truncated Mertens function" (= A088004) equals the n-th prime number.

Original entry on oeis.org

6, 10, 15, 22, 38, 51, 62, 77, 91, 123, 134, 159, 203, 206, 214, 253, 302, 305, 330, 341, 365, 395, 454, 489, 526, 542, 545, 554, 566, 586, 723, 753, 781, 794, 866, 870, 914, 933, 966, 1059, 1138, 1141, 1198, 1202, 1214, 1219, 1293, 1351, 1383, 1387, 1403

Offset: 1

Labos Elemer, Apr 28 2004

nonn

Truncated Mertens function = summatory Moebius when argument runs through nonprimes. See A088004(n) = A002321(n) + A000720(n).

Cf. A000720, A002321, A008682, A059071, A088004, A093772.

mer[x_] :=mer[x]=mer[x-1]+MoebiusMu[x]; mer[0]=0;$RecursionLimit=1000; t=Table[mer[w]+PrimePi[w], {w, 1, 1000}] Table[Min[Flatten[Position[t, Prime[j]]]], {j, 1, 200}]

a(n) = A093772(prime(n)) = A093772(A000040(n)). Solutions to min{x; A002321(x) + A000720(x) = A000040(n) = prime(n)} = a(n).

A059062 Card-matching numbers (Dinner-Diner matching numbers).

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 1, 1, 0, 25, 0, 100, 0, 100, 0, 25, 0, 1, 2252, 15150, 48600, 99350, 144150, 156753, 131000, 87075, 45000, 19300, 6000, 1800, 250, 75, 0, 1, 44127009, 274314600, 822998550, 1583402400, 2189652825, 2311947008

Offset: 0

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

This is a triangle of card matching numbers. A deck has n kinds of cards, 5 of each kind. The deck is shuffled and dealt in to n hands with 5 cards each. A match occurs for every card in the j-th hand of kind j. Triangle T(n,k) is the number of ways of achieving exactly k matches (k=0..5n). The probability of exactly k matches is T(n,k)/((5n)!/(5!)^n).
Rows have lengths 1,6,11,16,...
Analogous to A008290 - Zerinvary Lajos, Jun 22 2005

			There are 25 ways of matching exactly 2 cards when there are 2 different kinds of cards, 5 of each so T(2,2)=25.

F. N. David and D. E. Barton, Combinatorial Chance, Hafner, NY, 1962, Ch. 7 and Ch. 12.
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.

Vincenzo Librandi, Rows n = 1..15 of triangle, flattened
F. F. Knudsen and I. Skau, On the Asymptotic Solution of a Card-Matching Problem, Mathematics Magazine 69 (1996), 190-197.
Barbara H. Margolius, Dinner-Diner Matching Probabilities
B. H. Margolius, The Dinner-Diner Matching Problem, Mathematics Magazine, 76 (2003), 107-118.
S. G. Penrice, Derangements, permanents and Christmas presents, The American Mathematical Monthly 98(1991), 617-620.
Index entries for sequences related to card matching

Cf. A008290, A059056-A059071.

Cf. A008290.

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);
for n from 0 to 4 do seq(coeff(f(t,n,5),t,m)/5!^n,m=0..5*n); od;

nmax = 4; r[x_, n_, k_] := (k!^2*Sum[ x^j/((k-j)!^2*j!), {j, 0, k}])^n; f[t_, n_, k_] := Sum[ Coefficient[ r[x, n, k], x, j]*(t-1)^j*(n*k-j)!, {j, 0, n*k}]; Flatten[ Table[ Coefficient[ f[t, n, 5], t, m]/5!^n, {n, 0, nmax}, {m, 0, 5n}]](* Jean-François Alcover, Nov 23 2011, after Maple *)

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 (here k is 5) 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 j-th coefficient on x of the rook polynomial.

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

Original entry on oeis.org

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

Offset: 0

Jeremy Tan, Mar 16 2024

nonn

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

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

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

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.

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}]

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]

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

cp's OEIS Frontend

A059056 Penrice Christmas gift numbers, Card-matching numbers (Dinner-Diner matching numbers): Triangle T(n,k) = number of ways to get k matches for a deck with n cards, 2 of each kind.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A000459 Number of multiset permutations of {1, 1, 2, 2, ..., n, n} with no fixed points.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A059073 Card-matching numbers (Dinner-Diner matching numbers).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A059058 Card-matching numbers (Dinner-Diner matching numbers).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A000489 Card matching: Coefficients B[n,3] of t^3 in the reduced hit polynomial A[n,n,n](t).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A059060 Card-matching numbers (Dinner-Diner matching numbers).

Views

Author

Keywords

Comments

Examples

References

Links