IMC 2014/2/5

#1

Για κάθε θετικό ακέραιο

γράφουμε

για τον αριθμό των μεταθέσεων $(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)}}$

Λάμπρος Κατσάπας · #2

Demetres έγραψε: Παρ Αύγ 01, 2014 6:16 pm Για κάθε θετικό ακέραιο γράφουμε για τον αριθμό των μεταθέσεων $(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)$ με για κάθε $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 \}$ είχαμε ένα αυθαίρετο σύνολο αποτελούμενο από τους , διαφορετικούς μεταξύ τους, φυσικούς $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)$ .
Το αρχικό κομμάτι

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

αριθμοί 1,2,...,k

που εκτοπίστηκαν από τους k+1,k+2,…,2k

. Στη μετάθεση (3)

οι αριθμοί 1,2,...,k

είναι τοποθετημένοι εκτός θέσης. Παρ'όλα

αυτά δεν αποκλείεται να υπάρχει σύμπτωση κάποιου από τους 1,2,...,k

και του δείκτη του

. Για παράδειγμα, για n=6,k=2

και μετάθεση του $\mathcal{B}$

την 341562

ο αριθμός

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

(όταν οι

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

(όταν οι

έχουν τοποθετηθεί στις θέσεις

$i_{1},i_{2},…,i_{k}$ αντίστοιχα). Τα σύνολα $\mathcal{R}_{m}$ με στοιχεία από το $\mathcal{B}$ όπου

ακριβώς από τους 1,2,...,k

έχουν αντιστοιχηθεί με το δείκτη του

αποτελούν διαμέριση του

$\mathcal{B}$ δηλαδή $\mathcal{B}=\bigcup_{m=0}^{k}\mathcal{R}_{m}$ και $\left | \mathcal{B} \right |=\sum_{m=0}^{k}\left | \mathcal{R}_{m} \right |.$ Μπορούμε να τοποθετήσουμε

από τους

, ώστε να αντιστοιχηθούν με το δείκτη του

,

με $\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}$ τρόπους που τοποθετήσαμε τους

αντιστοιχούν $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)

που θέλαμε να δείξουμε.

IMC 2014/2/5

IMC 2014/2/5

Re: IMC 2014/2/5

Μέλη σε σύνδεση