uniolympiads English

IMC 2014, Ημέρα 2, Θέμα 5

For every positive integer nn, denote by DnD_n the number of permutations (x1,…,xn)(x_1, \dots, x_n) of (1,2,…,n)(1, 2, \dots, n) such that xj≠jx_j \ne j for every 1≤j≤n1 \le j \le n. For 1≤k≤n21 \le k \le \frac{n}{2}, denote by Δ(n,k)\Delta(n, k) the number of permutations (x1,…,xn)(x_1, \dots, x_n) of (1,2,…,n)(1, 2, \dots, n) such that xi=k+ix_i = k + i for every 1≤i≤k1 \le i \le k and xj≠jx_j \ne j for every 1≤j≤n1 \le j \le n. Prove that

Δ(n,k)=∑i=0k−1(k−1i)D(n+1)−(k+i)n−(k+i).\Delta(n, k) = \sum_{i=0}^{k-1} \binom{k-1}{i} \frac{D_{(n+1)-(k+i)}}{n - (k+i)}.
Πρωτότυπο από το επίσημο PDFFor every positive integer n , denote by D n the number of permutations (x 1 , . . . , x n ) of (1, 2, . . . , n) su h that x j 6 = j for every 1 ≤ j ≤ n . For 1 ≤ k ≤ n 2 , denote by ∆(n, k) the number of permutations (x 1 , . . . , x n ) of (1, 2, . . . , n) su h that x i = k + i for every 1 ≤ i ≤ k and x j 6 = j for every 1 ≤ j ≤ n . Prove that Problem 5. ∆(n, k) = k−1 X k − 1 D (n+1)−(k+i) i=0 i n − (k + i) .

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(Proposed by Combinatorics; Ferdowsi University of Mashhad, Iran; Mirzavaziri)

Solution. Let ar∈{i1,…,ik}∩{a1,…,ak}a_r \in \{i_1,\ldots,i_k\}\cap\{a_1,\ldots,a_k\}. Thus ar=isa_r = i_s for some s≠rs \ne r. Now there are two cases:

Case 1. as∈{i1,…,ik}a_s \in \{i_1,\ldots,i_k\}. Let as=ita_s = i_t. In this case a derangement x=(x1,…,xn)x = (x_1,\ldots,x_n) satisfies the condition xij=ajx_{i_j} = a_j if and only if the derangement x′=(x1′,…,xit−1′,xit+1′,xn′)x' = (x'_1,\ldots,x'_{i_t-1},x'_{i_t+1},x'_n) of the set [n]∖{it}[n]\setminus\{i_t\} satisfies the condition xij′=aj′x'_{i_j} = a'_j for all j≠tj \ne t, where aj′=aja'_j = a_j for j≠sj \ne s and as′=ata'_s = a_t. This provides a one to one correspondence between the derangements x=(x1,…,xn)x = (x_1,\ldots,x_n) of [n][n] with xij=ajx_{i_j} = a_j for the given sets {i1,…,ik}\{i_1,\ldots,i_k\} and {a1,…,ak}\{a_1,\ldots,a_k\} with ℓ\ell elements in their intersections, and the derangements x′=(x1′,…,xit−1′,xit+1′,xn′)x' = (x'_1,\ldots,x'_{i_t-1},x'_{i_t+1},x'_n) of [n]∖{it}[n]\setminus\{i_t\} with xij=aj′x_{i_j} = a'_j for the given sets {i1,…,ik}∖{it}\{i_1,\ldots,i_k\}\setminus\{i_t\} and {a1′,…,ak′}∖{at′}\{a'_1,\ldots,a'_k\}\setminus\{a'_t\} with ℓ−1\ell-1 elements in their intersections.

Case 2. as∉{i1,…,ik}a_s \notin \{i_1,\ldots,i_k\}. In this case a derangement x=(x1,…,xn)x = (x_1,\ldots,x_n) satisfies the condition xij=ajx_{i_j} = a_j if and only if the derangement x′=(x1′,…,xas−1′,xas+1′,xn′)x' = (x'_1,\ldots,x'_{a_s-1},x'_{a_s+1},x'_n) of the set [n]∖{as}[n]\setminus\{a_s\} satisfies the condition xij′=ajx'_{i_j} = a_j for all j≠sj \ne s. This provides a one to one correspondence between the derangements x=(x1,…,xn)x = (x_1,\ldots,x_n) of [n][n] with xij=ajx_{i_j} = a_j for the given sets {i1,…,ik}\{i_1,\ldots,i_k\} and {a1,…,ak}\{a_1,\ldots,a_k\} with ℓ\ell elements in their intersections, and the derangements x′=(x1′,…,xas−1′,xas+1′,xn′)x' = (x'_1,\ldots,x'_{a_s-1},x'_{a_s+1},x'_n) of [n]∖{as}[n]\setminus\{a_s\} with xij=ajx_{i_j} = a_j for the given sets {i1,…,ik}∖{is}\{i_1,\ldots,i_k\}\setminus\{i_s\} and {a1,…,ak}∖{as}\{a_1,\ldots,a_k\}\setminus\{a_s\} with ℓ−1\ell-1 elements in their intersections.

These considerations show that Δ(n,k,ℓ)=Δ(n−1,k−1,ℓ−1)\Delta(n,k,\ell) = \Delta(n-1,k-1,\ell-1). Iterating this argument we have

Δ(n,k,ℓ)=Δ(n−ℓ,k−ℓ,0).\Delta(n,k,\ell) = \Delta(n-\ell,k-\ell,0).
We can therefore assume that ℓ=0\ell = 0. We thus evaluate Δ(n,k,0)\Delta(n,k,0), where 2k⩽n2k \leqslant n. For k=0k = 0, we obviously have Δ(n,0,0)=Dn\Delta(n,0,0) = D_n. For k⩾1k \geqslant 1, we claim that
Δ(n,k,0)=Δ(n−1,k−1,0)+Δ(n−2,k−1,0).\Delta(n,k,0) = \Delta(n-1,k-1,0) + \Delta(n-2,k-1,0).
For a derangement x=(x1,…,xn)x = (x_1,\ldots,x_n) satisfying xij=ajx_{i_j} = a_j there are two cases: xa1=i1x_{a_1} = i_1 or xa1≠i1x_{a_1} \ne i_1.

If the first case occurs then we have to evaluate the number of derangements of the set [n]∖{i1,a1}[n]\setminus\{i_1,a_1\} for the given sets {i2,…,ik}\{i_2,\ldots,i_k\} and {a2,…,ak}\{a_2,\ldots,a_k\} with 00 elements in their intersections. The number is equal to Δ(n−2,k−1,0)\Delta(n-2,k-1,0).

If the second case occurs then we have to evaluate the number of derangements of the set [n]∖{a1}[n]\setminus\{a_1\} for the given sets {i2,…,ik}\{i_2,\ldots,i_k\} and {a2,…,ak}\{a_2,\ldots,a_k\} with 00 elements in their intersections. The number is equal to Δ(n−1,k−1,0)\Delta(n-1,k-1,0).

We now use induction on kk to show that

Δ(n,k,0)=∑i=0k−1(k−1i)D(n+1)−(k+i)n−(k+i),2⩽2k⩽n.\Delta(n,k,0) = \sum_{i=0}^{k-1}\binom{k-1}{i}\frac{D_{(n+1)-(k+i)}}{n-(k+i)}, \quad 2 \leqslant 2k \leqslant n.
For k=1k = 1 we have
Δ(n,1,0)=Δ(n−1,0,0)+Δ(n−2,0,0)=Dn−1+Dn−2=Dnn−1.\Delta(n,1,0) = \Delta(n-1,0,0) + \Delta(n-2,0,0) = D_{n-1} + D_{n-2} = \frac{D_n}{n-1}.
Now let the result be true for k−1k-1. We can write
Δ(n,k,0)=Δ(n−1,k−1,0)+Δ(n−2,k−1,0)=∑i=0k−2(k−2i)Dn−(k−1+i)(n−1)−(k−1+i)+∑i=0k−2(k−2i)D(n−1)−(k−1+i)(n−2)−(k−1+i)=∑i=0k−2(k−2i)D(n+1)−(k+i)n−(k+i)+∑i=1k−1(k−2i−1)Dn−(k+i−1)(n−1)−(k+i−1)=D(n+1)−kn−k+∑i=1k−2(k−2i)D(n+1)−(k+i)n−(k+i)+D(n+1)−(2k−1)n−(2k−1)+∑i=1k−2(k−2i−1)D(n+1)−(k+i)n−(k+i)=D(n+1)−kn−k+∑i=1k−2[(k−2i)+(k−2i−1)]D(n+1)−(k+i)n−(k+i)+D(n+1)−(2k−1)n−(2k−1)=D(n+1)−kn−k+∑i=1k−2(k−1i)D(n+1)−(k+i)n−(k+i)+D(n+1)−(2k−1)n−(2k−1)=∑i=0k−1(k−1i)D(n+1)−(k+i)n−(k+i).\begin{aligned} \Delta(n,k,0) &= \Delta(n-1,k-1,0) + \Delta(n-2,k-1,0) \\ &= \sum_{i=0}^{k-2}\binom{k-2}{i}\frac{D_{n-(k-1+i)}}{(n-1)-(k-1+i)} + \sum_{i=0}^{k-2}\binom{k-2}{i}\frac{D_{(n-1)-(k-1+i)}}{(n-2)-(k-1+i)} \\ &= \sum_{i=0}^{k-2}\binom{k-2}{i}\frac{D_{(n+1)-(k+i)}}{n-(k+i)} + \sum_{i=1}^{k-1}\binom{k-2}{i-1}\frac{D_{n-(k+i-1)}}{(n-1)-(k+i-1)} \\ &= \frac{D_{(n+1)-k}}{n-k} + \sum_{i=1}^{k-2}\binom{k-2}{i}\frac{D_{(n+1)-(k+i)}}{n-(k+i)} \\ &\quad + \frac{D_{(n+1)-(2k-1)}}{n-(2k-1)} + \sum_{i=1}^{k-2}\binom{k-2}{i-1}\frac{D_{(n+1)-(k+i)}}{n-(k+i)} \\ &= \frac{D_{(n+1)-k}}{n-k} + \sum_{i=1}^{k-2}\big[\binom{k-2}{i} + \binom{k-2}{i-1}\big]\frac{D_{(n+1)-(k+i)}}{n-(k+i)} + \frac{D_{(n+1)-(2k-1)}}{n-(2k-1)} \\ &= \frac{D_{(n+1)-k}}{n-k} + \sum_{i=1}^{k-2}\binom{k-1}{i}\frac{D_{(n+1)-(k+i)}}{n-(k+i)} + \frac{D_{(n+1)-(2k-1)}}{n-(2k-1)} \\ &= \sum_{i=0}^{k-1}\binom{k-1}{i}\frac{D_{(n+1)-(k+i)}}{n-(k+i)}. \end{aligned}

Remark. As a corollary of the above problem, we can solve the first problem. Let n=2kn = 2k, ij=ji_j = j and aj=k+ja_j = k+j for j=1,…,kj = 1,\ldots,k. Then a derangement x=(x1,…,xn)x = (x_1,\ldots,x_n) satisfies the condition xij=ajx_{i_j} = a_j if and only if x′=(xk+1,…,xn)x' = (x_{k+1},\ldots,x_n) is a permutation of [k][k]. The number of such permutations x′x' is k!k!. Thus ∑i=0k−1(k−1i)Dk+1−ik−i=k!\sum_{i=0}^{k-1}\binom{k-1}{i}\frac{D_{k+1-i}}{k-i} = k!.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 4–6. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;