(Proposed by Combinatorics; Ferdowsi University of Mashhad, Iran; Mirzavaziri)
Solution. Let ar∈{i1,…,ik}∩{a1,…,ak}. Thus ar=is for some s=r. Now there are two cases:
Case 1. as∈{i1,…,ik}. Let as=it. In this case a derangement x=(x1,…,xn) satisfies the condition xij=aj if and only if the derangement x′=(x1′,…,xit−1′,xit+1′,xn′) of the set [n]∖{it} satisfies the condition xij′=aj′ for all j=t, where aj′=aj for j=s and as′=at. This provides a one to one correspondence between the derangements x=(x1,…,xn) of [n] with xij=aj for the given sets {i1,…,ik} and {a1,…,ak} with ℓ elements in their intersections, and the derangements x′=(x1′,…,xit−1′,xit+1′,xn′) of [n]∖{it} with xij=aj′ for the given sets {i1,…,ik}∖{it} and {a1′,…,ak′}∖{at′} with ℓ−1 elements in their intersections.
Case 2. as∈/{i1,…,ik}. In this case a derangement x=(x1,…,xn) satisfies the condition xij=aj if and only if the derangement x′=(x1′,…,xas−1′,xas+1′,xn′) of the set [n]∖{as} satisfies the condition xij′=aj for all j=s. This provides a one to one correspondence between the derangements x=(x1,…,xn) of [n] with xij=aj for the given sets {i1,…,ik} and {a1,…,ak} with ℓ elements in their intersections, and the derangements x′=(x1′,…,xas−1′,xas+1′,xn′) of [n]∖{as} with xij=aj for the given sets {i1,…,ik}∖{is} and {a1,…,ak}∖{as} with ℓ−1 elements in their intersections.
These considerations show that Δ(n,k,ℓ)=Δ(n−1,k−1,ℓ−1). Iterating this argument we have
Δ(n,k,ℓ)=Δ(n−ℓ,k−ℓ,0).
We can therefore assume that
ℓ=0. We thus evaluate
Δ(n,k,0), where
2k⩽n. For
k=0, we obviously have
Δ(n,0,0)=Dn. For
k⩾1, we claim that
Δ(n,k,0)=Δ(n−1,k−1,0)+Δ(n−2,k−1,0).
For a derangement
x=(x1,…,xn) satisfying
xij=aj there are two cases:
xa1=i1 or
xa1=i1.
If the first case occurs then we have to evaluate the number of derangements of the set [n]∖{i1,a1} for the given sets {i2,…,ik} and {a2,…,ak} with 0 elements in their intersections. The number is equal to Δ(n−2,k−1,0).
If the second case occurs then we have to evaluate the number of derangements of the set [n]∖{a1} for the given sets {i2,…,ik} and {a2,…,ak} with 0 elements in their intersections. The number is equal to Δ(n−1,k−1,0).
We now use induction on k to show that
Δ(n,k,0)=i=0∑k−1(ik−1)n−(k+i)D(n+1)−(k+i),2⩽2k⩽n.
For
k=1 we have
Δ(n,1,0)=Δ(n−1,0,0)+Δ(n−2,0,0)=Dn−1+Dn−2=n−1Dn.
Now let the result be true for
k−1. We can write
Δ(n,k,0)=Δ(n−1,k−1,0)+Δ(n−2,k−1,0)=i=0∑k−2(ik−2)(n−1)−(k−1+i)Dn−(k−1+i)+i=0∑k−2(ik−2)(n−2)−(k−1+i)D(n−1)−(k−1+i)=i=0∑k−2(ik−2)n−(k+i)D(n+1)−(k+i)+i=1∑k−1(i−1k−2)(n−1)−(k+i−1)Dn−(k+i−1)=n−kD(n+1)−k+i=1∑k−2(ik−2)n−(k+i)D(n+1)−(k+i)+n−(2k−1)D(n+1)−(2k−1)+i=1∑k−2(i−1k−2)n−(k+i)D(n+1)−(k+i)=n−kD(n+1)−k+i=1∑k−2[(ik−2)+(i−1k−2)]n−(k+i)D(n+1)−(k+i)+n−(2k−1)D(n+1)−(2k−1)=n−kD(n+1)−k+i=1∑k−2(ik−1)n−(k+i)D(n+1)−(k+i)+n−(2k−1)D(n+1)−(2k−1)=i=0∑k−1(ik−1)n−(k+i)D(n+1)−(k+i).
Remark. As a corollary of the above problem, we can solve the first problem. Let n=2k, ij=j and aj=k+j for j=1,…,k. Then a derangement x=(x1,…,xn) satisfies the condition xij=aj if and only if x′=(xk+1,…,xn) is a permutation of [k]. The number of such permutations x′ is k!. Thus ∑i=0k−1(ik−1)k−iDk+1−i=k!.
Transcribed from the official solutions, pages 4–6. This transcription has not been checked a second time; if in doubt, look at the original.