Έστω m, n θετικοί ακέραιοι (φυσικοί) αριθμοί. Θεωρούμε την συμμετρική ποσότητα
Q(m,n) = Q(n,m) = (m+n)! / m! n!
Θέλουμε να δείξουμε ότι το Q είναι ακέραιος, για κάθε m και n.
Ένας τρόπος να δουλέψουμε είναι να παρατηρήσουμε ότι
Q(m,n) = (m+1)(m+2)...(m+n) / n!
και να δείξουμε ότι ο αριθμητής είναι ακέραιο πολλαπλάσιο του παρονομαστή. Θα πρέπει, λ.χ., να αναπτύξουμε αριθμητή και παρονομαστή σε γινόμενα δυνάμεων πρώτων αριθμών και να δείξουμε ότι οι δυνάμεις στον παρονομαστή δεν υπερβαίνουν τις αντίστοιχες στον αριθμητή. Η απόδειξη με αυτό τον τρόπο θα οδηγούσε, ίσως, σε μαθηματικό βραβείο!
Ένας διαφορετικός τρόπος είναι να αποδείξουμε ότι το Q(m,n) είναι πληθικός αριθμός (cardinal number) κάποιου συνόλου, ίσος εξ ορισμού με το πλήθος των στοιχείων του συνόλου. Ο αριθμός αυτός είναι, φυσικά, ακέραιος.
Θεωρούμε το σύνολο των διατεταγμένων n-άδων
S(n, m+n) = { (α1, α2, ... , αn) }
όπου τα α1, α2, ... , αn παίρνουν όλες τις δυνατές τιμές από το σύνολο {1,2,...,m+n}, που ικανοποιούν την ανισότητα α1 < α2 < ... < αn . Όπως λένε οι φωστήρες της συνδυαστικής ανάλυσης, ο πληθικός αριθμός τού πιο πάνω συνόλου ισούται με
| S(n, m+n) | = Q(m,n)
Εναλλακτικά, δοθέντος ότι το Q(m,n) είναι συμμετρικό ως προς τα m και n, μπορούμε να θεωρήσουμε το σύνολο των διατεταγμένων m-άδων
S(m, m+n) = { (α1, α2, ... , αm) }
όπου τα α1, α2, ... , αm παίρνουν όλες τις δυνατές τιμές από το σύνολο {1,2,...,m+n}, που ικανοποιούν την ανισότητα α1 < α2 < ... < αm . Τότε, και πάλι,
| S(m, m+n) | = Q(m,n)
Παράδειγμα: Για m=2 και n=3 έχουμε ότι
Q(2,3) = 5! / 2! 3! = 10 . Από την άλλη, το σύνολο
S(3,5) = { (1,2,3), (1,2,4), (1,2,5), (1,3,4), (1,3,5), (1,4,5),
(2,3,4), (2,3,5), (2,4,5), (3,4,5) }
έχει πληθικό αριθμό | S(3,5) |=10 . Ισοδύναμα, για το σύνολο
S(2,5) = { (1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5),
(3,4), (3,5), (4,5) }
έχουμε και πάλι ότι | S(2,5) |=10 .
Συμπέρασμα: Ο αριθμός Q = (m+n)! / m! n! είναι ακέραιος και ίσος με
Q(m,n) = | S(m, m+n) | = | S(n, m+n) |
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου