cp's OEIS Frontend

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

%I A028305 #37 Jul 21 2025 14:37:44
%S A028305 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,
%T A028305 84,1854,1255,771,411,281,138,0,330,14833,9949,6052,3583,2057,1366,
%U A028305 668,0,1812,133496,89162,55340,32135,19026,12685,6753,4305,0,9978,1334961,886837,547922,331930,193538,117323,79291,45536,25959,0,65503
%N A028305 Triangle of numbers of permutations eliminating just k cards out of n in game of Mousetrap.
%C A028305 Triangle T(n,k), 0 <= k <= n
%D A028305 R. K. Guy, Unsolved Problems Number Theory, E37.
%D A028305 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.
%D A028305 S. Washburn, T. Marlowe and C. T. Ryan, Discrete Mathematics, Addison-Wesley, 1999, page 326.
%H A028305 Georg Fischer, <a href="/A028305/b028305.txt">Table of n, a(n) for n = 0..107</a> (terms 36..65 from Martin Renner)
%H A028305 Arthur Cayley, <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN600494829_0015&amp;IDDOC=649134">On the game of Mousetrap</a>, in: Quarterly Journal of Pure and Applied Mathematics 15 (1878), p. 8-10.
%H A028305 R. K. Guy and R. J. Nowakowski, <a href="/A002467/a002467_1.pdf">Mousetrap</a>, Preprint, Feb 10 1993 [Annotated scanned copy]
%H A028305 Adolph Steen, <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN600494829_0015&amp;IDDOC=649134">Some formulas respecting the game of Mousetrap</a>, Quarterly Journal of Pure and Applied Mathematics 15 (1878), p. 230-241.
%F A028305 T(n,0) = A000166(n), T(n,1) = A007710(n), T(n,n-1) = A000004(n) = 0, T(n,n) = A007709(n).
%e A028305 Triangle begins:
%e A028305      1,
%e A028305      0,    1,
%e A028305      1,    0,   1,
%e A028305      2,    2,   0,   2,
%e A028305      9,    6,   3,   0,   6,
%e A028305     44,   31,  19,  11,   0,  15,
%e A028305    265,  180, 105,  54,  32,   0, 84,
%e A028305   1854, 1255, 771, 411, 281, 138,  0, 330,
%e A028305   ...
%p A028305 A028305:=proc(n)
%p A028305   local P, j, M, K, A, i, K_neu, k, m;
%p A028305   P:=combinat[permute](n):
%p A028305   for j from 0 to n do
%p A028305     M[j]:=0:
%p A028305   od:
%p A028305   for j from 1 to nops(P) do
%p A028305     K:=P[j]:
%p A028305     A:=[]:
%p A028305     for i while nops(K)>0 do
%p A028305       K_neu:=[]:
%p A028305       for k from 1 to n do
%p A028305         m:=nops(K);
%p A028305         if k mod m = 0 then
%p A028305           if K[m]=k then
%p A028305             K_neu:=[seq(K[j],j=1..m-1)];
%p A028305             A:=[op(A),k];
%p A028305           else next;
%p A028305           fi;
%p A028305         else
%p A028305           if K[k mod m]=k then
%p A028305             K_neu:=[seq(K[j],j=(k mod m)+1..m),seq(K[j],j=1..(k mod m)-1)];
%p A028305             A:=[op(A),k];
%p A028305           else next;
%p A028305           fi;
%p A028305         fi;
%p A028305         if nops(K_neu)<>0 then break; fi;
%p A028305       od;
%p A028305       if nops(K_neu)<>0 then
%p A028305         K:=K_neu;
%p A028305       else break;
%p A028305       fi;
%p A028305     od:
%p A028305     M[nops(A)]:=M[nops(A)]+1;
%p A028305   od:
%p A028305   seq(M[j],j=0..n);
%p A028305 end:
%p A028305 # _Martin Renner_, Sep 03 2015
%Y A028305 Cf. A000166, A007709, A007710.
%K A028305 tabl,nonn,hard
%O A028305 0,7
%A A028305 _N. J. A. Sloane_
%E A028305 a(36)-a(65) from _Martin Renner_, Sep 02 2015