login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A028305 Triangle of numbers of permutations eliminating just k cards out of n in game of Mousetrap. 4
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,7

COMMENTS

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

REFERENCES

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.

LINKS

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.

FORMULA

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

EXAMPLE

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,

  ...

MAPLE

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

CROSSREFS

Cf. A000166, A007709, A007710.

Sequence in context: A294525 A011218 A171244 * A347086 A137349 A087318

Adjacent sequences:  A028302 A028303 A028304 * A028306 A028307 A028308

KEYWORD

tabl,nonn,hard,more

AUTHOR

N. J. A. Sloane

EXTENSIONS

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

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 23 20:42 EDT 2021. Contains 347617 sequences. (Running on oeis4.)