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