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