A007709 -id:A007709 - cp's OEIS frontend

A007711 Number of unreformed permutations of {1,...,n}.

0, 1, 4, 18, 105, 636, 4710, 38508, 352902, 3563297, 39467081, 475326930, 6198134207, 86912048471, 1305146666727, 20897040866280

Offset: 1

N. J. A. Sloane

			For n=3, the 4 unreformed permutations are 123, 231, 312, 213, so a(3)=4. Also 132->123, 321->213 are reformable.

A. M. Bersani, "Reformed permutations in Mousetrap and its generalizations", preprint MeMoMat n. 15/2005.
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 and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

A. M. Bersani, On the game Mousetrap.
A. M. Bersani, Reformed Permutations in mousetrap and its generalizations, INTEGERS, 10 (2010), #G01.
R. K. Guy and R. J. Nowakowski, Mousetrap, Preprint, Feb 10 1993 [Annotated scanned copy]
R. K. Guy and R. J. Nowakowski, Mousetrap, Amer. Math. Monthly, 101 (1994), 1007-1010.

Cf. A007709, A007712, A055459, A067950.

a(n) = n! - A007709(n). - Sean A. Irvine, Jan 17 2018

More terms from Kok Seng Chua (chuaks(AT)ihpc.nus.edu.sg), Mar 06 2002
2 more terms from Alberto M. Bersani (bersani(AT)dmmm.uniroma1.it), Feb 07 2007
One more term from Alberto M. Bersani (bersani(AT)dmmm.uniroma1.it), Feb 24 2008
a(1) corrected by Joerg Arndt, Dec 24 2014

A007712 Number of once reformable permutations of {1,2,...,n}.

Original entry on oeis.org

1, 2, 4, 14, 72, 316, 1730, 9728, 64330, 444890, 3645441, 28758111, 265434293, 2522822881, 25717118338

Offset: 2

N. J. A. Sloane

			For n=3, 123, 312, 231, 213 are unreformed but 132->123, 321->213 so a(3)=2.

A. M. Bersani, "Reformed permutations in Mousetrap and its generalizations", preprint MeMoMat, No. 15, 2005.
R. K. Guy, Unsolved Problems Number Theory, Section 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 and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

A. M. Bersani, On the game Mousetrap.
R. K. Guy and R. J. Nowakowski, Mousetrap, Preprint, Feb 10 1993 [Annotated scanned copy].
R. K. Guy and R. J. Nowakowski, Mousetrap Amer. Math. Monthly, 101 (1994), 1007-1010.

Cf. A007709, A007711, A055459, A067950.

More terms from Kok Seng Chua (chuaks(AT)ihpc.nus.edu.sg), Mar 06 2002
2 more terms from Alberto M. Bersani (bersani(AT)dmmm.uniroma1.it), Feb 07 2007
One more term from Alberto M. Bersani (bersani(AT)dmmm.uniroma1.it), Feb 24 2008

A055459 a(n) = number of permutations of {1,...,n} which are twice but not 3-times reformable.

Original entry on oeis.org

2, 1, 11, 14, 81, 242, 1142, 4771, 29009, 127876, 805947, 4868681, 31862753

Offset: 1

Robert G. Wilson v, Jul 05 2000

nonn

Consider a permutation {a1,...,an}; start counting from the beginning: if a1 is not 1, a1 is replaced at the end of an, until we reach the first i such that ai=i in which case ai is removed and the count start from 1 again. The permutation is unreformable if a count of n+1 is reached before all ai are removed. Otherwise, the order of removal of the ai defines the reformed permutation.

			a(4)=2 since 4213->2134->3214, 1432->1423->1234 are the only two permutations that can be reformed twice.

A. M. Bersani, "Reformed permutations in Mousetrap and its generalizations", preprint MeMoMat n. 15/2005.
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.

A. M. Bersani, On the game Mousetrap.
R. K. Guy and R. J. Nowakowski, Mousetrap Amer. Math. Monthly, 101 (1994), 1007-1010.

Cf. A007709, A007711, A007712, A067950.

Edited by Kok Seng Chua (chuaks(AT)ihpc.nus.edu.sg), Mar 06 2002
2 more terms from Alberto M. Bersani (bersani(AT)dmmm.uniroma1.it), Feb 07 2007
One more term from Alberto M. Bersani (bersani(AT)dmmm.uniroma1.it), Feb 24 2008

A067950 a(n) = number of 3-times (but not 4-times) reformable permutation of {1,...,n}.

Original entry on oeis.org

1, 0, 1, 8, 31, 56, 219, 605, 2485, 9697, 40571

Offset: 6

Kok Seng Chua (chuaks(AT)ihpc.nus.edu.sg), Mar 06 2002

			a(6)=1, 165342->132564->125346->136524.

A. M. Bersani, "Reformed permutations in Mousetrap and its generalizations", preprint MeMoMat n. 15/2005.
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.

A. M. Bersani, On the game Mousetrap.
R. K. Guy and R. J. Nowakowski, Mousetrap Amer. Math. Monthly, 101 (1994), 1007-1010.

Cf. A007709, A007711, A007712, A055459.

2 more terms from Alberto M. Bersani (bersani(AT)dmmm.uniroma1.it), Feb 07 2007

One more term from Alberto M. Bersani (bersani(AT)dmmm.uniroma1.it), Feb 24 2008

A028305 Triangle of numbers of permutations eliminating just k cards out of n in game of Mousetrap.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 2, 2, 0, 2, 9, 6, 3, 0, 6, 44, 31, 19, 11, 0, 15, 265, 180, 105, 54, 32, 0, 84, 1854, 1255, 771, 411, 281, 138, 0, 330, 14833, 9949, 6052, 3583, 2057, 1366, 668, 0, 1812, 133496, 89162, 55340, 32135, 19026, 12685, 6753, 4305, 0, 9978, 1334961, 886837, 547922, 331930, 193538, 117323, 79291, 45536, 25959, 0, 65503

Offset: 0

N. J. A. Sloane

Triangle T(n,k), 0 <= k <= n

			Triangle begins:
     1,
     0,    1,
     1,    0,   1,
     2,    2,   0,   2,
     9,    6,   3,   0,   6,
    44,   31,  19,  11,   0,  15,
   265,  180, 105,  54,  32,   0, 84,
  1854, 1255, 771, 411, 281, 138,  0, 330,
  ...

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.
S. Washburn, T. Marlowe and C. T. Ryan, Discrete Mathematics, Addison-Wesley, 1999, page 326.

Georg Fischer, Table of n, a(n) for n = 0..107 (terms 36..65 from Martin Renner)
Arthur Cayley, On the game of Mousetrap, in: Quarterly Journal of Pure and Applied Mathematics 15 (1878), p. 8-10.
R. K. Guy and R. J. Nowakowski, Mousetrap, Preprint, Feb 10 1993 [Annotated scanned copy]
Adolph Steen, Some formulas respecting the game of Mousetrap, Quarterly Journal of Pure and Applied Mathematics 15 (1878), p. 230-241.

Cf. A000166, A007709, A007710.

A028305:=proc(n)
  local P, j, M, K, A, i, K_neu, k, m;
  P:=combinat[permute](n):
  for j from 0 to n do
    M[j]:=0:
  od:
  for j from 1 to nops(P) do
    K:=P[j]:
    A:=[]:
    for i while nops(K)>0 do
      K_neu:=[]:
      for k from 1 to n do
        m:=nops(K);
        if k mod m = 0 then
          if K[m]=k then
            K_neu:=[seq(K[j],j=1..m-1)];
            A:=[op(A),k];
          else next;
          fi;
        else
          if K[k mod m]=k then
            K_neu:=[seq(K[j],j=(k mod m)+1..m),seq(K[j],j=1..(k mod m)-1)];
            A:=[op(A),k];
          else next;
          fi;
        fi;
        if nops(K_neu)<>0 then break; fi;
      od;
      if nops(K_neu)<>0 then
        K:=K_neu;
      else break;
      fi;
    od:
    M[nops(A)]:=M[nops(A)]+1;
  od:
  seq(M[j],j=0..n);
end:
# Martin Renner, Sep 03 2015

T(n,0) = A000166(n), T(n,1) = A007710(n), T(n,n-1) = A000004(n) = 0, T(n,n) = A007709(n).

a(36)-a(65) from Martin Renner, Sep 02 2015

A127966 a(n) = number of 4-times (but not 5-times) reformable permutation of {1,...,n}.

Original entry on oeis.org

2, 1, 1, 4, 14, 57

Offset: 11

Alberto M. Bersani (bersani(AT)dmmm.uniroma1.it), Feb 09 2007

For n=16 we have the first example of a 5-reformed (but not 6-reformed) permutation: 1, 16, 12, 15, 6, 8, 14, 10, 9, 3, 4, 11, 13, 2, 7, 5 - Alberto M. Bersani (bersani(AT)dmmm.uniroma1.it), Feb 24 2008

A. M. Bersani, ``Reformed permutations in Mousetrap and its generalizations,'' Preprint Me.Mo.Mat. n. 15/2005.
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.

A. M. Bersani, On the game Mousetrap.
R. K. Guy and R. J. Nowakowski, Mousetrap, Amer. Math. Monthly, 101 (1994), 1007-1010.

Cf. A007709, A007710, A007711, A007712, A055459, A067950.

One more term from Alberto M. Bersani (bersani(AT)dmmm.uniroma1.it), Feb 24 2008

A261867 Triangle T(n, k) read by rows (n >= 1, 1 <= k <= n), where row n gives the lexicographically first permutation of n cards that is a winning (or reformed) deck at Cayley's Mousetrap.

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 1, 2, 4, 3, 1, 2, 5, 3, 4, 1, 2, 4, 3, 6, 5, 1, 2, 3, 7, 6, 5, 4, 1, 2, 3, 5, 8, 4, 6, 7, 1, 2, 3, 4, 8, 5, 7, 9, 6, 1, 2, 3, 4, 6, 9, 8, 7, 10, 5, 1, 2, 3, 4, 6, 7, 5, 11, 8, 10, 9, 1, 2, 3, 4, 5, 8, 10, 6, 12, 9, 11, 7, 1, 2, 3, 4, 5, 6, 9, 12, 7, 10, 13, 11, 8, 1, 2, 3, 4, 5, 6, 10, 9, 14, 13, 8, 11, 12, 7, 1, 2, 3, 4, 5, 6, 8, 9, 12, 7, 14, 10, 15, 13, 11

Offset: 1

Martin Renner, Sep 03 2015

			With four cards in the order 1243 the player will win the first time (out of six times), taking the cards away in the order 1342, i.e., the cards held in hand develop from 1243 -> 243 -> 24 -> 2.
Triangle starts with
1
1, 2
1, 3, 2
1, 2, 4, 3
1, 2, 5, 3, 4
...

Arthur Cayley, On the game of Mousetrap, Quarterly Journal of Pure and Applied Mathematics 15 (1878), pp. 8-10.
Adolph Steen, Some formulas respecting the game of Mousetrap, Quarterly Journal of Pure and Applied Mathematics 15 (1878), pp. 230-241.

Cf. A007709, A028305.

cp's OEIS Frontend

A007711 Number of unreformed permutations of {1,...,n}.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

Extensions

A007712 Number of once reformable permutations of {1,2,...,n}.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Extensions

A055459 a(n) = number of permutations of {1,...,n} which are twice but not 3-times reformable.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A067950 a(n) = number of 3-times (but not 4-times) reformable permutation of {1,...,n}.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Extensions

A028305 Triangle of numbers of permutations eliminating just k cards out of n in game of Mousetrap.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

Extensions

A127966 a(n) = number of 4-times (but not 5-times) reformable permutation of {1,...,n}.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A261867 Triangle T(n, k) read by rows (n >= 1, 1 <= k <= n), where row n gives the lexicographically first permutation of n cards that is a winning (or reformed) deck at Cayley's Mousetrap.

Views

Author

Keywords

Examples

Links

Crossrefs