A293211 -id:A293211 - cp's OEIS frontend

A002467 The game of Mousetrap with n cards (given n letters and n envelopes, how many ways are there to fill the envelopes so that at least one letter goes into its right envelope?).

0, 1, 1, 4, 15, 76, 455, 3186, 25487, 229384, 2293839, 25232230, 302786759, 3936227868, 55107190151, 826607852266, 13225725636255, 224837335816336, 4047072044694047, 76894368849186894, 1537887376983737879, 32295634916658495460, 710503968166486900119

Offset: 0

N. J. A. Sloane, Jeffrey Shallit

a(n) is the number of permutations in the symmetric group S_n that have a fixed point, i.e., they are not derangements (A000166). - Ahmed Fares (ahmedfares(AT)my-deja.com), May 08 2001
a(n+1)=p(n+1) where p(x) is the unique degree-n polynomial such that p(k)=k! for k=0,1,...,n. - Michael Somos, Oct 07 2003
The termwise sum of this sequence and A000166 gives the factorial numbers. - D. G. Rogers, Aug 26 2006, Jan 06 2008
a(n) is the number of deco polyominoes of height n and having in the last column an odd number of cells. A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column. Example: a(2)=1 because the horizontal domino is the only deco polyomino of height 2 having an odd number of cells in the last column. - Emeric Deutsch, May 08 2008
Starting (1, 4, 15, 76, 455, ...) = eigensequence of triangle A127899 (unsigned). - Gary W. Adamson, Dec 29 2008
(n-1) | a(n), hence a(n) is never prime. - Jonathan Vos Post, Mar 25 2009
a(n) is the number of permutations of [n] that have at least one fixed point = number of positive terms in n-th row of the triangle in A170942, n > 0. - Reinhard Zumkeller, Mar 29 2012
Numerator of partial sum of alternating harmonic series, provided that the denominator is n!. - Richard Locke Peterson, May 11 2020
a(n) is the number of terms in the polynomial expansion of the determinant of a n X n matrix that contains at least one diagonal element. - Adam Wang, May 28 2025

			G.f. = x + x^2 + 4*x^3 + 15*x^4 + 76*x^5 + 455*x^6 + 3186*x^7 + 25487*x^8 + ...

R. K. Guy, Unsolved Problems Number Theory, E37.
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).

Alois P. Heinz, Table of n, a(n) for n = 0..450 (first 101 terms from T. D. Noe)
E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.
P. R. de Montmort, On the Game of Thirteen (1713), reprinted in Annotated Readings in the History of Statistics, ed. H. A. David and A. W. F. Edwards, Springer-Verlag, 2001, pp. 25-29.
Sergi Elizalde, Bijections for restricted inversion sequences and permutations with fixed points, arXiv:2006.13842 [math.CO], 2020.
R. K. Guy, Letter to N. J. A. Sloane, Feb 10 1993
R. K. Guy and R. J. Nowakowski, Mousetrap, Preprint, Feb 10 1993 [Annotated scanned copy]
R. K. Guy and S. Washburn, Correspondence, Nov. - Dec. 1991
T. Kotek, J. A. Makowsky, Recurrence Relations for Graph Polynomials on Bi-iterative Families of Graphs, arXiv preprint arXiv:1309.4020 [math.CO], 2013.
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.
Alexsandar Petojevic, The Function vM_m(s; a; z) and Some Well-Known Sequences, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.7.
Simon Plouffe, Exact formulas for Integer Sequences.
A. Steen, Some formulas respecting the game of mousetrap, Quart. J. Pure Applied Math., 15 (1878), 230-241.
L. Takacs, The Problem of Coincidences, Archive for History of Exact Sciences, Volume 21, No. 3, Sept. 1980. pp 229-244, paragraphs 5 and 7.
Eric Weisstein's World of Mathematics, Mousetrap

Cf. A002468, A002469, A028306, A047920, A052169, A127899, A276975.
Row sums of A068106.
Column k=1 of A293211.
Column k=0 of A299789, A306234, and of A324362.

a := proc(n) -add((-1)^i*binomial(n, i)*(n-i)!, i=1..n) end;
a := n->-n!*add((-1)^k/k!, k=1..n): seq(a(n), n=0..20); # Zerinvary Lajos, May 25 2007
a := n -> simplify(GAMMA(n+1) - GAMMA(n+1, -1)*exp(-1)):
seq(a(n), n=0..20); # Peter Luschny, Feb 28 2017

Denominator[k=1; NestList[1+1/(k++ #1)&,1,12]] (* Wouter Meeussen, Mar 24 2007 *)
a[ n_] := If[ n < 0, 0, n! - Subfactorial[n]] (* Michael Somos, Jan 25 2014 *)
a[ n_] := If[ n < 1, 0, n! - Round[ n! / E]] (* Michael Somos, Jan 25 2014 *)
a[ n_] := If[ n < 0, 0, n! - (-1)^n HypergeometricPFQ[ {- n, 1}, {}, 1]](* Michael Somos, Jan 25 2014 *)
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ (1 - Exp[ -x] ) / (1 - x), {x, 0, n}]] (* Michael Somos, Jan 25 2014 *)
RecurrenceTable[{a[n] == (n - 1) ( a[n - 1] + a[n - 2]), a[0] == 0, a[1] == 1}, a[n], {n, 20}] (* Ray Chandler, Jul 30 2015 *)

{a(n) = if( n<1, 0, n * a(n-1) - (-1)^n)} /* Michael Somos, Mar 24 2003 */

{a(n) = if( n<0, 0, n! * polcoeff( (1 - exp( -x + x * O(x^n))) / (1 - x), n))} /* Michael Somos, Mar 24 2003 */

a(n) = if(n<1,0,subst(polinterpolate(vector(n,k,(k-1)!)),x,n+1))

A002467(n) = if(n<1, 0, n*A002467(n-1)-(-1)^n); \\ Joerg Arndt, Apr 22 2013

a(n) = n! - A000166(n) = A000142(n) - A000166(n).
E.g.f.: (1 - exp(-x)) / (1 - x). - Michael Somos, Aug 11 1999
a(n) = (n-1)*(a(n-1) + a(n-2)), n > 1; a(1) = 1. - Michael Somos, Aug 11 1999
a(n) = n*a(n-1) - (-1)^n. - Michael Somos, Aug 11 1999
a(0) = 0, a(n) = floor(n!(e-1)/e + 1/2) for n > 0. - Michael Somos, Aug 11 1999
a(n) = - n! * Sum_{i=1..n} (-1)^i/i!. Limit_{n->infinity} a(n)/n! = 1 - 1/e. - Gerald McGarvey, Jun 08 2004
Inverse binomial transform of A002627. - Ross La Haye, Sep 21 2004
a(n) = (n-1)*(a(n-1) + a(n-2)), n > 1. - Gary Detlefs, Apr 11 2010
a(n) = n! - floor((n!+1)/e), n > 0. - Gary Detlefs, Apr 11 2010
For n > 0, a(n) = {(1-1/exp(1))*n!}, where {x} is the nearest integer. - Simon Plouffe, conjectured March 1993, added Feb 17 2011
0 = a(n) * (a(n+1) + a(n+2) - a(n+3)) + a(n+1) * (a(n+1) + 2*a(n+2) - a(n+3)) + a(n+2) * (a(n+2)) if n >= 0. - Michael Somos, Jan 25 2014
a(n) = Gamma(n+1) - Gamma(n+1, -1)*exp(-1). - Peter Luschny, Feb 28 2017
a(n) = Sum_{k=0..n-1} A047920(n-1,k). - Alois P. Heinz, Sep 01 2021

A132961 Total number of all distinct cycle sizes in all permutations of [n].

Original entry on oeis.org

1, 2, 9, 38, 215, 1384, 10409, 86946, 825075, 8541998, 97590779, 1205343952, 16148472977, 231416203212, 3560209750005, 58104163643054, 1008693571819919, 18477578835352366, 357476371577422955, 7258865626801695048, 154893910336866444009, 3454112338490001478772

Offset: 1

Vladeta Jovovic, Sep 06 2007

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..450

Cf. A000254, A132958, A132959, A132960, A132962, A132963.

Row sums of A293211.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, [1, 0], `if`(i<1, 0,
      add(multinomial(n, n-i*j, i$j)/j!*(i-1)!^j*(p-> p+
      [0, p[1]*`if`(j>0, 1, 0)])(b(n-i*j, i-1)), j=0..n/i)))
    end:
a:= n-> b(n$2)[2]:
seq(a(n), n=1..30);  # Alois P. Heinz, Oct 21 2015

Rest[ Range[0, 22]! CoefficientList[ Series[1/(1 - x) Sum[1 - Exp[ -x^k/k], {k, 25}], {x, 0, 22}], x]] (* Robert G. Wilson v, Sep 13 2007 *)

E.g.f.: 1/(1-x)*Sum_{k>0} (1-exp(-x^k/k)). Exponential convolution of A132960(n) and n!: a(n) = n!*Sum_{k=1..n} A132960(k)/k!.

More terms from Robert G. Wilson v, Sep 13 2007

A027616 Number of permutations of n elements containing a 2-cycle.

Original entry on oeis.org

0, 0, 1, 3, 9, 45, 285, 1995, 15855, 142695, 1427895, 15706845, 188471745, 2450132685, 34301992725, 514529890875, 8232476226975, 139952095858575, 2519137759913775, 47863617438361725, 957272348112505425, 20102719310362613925, 442259824841726816925, 10171975971359716789275

Offset: 0

Joe Keane (jgk(AT)jgk.org)

nonn

Robert Israel, Table of n, a(n) for n = 0..449
Larry Carter and Stan Wagon, The Mensa Correctional Institute, The American Mathematical Monthly 125.4 (2018): 306-319.

Cf. A000266, A088436, A114320.

Column k=2 of A293211.

A027616:= func< n | Factorial(n)*(1- (&+[(-1/2)^j/Factorial(j): j in [0..Floor(n/2)]]) ) >;
[A027616(n): n in [0..30]]; // G. C. Greubel, Aug 05 2022

S:= series((1-exp(-x^2/2))/(1-x), x, 101):
seq(coeff(S,x,j)*j!,j=0..100); # Robert Israel, May 12 2016

nn=30; Table[n!,{n,0,nn}]-Range[0,nn]!CoefficientList[Series[Exp[-x^2/2]/(1-x),{x,0,nn}],x]  (* Geoffrey Critzer, Oct 20 2012 *)

a(n) = n! * (1 - sum(k=0,floor(n/2), (-1)^k / (2^k * k!) ) );
/* Joerg Arndt, Oct 20 2012 */

N=33; x='x+O('x^N);
v=Vec( 'a0 + serlaplace( (1-exp(-x^2/2))/(1-x) ) );
v[1]-='a0;  v
/* Joerg Arndt, Oct 20 2012 */

def A027616(n): return factorial(n)*(1-sum((-1/2)^k/factorial(k) for k in (0..(n//2))))
[A027616(n) for n in (0..30)] # G. C. Greubel, Aug 05 2022

E.g.f.: (1 - exp(-x^2/2)) / (1-x).
a(n) = n! * ( 1 - Sum_{k=0..floor(n/2)} (-1)^k / (2^k * k!) ).
a(n) + A000266(n) = n!. - Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 09 2003
Limit_{n -> oo} a(n)/n! = 1 - e^(-1/2) = 1 - A092605. - Michel Marcus, Aug 08 2013

Added more terms, Geoffrey Critzer, Oct 20 2012

A052145 a(n) = (2n-1)*(2n-1)!/n.

Original entry on oeis.org

1, 9, 200, 8820, 653184, 73180800, 11564467200, 2451889440000, 671854030848000, 231125690776780800, 97537253236899840000, 49549698749529538560000, 29829250083328819200000000, 20999962511521107738624000000, 17094073187896757112117657600000

Offset: 1

N. J. A. Sloane, Jan 23 2000

This is the number of permutations of 2n letters having a cycle of length n. - Marko Riedel, Apr 21 2015

			For n=2, there are 9 permutations of [4] = { 1, 2, 3, 4 } which have a cycle of length 2: each of the 4*3/2 = 6 transpositions, plus the 3 different possible products of two transpositions. - _M. F. Hasler_, Apr 21 2015

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.68(d).

Alois P. Heinz, Table of n, a(n) for n = 1..225
Math Stackexchange, How many permutations

Cf. A126074, A293211.

[(2*n-1)*Factorial(2*n-1)/n: n in [1..20]]; // Vincenzo Librandi, Apr 22 2015

Table[(2 n - 1) (2 n - 1)! / n, {n, 30}] (* Vincenzo Librandi, Apr 22 2015 *)

a(n)=(2*n-1)*(2*n-1)!/n \\ Charles R Greathouse IV, Apr 21 2015

a(n) = 2*m*m!/(m+1) where m=2n-1.
a(n) = A126074(2n,n). - Alois P. Heinz, Apr 21 2017
a(n) = A293211(2n,n). - Alois P. Heinz, Oct 11 2017

A122974 Triangle T(n,k), the number of permutations on n elements that have no cycles of length k.

Original entry on oeis.org

0, 1, 1, 2, 3, 4, 9, 15, 16, 18, 44, 75, 80, 90, 96, 265, 435, 520, 540, 576, 600, 1854, 3045, 3640, 3780, 4032, 4200, 4320, 14833, 24465, 29120, 31500, 32256, 33600, 34560, 35280, 133496, 220185, 259840, 283500, 290304, 302400, 311040, 317520, 322560

Offset: 1

Dennis P. Walsh, Oct 27 2006

Read as sequence, a(n) is the number of permutations on j elements with no cycles of length i where j=round((2*n)^.5) and i=n-C(j,2).

T(n,k) generalizes several sequences already in the On-Line Encyclopedia, such as A000166, the number of permutations on n elements with no fixed points and A000266, the number of permutations on n elements with no transpositions (i.e., no 2-cycles). See the cross references for further examples.

			T(3,2)=3 since there are exactly 3 permutations of 1,2,3 that have no cycles of length 2, namely, (1)(2)(3),(1 2 3) and (2 1 3).
Triangle T(n,k) begins:
      0;
      1,     1;
      2,     3,     4;
      9,    15,    16,    18;
     44,    75,    80,    90,    96;
    265,   435,   520,   540,   576,   600;
   1854,  3045,  3640,  3780,  4032,  4200,  4320;
  14833, 24465, 29120, 31500, 32256, 33600, 34560, 35280;
  ...

Alois P. Heinz, Rows for n = 1..141, flattened
Dennis P. Walsh, The Number of Permutations with No k-Cycles.

Cf. T(n, 1)=A000166 for n=>1 T(n, 2)=A000266 for n=>2 T(n, 3)=A000090 for n=>3 T(n, 4)=A000138 for n=>4 T(n, 5)=A060725 for n=>5 T(n, 6)=A060726 for n=>6 T(n, 7)=A060727 for n=>7.

T(n,n) gives A094304(n+1).

seq((round((2*n)^.5))!*sum((-1/(n-binomial(round((2*n)^.5),2)))^r/r!,r=0..floor(round((2*n)^.5)/(n-binomial(round((2*n)^.5),2)))),n=1..66);
# second Maple program:
T:= proc(n, k) option remember; `if`(n=0, 1, add(`if`(j=k, 0,
      T(n-j, k)*binomial(n-1, j-1)*(j-1)!), j=1..n))
    end:
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Nov 24 2019

T[n_, k_] := T[n, k] = If[n==0, 1, Sum[If[j==k, 0, T[n - j, k] Binomial[n - 1, j - 1] (j - 1)!], {j, 1, n}]];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Dec 08 2019, after Alois P. Heinz *)

T(n,k)=n!*sum r=0..floor(n/k)((-1/k)^r/r!) E.G.F: exp(-x^k/k)/(1-x) a(n)=(round((2*n)^.5))!*sum((-1/(n-binomial(round((2*n)^.5),2)))^r/r!,r=0..floor(round((2*n)^.5)/(n-binomial(round((2*n)^.5),2)))).

T(n,k) = n! - A293211(n,k). - Alois P. Heinz, Nov 24 2019

A027617 Number of permutations of n elements containing a 3-cycle.

Original entry on oeis.org

0, 0, 0, 2, 8, 40, 200, 1400, 11200, 103040, 1030400, 11334400, 135766400, 1764963200, 24709484800, 370687116800, 5930993868800, 100826895769600, 1814871926067200, 34482566595276800, 689651331905536000, 14482682605174784000, 318619017313845248000

Offset: 0

Joe Keane (jgk(AT)jgk.org)

nonn

a(n)/n! is asymptotic to 1-e^(-1/3) = 1 - A092615. - Michel Marcus, Aug 08 2013

Alois P. Heinz, Table of n, a(n) for n = 0..200

Column k=3 of A293211.

nn=20;Range[0,nn]!CoefficientList[Series[1/(1-x)-Exp[-x^3/3]/(1-x), {x,0,nn}],x]  (* Geoffrey Critzer, Jan 23 2013 *)

a(n) = n! * (1 - sum(k=0, floor(n/3), (-1)^k/(k!*3^k) ) ); \\ Stéphane Rézel, Dec 11 2019

a(n) = n! * ( 1 - Sum_{k=0..floor(n/3)} (-1)^k / (3^k * k!) ).
E.g.f.: 1/(1-x) - exp(-x^3/3)/(1-x). - Geoffrey Critzer, Jan 23 2013
Recurrence: a(n) = n*a(n-1) - (n-2)*(n-1)*a(n-3) + (n-3)*(n-2)*(n-1)*a(n-4). - Vaclav Kotesovec, Aug 13 2013
Conjectures from Stéphane Rézel, Dec 11 2019: (Start)
Recurrence: a(n) = n*a(n-1), for n > 3 and n !== 0 (mod 3);
for k > 1, a(3*k) = a(3*k-1)*S(k)/S(k-1) where S(k) = 3*k*S(k-1) - (-1)^k with S(1) = 1.
(End)

More terms from Geoffrey Critzer, Jan 23 2013

cp's OEIS Frontend

A002467 The game of Mousetrap with n cards (given n letters and n envelopes, how many ways are there to fill the envelopes so that at least one letter goes into its right envelope?).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

PARI

Formula

A132961 Total number of all distinct cycle sizes in all permutations of [n].

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A027616 Number of permutations of n elements containing a 2-cycle.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

Extensions

A052145 a(n) = (2n-1)*(2n-1)!/n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A122974 Triangle T(n,k), the number of permutations on n elements that have no cycles of length k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A027617 Number of permutations of n elements containing a 3-cycle.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI