Demetres έγραψε: ↑Παρ Αύγ 01, 2014 6:16 pm
Για κάθε θετικό ακέραιο
γράφουμε
για τον αριθμό των μεταθέσεων
του
με
για κάθε
. Για κάθε
γράφουμε
για τον αριθμό των μεταθέσεων
του
με
για κάθε
και
για κάθε
. Να δειχθεί ότι
Θα φέρουμε την προς απόδειξη σχέση σε απλούστερη μορφή ώστε να είναι πιο εύκολα ερμηνεύσιμη. Καταρχάς παρακάτω θα θεωρήσω γνωστό ότι το πλήθος
των μεταθέσεων των στοιχείων του συνόλου
χωρίς σταθερά σημεία (δηλαδή το
) ικανοποιεί την αναδρομική σχέση
Επίσης, θα συμβολίσω με
το σύνολο με στοιχεία τις μεταθέσεις χωρίς σταθερά σημεία και με τους περιορισμούς της εκφώνησης. Είναι
Από την
παίρνουμε
Άρα
Παρατήρηση
Αν αντί του συνόλου είχαμε ένα αυθαίρετο σύνολο αποτελούμενο από τους , διαφορετικούς μεταξύ τους, φυσικούς με
αντίστοιχες θέσεις τότε το πλήθος των μεταθέσεων χωρίς σταθερά σημεία θα ήταν (προφανώς) το ίδιο, δηλαδή . Εν ανάγκη
αντιστοιχούμε και ξαναπέφτουμε στην προηγούμενη περίπτωση.
Θεωρούμε τώρα μια μετάθεση του
. Αυτή θα έχει τη μορφή
.
Το αρχικό κομμάτι
είναι ίδιο σε οποιαδήποτε μετάθεση του
. Σε κάποιες από τις θέσεις
έχουν τοποθετηθεί οι
αριθμοί
που εκτοπίστηκαν από τους
. Στη μετάθεση
οι αριθμοί
είναι τοποθετημένοι εκτός θέσης. Παρ'όλα
αυτά δεν αποκλείεται να υπάρχει σύμπτωση κάποιου από τους
και του δείκτη του
. Για παράδειγμα, για
και μετάθεση του
την
ο αριθμός
έχει καταλάβει τη θέση του
(σύμπτωση αριθμού και δείκτη).Το πλήθος αυτών των συμπτώσεων κυμαίνεται από
(όταν οι
έχουν τοποθετηθεί σε κάποιες από τις θέσεις
) μέχρι
(όταν οι
έχουν τοποθετηθεί στις θέσεις
αντίστοιχα). Τα σύνολα
με στοιχεία από το
όπου
ακριβώς από τους
έχουν αντιστοιχηθεί με το δείκτη του
αποτελούν διαμέριση του
δηλαδή
και
Μπορούμε να τοποθετήσουμε
από τους
, ώστε να αντιστοιχηθούν με το δείκτη του
,
με
τρόπους (αρκεί να επιλέξουμε ποιους θα τοποθετήσουμε). Έστω
οι εναπομείναντες από τους
με αντίστοιχες θέσεις
. Έχουμε ακόμα τους
με αντίστοιχες θέσεις αυτές των
Τελικά μείναμε με
αριθμούς ο καθένας από τους οποίους έχει διαφορετικό αριθμό θέσης. Από την παρατήρηση τώρα παίρνουμε τελικά
ότι για κάθε έναν από τους
τρόπους που τοποθετήσαμε τους
αντιστοιχούν
τρόποι για να τοποθετηθούν οι υπόλοιποι. Από την
πολλαπλασιαστική αρχή τώρα παίρνουμε
και
δηλαδή τη
που θέλαμε να δείξουμε.