This post extends the traditional derangment problem to calculate number of acceptable placement solution,
with introducing a new concept
step that opening box
i is the
first step, and each of the following step is to open another box whose number equals the number of
ball from the last opened box until found a box whose ball in it is numbered
i. The task
is to find amount of ways to place balls into boxes, so that each box contains exactly one ball, and that
for all
i from 1 to
n, ball
i can be found by opening no more than
step boxes.
It is obvious that
step=1 is like original problem and the number of placement is 1,
placing each ball into the box with the same number. With some error allowed in finding the ball, the problem become interesting.
The idea of this extended problem's solution raises from an easily understandable way of computing original problem's answer
by decomposing the problem into multiple subproblems (solution set size
Dn obtained from
Dn-1
and
Dn-2).
For the nature that it extends the idea of another Chinese post, English version
of this post is currently unavailable. Hope
translation software helps :)