login
This site is supported by donations to The OEIS Foundation.

 

Logo

"Email this user" was broken Aug 14 to 9am Aug 16. If you sent someone a message in this period, please send it again.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000459 Number of multiset permutations of {1, 1, 2, 2, ..., n, n} with no fixed points.
(Formerly M4750 N2032)
14
1, 0, 1, 10, 297, 13756, 925705, 85394646, 10351036465, 1596005408152, 305104214112561, 70830194649795010, 19629681235869138841, 6401745422388206166420, 2427004973632598297444857, 1058435896607583305978409166, 526149167104704966948064477665 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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

REFERENCES

F. N. David and D. E. Barton, Combinatorial Chance, Hafner, NY, 1962, Ch. 7 and Ch. 12.

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.

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

John Riordan and N. J. A. Sloane, Correspondence, 1974

R. Vidunas, Counting derangements and Nash equilibria, arXiv preprint arXiv:1401.5400, 2014

Wikipedia, Permutations of multisets

Index entries for sequences related to card matching

FORMULA

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

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

EXAMPLE

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)

MAPLE

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

MATHEMATICA

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

PROG

(MAGMA) 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

(PARI) 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

(PARI) { 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

CROSSREFS

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

Sequence in context: A258794 A239775 A059072 * A125288 A217487 A173479

Adjacent sequences:  A000456 A000457 A000458 * A000460 A000461 A000462

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 20 11:34 EDT 2017. Contains 290835 sequences.