Talk:Partial permutation

Recurrence relation

I don't see it. The argument is fairly complex, and doesn't seem correct.

I get

$P(n)=2nP(n-1)-(n-1)^{2}P(n-2).$

Counting as follows. Let the n-element sets be A and B, with distinguished elements a ∈ A and b in B.

P(n−1) where neither a or b is active. (Sets being A−{a} and B−{b}.)

P(n−1) where a maps to b. (Sets being A−{a} and B−{b})

(n−1) P(n−1) where a maps somewhere but not to b (Sets being A−{a} and B−{f(a)}.)

(n−1) P(n−1) where b maps somewhere but not to a. (Sets being A−{f⁻¹(b)} and B−{b}.)

less permutations where a and b map somewhere, but not to each other, which are counted in both of the last two sets.

(n−1)² P(n−2) (Sets being A−{a,f⁻¹(b)} and B−{b,f(a).}

But I think this is complicated enough to need a reference. — Arthur Rubin (talk) 03:53, 15 August 2014 (UTC)