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

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

Author

N. J. A. Sloane

Keywords

• tabl
• nonn
• hard

Comments

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

Examples

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

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.

Crossrefs

Cf. A000166, A007709, A007710.

Programs

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

Formula

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

Extensions

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