A059056 -id:A059056 - cp's OEIS frontend

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

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

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

Original entry on oeis.org

1, 9, 8, 6, 0, 1, 297, 672, 736, 480, 246, 64, 24, 0, 1, 13833, 49464, 84510, 90944, 69039, 38448, 16476, 5184, 1431, 216, 54, 0, 1, 748521, 3662976, 8607744, 12880512, 13731616, 11042688, 6928704, 3458432, 1395126

Offset: 0

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

This is a triangle of card matching numbers. A deck has 4 kinds of cards, n of each kind. The deck is shuffled and dealt in to 4 hands with each with n cards. 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)!/n!^4).
Rows have lengths 1,5,9,13,...
Analogous to A008290 - Zerinvary Lajos, Jun 22 2005

			There are 736 ways of matching exactly 2 cards when there are 2 cards of each kind and 4 kinds of card so T(2,2)=736.
Triangle begins:
      1;
      9,     8,     6,     0,     1;
    297,   672,   736,   480,   246,    64,    24,    0,    1;
  13833, 49464, 84510, 90944, 69039, 38448, 16476, 5184, 1431, 216, 54, 0, 1;
  ...

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.
Cf. A008290.
Row sums give A008977.

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,4,n),t,m)/n!^4,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, 4, n], t, m]/n!^4, {n, 0, 4}, {m, 0, 4*n}] // Flatten (* Jean-François Alcover, Dec 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 (4 in this case), k is the number of cards of each kind 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.

A059057 Penrice Christmas gift numbers, Card-matching numbers (Dinner-Diner matching numbers).

Original entry on oeis.org

1, 0, 0, 2, 4, 0, 16, 0, 4, 80, 192, 216, 128, 96, 0, 8, 4752, 10752, 11776, 7680, 3936, 1024, 384, 0, 16, 440192, 975360, 1035680, 696320, 329600, 114176, 31040, 5120, 1280, 0, 32, 59245120, 129054720, 135477504, 90798080

Offset: 0

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

This is a triangle of card matching numbers. Two decks each have n kinds of cards, 2 of each kind. The first deck is laid out in order. The second deck is shuffled and laid out next to the first. A match occurs if a card from the second deck is next to a card of the same kind from the first deck. 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)!.

Rows are of length 1,3,5,7,...

			There are 16 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)=16.

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 6 do seq(coeff(f(t,n,2),t,m),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}]; Flatten[ Table[ Coefficient[ f[t, n, 2], t, m], {n, 0, 6}, {m, 0, 2 n}]](* Jean-François Alcover, Nov 28 2011, 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.

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

Original entry on oeis.org

1, 0, 0, 0, 6, 36, 0, 324, 0, 324, 0, 36, 12096, 46656, 81648, 93960, 69984, 40824, 11664, 5832, 0, 216, 17927568, 64105344, 109524960, 117863424, 89474544, 49828608, 21352896, 6718464, 1854576, 279936, 69984, 0, 1296

Offset: 0

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

This is a triangle of card matching numbers. Two decks each have n kinds of cards, 3 of each kind. The first deck is laid out in order. The second deck is shuffled and laid out next to the first. A match occurs if a card from the second deck is next to a card of the same kind from the first deck. 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)!.

Rows are of length 1,4,7,10,...

			There are 324 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)=324.

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 4 do seq(coeff(f(t,n,3),t,m),m=0..3*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, 3], t, m], {n, 0, 4}, {m, 0, 3*n}] // Flatten (* Jean-François Alcover, Oct 21 2013, 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.

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

Original entry on oeis.org

1, 0, 0, 0, 0, 24, 576, 0, 9216, 0, 20736, 0, 9216, 0, 576, 4783104, 25214976, 62705664, 98648064, 109859328, 87588864, 54411264, 23887872, 9455616, 1769472, 663552, 0, 13824, 248341303296, 1215287525376, 2855842873344

Offset: 0

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

This is a triangle of card matching numbers. Two decks each have n kinds of cards, 4 of each kind. The first deck is laid out in order. The second deck is shuffled and laid out next to the first. A match occurs if a card from the second deck is next to a card of the same kind from the first deck. 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)!.

rows are of length 1,5,9,13,...

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

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 4 do seq(coeff(f(t,n,4),t,m),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}]; a[n_, m_] := Coefficient[ f[t, n, 4], t, m]; Table[a[n, m], {n, 0, 4}, {m, 0, 4*n}] // Flatten (* Jean-François Alcover, Oct 07 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.

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

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 120, 14400, 0, 360000, 0, 1440000, 0, 1440000, 0, 360000, 0, 14400, 3891456000, 26179200000, 83980800000, 171676800000, 249091200000, 270869184000, 226368000000, 150465600000, 77760000000

Offset: 0

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

This is a triangle of card matching numbers. Two decks each have n kinds of cards, 5 of each kind. The first deck is laid out in order. The second deck is shuffled and laid out next to the first. A match occurs if a card from the second deck is next to a card of the same kind from the first deck. 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)!.

Rows are of length 1,6,11,16,...

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

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 4 do seq(coeff(f(t,n,5),t,m),m=0..5*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}]; k = 5; Table[ Table[ Coefficient[f[t, n, k], t, m], {m, 0, k*n}], {n, 0, 4}] // Flatten (* Jean-François Alcover, Oct 21 2013, 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 coefficient x^j of the rook polynomial.

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

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 4, 0, 1, 1, 0, 9, 0, 9, 0, 1, 1, 0, 16, 0, 36, 0, 16, 0, 1, 1, 0, 25, 0, 100, 0, 100, 0, 25, 0, 1, 1, 0, 36, 0, 225, 0, 400, 0, 225, 0, 36, 0, 1, 1, 0, 49, 0, 441, 0, 1225, 0, 1225, 0, 441, 0, 49, 0, 1, 1, 0, 64, 0, 784, 0, 3136, 0, 4900, 0

Offset: 0

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

This is a triangle of card matching numbers. A deck has 2 kinds of cards, n of each kind. The deck is shuffled and dealt in to 2 hands each with n cards. 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). An odd number of matches is impossible, so alternating elements in each row of the triangle are zero. The probability of exactly k matches is T(n,k)/((2n)!/n!^2).
Rows have lengths 1,3,5,7,...
Analogous to A008290 - Zerinvary Lajos, Jun 22 2005

			There are 4 ways of matching exactly 2 cards when there are 2 cards of each kind and 2 kinds of card so T(2,2)=4.

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.

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 10 do seq(coeff(f(t,2,n),t,m)/n!^2,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[ Table[ Coefficient[f[t, 2, n], t, m]/n!^2, {m, 0, 2n}], {n, 0, 8}] // Flatten  (* Jean-François Alcover, Jan 25 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 (2 in this case), k is the number of cards of each kind 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 x^j of the rook polynomial.

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

Original entry on oeis.org

1, 1, 0, 1, 4, 0, 16, 0, 4, 36, 0, 324, 0, 324, 0, 36, 576, 0, 9216, 0, 20736, 0, 9216, 0, 576, 14400, 0, 360000, 0, 1440000, 0, 1440000, 0, 360000, 0, 14400, 518400, 0, 18662400, 0, 116640000, 0, 207360000, 0, 116640000

Offset: 0

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

This is a triangle of card matching numbers. Two decks each have 2 kinds of cards, n of each kind. The first deck is laid out in order. The second deck is shuffled and laid out next to the first. A match occurs if a card from the second deck is next to a card of the same kind from the first deck. 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)!.

rows are of length 1,3,5,7,...

			There are 16 ways of matching exactly 2 cards when there are 2 cards of each kind and 2 kinds of card so T(2,2)=16.

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

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

Original entry on oeis.org

1, 2, 3, 0, 1, 10, 24, 27, 16, 12, 0, 1, 56, 216, 378, 435, 324, 189, 54, 27, 0, 1, 346, 1824, 4536, 7136, 7947, 6336, 3936, 1728, 684, 128, 48, 0, 1, 2252, 15150, 48600, 99350, 144150, 156753, 131000, 87075, 45000, 19300, 6000

Offset: 0

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

This is a triangle of card matching numbers. A deck has 3 kinds of cards, n of each kind. The deck is shuffled and dealt in to 3 hands each with n cards. 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)!/n!^3).
Rows have lengths 1,4,7,10,...
Analogous to A008290. - Zerinvary Lajos, Jun 22 2005

			There are 27 ways of matching exactly 2 cards when there are 2 cards of each kind and 3 kinds of card so T(2,2)=27.

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.

D. Callan, A combinatorial interpretation for an identity of Barrucand, JIS 11 (2008) 08.3.4.
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 7 do seq(coeff(f(t,3,n),t,m)/n!^3,m=0..3*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, 3, n], t, m]/n!^3, {n, 0, 5}, {m, 0, 3*n}] // Flatten (* Jean-François Alcover, Mar 04 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 (3 in this case), k is the number of cards of each kind 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.

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

Original entry on oeis.org

1, 2, 3, 0, 1, 80, 192, 216, 128, 96, 0, 8, 12096, 46656, 81648, 93960, 69984, 40824, 11664, 5832, 0, 216, 4783104, 25214976, 62705664, 98648064, 109859328, 87588864, 54411264, 23887872, 9455616, 1769472, 663552, 0

Offset: 0

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

This is a triangle of card matching numbers. Two decks each have 3 kinds of cards, n of each kind. The first deck is laid out in order. The second deck is shuffled and laid out next to the first. A match occurs if a card from the second deck is next to a card of the same kind from the first deck. 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)!.

rows are of length 1,4,7,10,...

			There are 216 ways of matching exactly 2 cards when there are 2 cards of each kind and 3 kinds of card so T(2,2)=216.

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,3,n),t,m),m=0..3*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, 3, n], t, m], {n, 0, 5}, {m, 0, 3*n}] // Flatten (* Jean-François Alcover, Oct 21 2013, after Maple *)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A059057 Penrice Christmas gift numbers, Card-matching numbers (Dinner-Diner matching numbers).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica