|
|
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
|
R. K. Guy and R. J. Nowakowski, Mousetrap, Preprint, Feb 10 1993 [Annotated scanned copy]
|
|
FORMULA
|
|
|
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
|
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:
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|