Σελίδα 1 από 1

IMC 2014/2/5

Δημοσιεύτηκε: Παρ Αύγ 01, 2014 6:16 pm
από Demetres
Για κάθε θετικό ακέραιο n γράφουμε D_n για τον αριθμό των μεταθέσεων (x_1,\ldots,x_n) του (1,2,\ldots,n) με x_j \neq j για κάθε 1 \leqslant j \leqslant n. Για κάθε 1 \leqslant k \leqslant n/2 γράφουμε \Delta(n,k) για τον αριθμό των μεταθέσεων (x_1,\ldots,x_n) του (1,2,\ldots,n) με x_i = k+i για κάθε 1 \leqslant i \leqslant k και x_j \neq j για κάθε 1 \leqslant j \leqslant n. Να δειχθεί ότι

\displaystyle{ \Delta(n,k) = \sum_{i=0}^{k-1} \binom{k-1}{i} \frac{D_{n+1-(k+i)}}{n-(k+i)}}

Re: IMC 2014/2/5

Δημοσιεύτηκε: Παρ Απρ 06, 2018 2:30 am
από Λάμπρος Κατσάπας
Demetres έγραψε:
Παρ Αύγ 01, 2014 6:16 pm
Για κάθε θετικό ακέραιο n γράφουμε D_n για τον αριθμό των μεταθέσεων (x_1,\ldots,x_n) του (1,2,\ldots,n) με x_j \neq j για κάθε 1 \leqslant j \leqslant n. Για κάθε 1 \leqslant k \leqslant n/2 γράφουμε \Delta(n,k) για τον αριθμό των μεταθέσεων (x_1,\ldots,x_n) του (1,2,\ldots,n) με x_i = k+i για κάθε 1 \leqslant i \leqslant k και x_j \neq j για κάθε 1 \leqslant j \leqslant n. Να δειχθεί ότι

\displaystyle{ \Delta(n,k) = \sum_{i=0}^{k-1} \binom{k-1}{i} \frac{D_{n+1-(k+i)}}{n-(k+i)}}
Θα φέρουμε την προς απόδειξη σχέση σε απλούστερη μορφή ώστε να είναι πιο εύκολα ερμηνεύσιμη. Καταρχάς παρακάτω θα θεωρήσω γνωστό ότι το πλήθος

των μεταθέσεων των στοιχείων του συνόλου \left \{ 1,2,...,n \right \} χωρίς σταθερά σημεία (δηλαδή το D_{n}) ικανοποιεί την αναδρομική σχέση

το D_{n}=(n-1)(D_{n-1}+D_{n-2}). (1)
Επίσης, θα συμβολίσω με \mathcal{B} το σύνολο με στοιχεία τις μεταθέσεις χωρίς σταθερά σημεία και με τους περιορισμούς της εκφώνησης. Είναι |\mathcal{B}|=\Delta (n,k).

Από την (1) παίρνουμε \frac{D_{n+1-(k+i)}}{n-(k+i)}=D_{n-(k+i)}+D_{n-1-(k+i)}. Άρα

\Delta (n,k)=\sum_{i=0}^{k-1}\binom{k-1}{i}\left ( D_{n-(k+i)}+D_{n-1-(k+i)} \right ) \vspace{2em}
=\sum_{i=0}^{k-1}\binom{k-1}{i}\left D_{n-(k+i)}+\sum_{i=0}^{k-1}\binom{k-1}{i}\left D_{n-1-(k+i)} \vspace{2em}
=\sum_{i=0}^{k-1}\binom{k-1}{i}\left D_{n-(k+i)}+\sum_{i=1}^{k}\binom{k-1}{i-1}\left D_{n-(k+i)} \vspace{2em}
=D_{n-k}+\sum_{i=1}^{k-1}\left ( \binom{k-1}{i}+\binom{k-1}{i-1} \right )\left D_{n-(k+i)}+D_{n-2k} \vspace{2em}
=D_{n-k}+\sum_{i=1}^{k-1} \binom{k}{i}\left D_{n-(k+i)}+D_{n-2k} \vspace{2em}
=\sum_{i=0}^{k}\left  \binom{k}{i}\left D_{n-(k+i)} (2)
Παρατήρηση

Αν αντί του συνόλου \left \{ 1,2,..,n \right \} είχαμε ένα αυθαίρετο σύνολο αποτελούμενο από τους n , διαφορετικούς μεταξύ τους, φυσικούς j_{1},j_{2},...,j_{n}, με

αντίστοιχες θέσεις l_{1},l_{2},...,l_{n} τότε το πλήθος των μεταθέσεων χωρίς σταθερά σημεία θα ήταν (προφανώς) το ίδιο, δηλαδή D_{n}. Εν ανάγκη

αντιστοιχούμε j_{i},l_{i}\rightarrow i και ξαναπέφτουμε στην προηγούμενη περίπτωση.



Θεωρούμε τώρα μια μετάθεση του \mathcal{B}. Αυτή θα έχει τη μορφή

k+1,k+2,…,2k,i_{1},i_{2},…,i_{n-k}(3).
Το αρχικό κομμάτι k+1,k+2,…,2k είναι ίδιο σε οποιαδήποτε μετάθεση του \mathcal{B}. Σε κάποιες από τις θέσεις i_{1},i_{2},…,i_{n-k} έχουν τοποθετηθεί οι

αριθμοί 1,2,...,k που εκτοπίστηκαν από τους k+1,k+2,…,2k. Στη μετάθεση (3) οι αριθμοί 1,2,...,k είναι τοποθετημένοι εκτός θέσης. Παρ'όλα

αυτά δεν αποκλείεται να υπάρχει σύμπτωση κάποιου από τους 1,2,...,k και του δείκτη του i. Για παράδειγμα, για n=6,k=2 και μετάθεση του \mathcal{B}

την 341562 ο αριθμός 1 έχει καταλάβει τη θέση του i_{1} (σύμπτωση αριθμού και δείκτη).Το πλήθος αυτών των συμπτώσεων κυμαίνεται από 0 (όταν οι

1,2,...,k έχουν τοποθετηθεί σε κάποιες από τις θέσεις i_{k+1},i_{k+2},…,i_{n-k}) μέχρι k (όταν οι 1,2,...,k έχουν τοποθετηθεί στις θέσεις

i_{1},i_{2},…,i_{k} αντίστοιχα). Τα σύνολα \mathcal{R}_{m} με στοιχεία από το \mathcal{B} όπου m ακριβώς από τους 1,2,...,k έχουν αντιστοιχηθεί με το δείκτη του i αποτελούν διαμέριση του

\mathcal{B} δηλαδή \mathcal{B}=\bigcup_{m=0}^{k}\mathcal{R}_{m} και \left | \mathcal{B} \right |=\sum_{m=0}^{k}\left | \mathcal{R}_{m} \right |. Μπορούμε να τοποθετήσουμε m από τους 1,2,...,k, ώστε να αντιστοιχηθούν με το δείκτη του i,

με \binom{k}{m} τρόπους (αρκεί να επιλέξουμε ποιους θα τοποθετήσουμε). Έστω j_{1},j_{2},...,j_{k-m} οι εναπομείναντες από τους 1,2,...,k με αντίστοιχες θέσεις

l_{1},l_{2},...,l_{k-m}. Έχουμε ακόμα τους 2k+1,2k+2,...,n με αντίστοιχες θέσεις αυτές των i_{k+1},i_{k+2},...,i_{n-k}. Τελικά μείναμε με

(n-2k)+(k-m)=n-k-m αριθμούς ο καθένας από τους οποίους έχει διαφορετικό αριθμό θέσης. Από την παρατήρηση τώρα παίρνουμε τελικά

ότι για κάθε έναν από τους \binom{k}{m} τρόπους που τοποθετήσαμε τους m αντιστοιχούν D_{n-k-m} τρόποι για να τοποθετηθούν οι υπόλοιποι. Από την

πολλαπλασιαστική αρχή τώρα παίρνουμε \left | \mathcal{R}_{m} \right |=\binom{k}{m}D_{n-k-m} και \left | \mathcal{B} \right |=\sum_{m=0}^{k}\binom{k}{m}D_{n-k-m} δηλαδή τη (2) που θέλαμε να δείξουμε.