%I A000316 M3702 N1513
%S A000316 0,4,80,4752,440192,59245120,10930514688,2649865335040,817154768973824,
%T A000316 312426715251262464,145060238642780180480,80403174342119992692736,
%U A000316 52443098500204184915312640,39764049487996490505336537088
%N A000316 Number of permutations with no hits on 2 main diagonals.
%C 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. The probability of no matches is 
               a(n)/(2n)!.
%C A000316 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 (dimad72(AT)gmail.com), Dec 17 2006
%C A000316 (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 (dimad72(AT)gmail.com), Dec 17 2006
%D A000316 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A000316 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A000316 F. N. David and D. E. Barton, Combinatorial Chance, Hafner, NY, 1962, 
               Ch. 7 and Ch. 12.
%D A000316 F. F. Knudsen and I. Skau, On the Asymptotic Solution of a Card-Matching 
               Problem, Mathematics Magazine 69 (1996), 190-197.
%D A000316 B. H. Margolius, The Dinner-Diner Matching Problem, Mathematics Magazine, 
               76 (2003), 107-118.
%D A000316 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 
               187.
%H A000316 T. D. Noe, <a href="b000316.txt">Table of n, a(n) for n=1..100</a>
%H A000316 Barbara H. Margolius, <a href="http://academic.csuohio.edu/bmargolius/
               homepage/dinner/dinner/cardentry.htm">Dinner-Diner Matching Probabilities</
               a>
%H A000316 <a href="Sindx_Ca.html#cardmatch">Index entries for sequences related 
               to card matching</a>
%F A000316 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 (2 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 Riordan). coeff(R(x, 
               n, k), x, j) indicates the coefficient for x^j of the rook polynomial.
%F A000316 a(n) = n! * sum((-1)^b * 2^{a+2b} * (2n-2a-b)! / (a! * b! * (n-a-b)!), 
               a,b >= 0, a+b <= n) a(n) = n * a(n-1) + n! * 4^n * sum((-1)^a / (a! 
               * 2^a), a=0 to n) - Dan Dima (dimad72(AT)gmail.com), Dec 17 2006
%e A000316 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.
%p A000316 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), n=0..18);
%Y A000316 2^n*A000459.
%Y A000316 Sequence in context: A013007 A013008 A013180 this_sequence A012106 A156103 
               A116189
%Y A000316 Adjacent sequences: A000313 A000314 A000315 this_sequence A000317 A000318 
               A000319
%K A000316 nonn,easy,nice
%O A000316 1,2
%A A000316 N. J. A. Sloane (njas(AT)research.att.com).
%E A000316 Formulae, more terms etc. from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), 
               Dec 22 2000