A002468 The game of Mousetrap with n cards: the number of permutations of n cards having at least one hit after 2.

0, 0, 1, 3, 13, 65, 397, 2819, 22831, 207605, 2094121, 23205383, 280224451, 3662810249, 51523391965, 776082247979, 12463259986087, 212573743211549, 3837628837381201, 73108996989052175, 1465703611456618891, 30847249002794047793, 679998362512214208901, 15668677914172813691699, 376683592679293811722735

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

The subsequence of primes begins: 3, 13, 397, 2819, no more through a(19). - Jonathan Vos Post, Feb 01 2011

References

• R. K. Guy and R. J. Nowakowski, "Mousetrap," in D. Miklos, V. T. Sos and T. Szonyi, eds., Combinatorics, Paul Erdős is Eighty. Bolyai Society Math. Studies, Vol. 1, pp. 193-206, 1993.
• 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

• Joerg Arndt, Table of n, a(n) for n = 1..102
• R. K. Guy and R. J. Nowakowski, Mousetrap, Preprint, Feb 10 1993 [Annotated scanned copy]
• J. Metzger, Email to N. J. A. Sloane, Apr 30 1991
• Daniel J. Mundfrom, A problem in permutations: the game of 'Mousetrap'. European J. Combin. 15 (1994), no. 6, 555-560.
• A. Steen, Some formulas respecting the game of mousetrap, Quart. J. Pure Applied Math., 15 (1878), 230-241.
• Eric Weisstein's World of Mathematics, Mousetrap

Crossrefs

Cf. A002467, A002468, A002469, A028306, etc.

Programs

Mathematica

a[n_] := (n-2)*(n-2)!-(n-4)*Subfactorial[n-3]-(n-3)*Subfactorial[n-2]; a[1]=a[2]=0; a[3]=1; Table[a[n], {n, 1, 21}] (* Jean-François Alcover, Dec 12 2014 *)

Formula

a(n) = A001563(n) - A002469(n+2). (corrected by Sean A. Irvine and Joerg Arndt, Feb 10 2014)

Extensions

Added two more terms, Joerg Arndt, Feb 15 2014