

A000316


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. a(n) is the number of ways of achieving no matches.
(Formerly M3702 N1513)


7



1, 0, 4, 80, 4752, 440192, 59245120, 10930514688, 2649865335040, 817154768973824, 312426715251262464, 145060238642780180480, 80403174342119992692736, 52443098500204184915312640, 39764049487996490505336537088
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Each deck contains 2n cards.
The probability of no matches is a(n)/(2n)!.
n couples meet for a party and they exchange gifts. Each of the 2n writes their name on a piece of paper and puts it into a hat. They take turns drawing names and give their gift to the person whose name they drew. If anyone draws either their own name or the name of their partner, everyone puts the name they have drawn back into the hat and everyone draws anew. a(n) is the number of different permissible drawings.  Dan Dima, Dec 17 2006
(2n)! / a(n) is the expected number of deck shuffles until no matches occur. a(n) / (2n)! is the probability for a permissible drawing to be achieved. (2n)! / a(n) is the expected number of drawings before a permissible drawing is achieved. As n goes to infinity (2n)! / a(n) will strictly decrease very slowly to e^2 ~ 7.38906 (starting from n > 2)  Dan Dima, Dec 17 2006
a(n) equals the permanent of the (2n)X(2n) matrix with 0's along the main diagonal and the antidiagonal, and 1's everywhere else.  John M. Campbell, Jul 11 2011
Also, number of permutations p of (1,...,2n) such that round(p(k)/2) != round(k/2) for all k=1,...,2n (where halfintegers are rounded up).  M. F. Hasler, Sep 30 2015


REFERENCES

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, p. 187.
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).


LINKS

T. D. Noe, Table of n, a(n) for n = 0..100
F. F. Knudsen and I. Skau, On the Asymptotic Solution of a CardMatching Problem, Mathematics Magazine 69 (1996), 190197.
B. H. Margolius, The DinnerDiner Matching Problem, Mathematics Magazine, 76 (2003), 107118.
Barbara H. Margolius, DinnerDiner Matching Probabilities
L. I. Nicolaescu, Derangements and asymptotics of the Laplace transforms of large powers of a polynomial, New York J. Math. 10 (2004) 117131.
John Riordan and N. J. A. Sloane, Correspondence, 1974
Index entries for sequences related to card matching


FORMULA

a(n) = A000459(n)*2^n.
G.f.: Sum_{j=0..n*k} coeff(R(x, n, k), x, j)*(1)^j*(n*kj)! where n is the number of kinds of cards, k is the number of cards of each kind (2 in this case) and R(x, n, k) is the rook polynomial given by R(x, n, k)=(k!^2*Sum_{j=0..k} x^j/((kj)!^2*j!))^n (see Riordan). coeff(R(x, n, k), x, j) indicates the coefficient for x^j of the rook polynomial.
From Dan Dima, Dec 17 2006: (Start)
a(n) = n! * Sum_{a,b >= 0, a+b <= n} (1)^b * 2^(a+2*b) * (2*n2*ab)! / (a! * b! * (nab)!).
a(n) = n * a(n1) + n! * 4^n * Sum_{a=0..n} (1)^a / (a! * 2^a). (End)
a(n) = 2^n * round(2^(n/2 + 3/4)*Pi^(1/2)*exp(2)*n!*BesselK(1/2+n,2^(1/2))) for n > 0.  Mark van Hoeij, Oct 30 2011
Recurrence: (2*n3)*a(n) = 2*(n1)*(2*n1)^2*a(n1) + 4*(n1)*(2*n3)*a(n2)  16*(n2)*(n1)*(2*n1)*a(n3).  Vaclav Kotesovec, Aug 07 2013
From Peter Bala, Jul 07 2014: (Start)
a(n) = Integral_{x>=0} exp(x)*(x^2  4*x + 2)^n dx. Cf. A000166(n) = Integral_{x>=0} exp(x)*(x  1)^n dx.
Asymptotic: a(n) ~ (2*n)!*exp(2)*( 1  1/(2*n)  23/(96*n^2) + O(1/n^3) ). See Nicolaescu. (End)


EXAMPLE

There are 80 ways of achieving zero matches when there are 2 cards of each kind and 3 kinds of card so a(3)=80.
Among the 24 (multiset) permutations of {1,1',2,2'}, only {2,2',1,1'}, {2',2,1,1'}, {2,2',1',1} and {2',2,1',1} have no fixed points, thus a(2)=4.


MAPLE

p := (x, k)>k!^2*sum(x^j/((kj)!^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)*(t1)^j*(n*kj)!, j=0..n*k); seq(f(0, n, 2), n=0..18);


MATHEMATICA

(* b = A000459 *)
b[n_] := b[n] = Switch[n, 0, 1, 1, 0, 2, 1, _, n(2n1) b[n1] + 2n(n1) b[n2]  (2n1)];
a[n_] := b[n] * 2^n;
Array[a, 14] (* JeanFrançois Alcover, Oct 30 2019 *)


PROG

(PARI) a(n)=if(n==0, 1, round(2^(n/2+3/4)/Pi^.5*exp(2)*n!*besselk(1/2+n, 2^.5))<<n) \\ requires sufficient realprecision.  M. F. Hasler, Sep 27 2015
(PARI) \\ Illustration of the multisetfixedpoint interpretation
count(n, c=ceil(vector(n, i, i)/2))=sum(k=1, n!, !setsearch(Set(ceil(Vec(numtoperm(n, k))/2)c), 0))
a(n) = count(2*n) \\ M. F. Hasler, Sep 30 2015


CROSSREFS

Cf. A000166, A000459, A337302.
Sequence in context: A013008 A013180 A322751 * A012106 A156103 A204294
Adjacent sequences: A000313 A000314 A000315 * A000317 A000318 A000319


KEYWORD

nonn,easy,nice


AUTHOR

N. J. A. Sloane


EXTENSIONS

Formulae, more terms etc. from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Dec 22 2000
Edited by M. F. Hasler, Sep 27 2015 and N. J. A. Sloane, Oct 02 2015
a(0)=1 prepended by Andrew Howroyd, Oct 09 2020


STATUS

approved



