automatic "lotjes trekken"

[Carel Fellinger]

Tim Peters <tim_one at email.msn.com> wrote:
> [Carel Fellinger]
>> ...
>> in the damp and cold days of late November and early December we

> In combinatorics, this is the general problem of permutations with forbidden
> positions:  you can view the lots as mapping the set of people into itself,
> one-to-one and onto.  That is, it's a permutation.  Since a person is not
> allowed to map to themself here, an upper bound is the number of
> "derangements" (great word!) of N people.  A derangement is simply a

indeed a great word!

> permutation where no element maps to itself.  Asymptotically, there are N!/e
> derangements of N things (N! is N factorial = N * (N-1) * ... * 1, and e is
> 2.71828...).  This is an excellent approximation even for small N; e.g., for
> N=5, 5!/e = 120/e ~= 44.15, while the exact number of derangements of 5
> things is 44.

and a nice function, elas it only applies to this one special case.

> Now you *can* systematically count the number of ways to do this without
> backtracking, but accounting for the 2-dimensional geometry of the forbidden
> positions is essential.  This makes it tricky.  Here's how:

...clear and crisp explanation snipped out. It ended with Tim telling
that this non-backtracking approach of him could end up using N!/e function
calls; well that helps:)  So we definitely need those tricks to speed things
up, and especially the second trick seems promissing, but...

> The next twist in the tale is too involved to explain here:  it turns out
> that it's possible to deduce the result from the numbers of ways to place 0,

and how then can this be deduced, what simple function are we to apply? 
please inform us, give us a sign, o master
or is this supposed to be part of the wintery pondering?

still-after-a-non-backtracking-draw-ly y'rs - carel
-- 
groetjes, carel