Vojtech Jarvik 2013/4 Category I

Συντονιστής: Demetres

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8113
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Vojtech Jarvik 2013/4 Category I

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Φεβ 15, 2016 12:32 pm

Έστω θετικοί ακέραιοι n,k. Να υπολογιστεί το άθροισμα

\displaystyle{ \sum_{j=0}^k \binom{k}{j}^2\binom{n+2k-j}{2k}. }


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8113
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Vojtech Jarvik 2013/4 Category I

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Φεβ 17, 2016 3:29 pm

Δίνω μια διαφορετική λύση από την επίσημη.

Δοκιμάζοντας μικρά n δεν αργούμε να μαντέψουμε ότι το άθροισμα «πρέπει να» ισούται με \displaystyle{ \binom{n+k}{k}.}

Θα δείξω πιο γενικά ότι
\displaystyle{ \sum_{j=0}^k \binom{k}{j}^2 \binom{m+k-j}{2k} = \binom{m}{k}^2. }

Το αποτέλεσμα έπεται θέτοντας m=n+k.

Ξεκινώ με δύο ξένα μεταξύ τους σύνολα A,B με m και k στοιχεία αντίστοιχα. Παίρνω ένα υποσύνολο C μεγέθους k από το A. Ακολούθως παίρνω ένα υποσύνολο D μεγέθους k από το (A \cup B) \setminus C.

Επειδή |(A \cup B) \setminus C| = m έχω συνολικά \displaystyle{\binom{m}{k}^2} τρόπους να κάνω το πιο πάνω. Το τελικό αποτέλεσμα είναι ένα υποσύνολο E = C \cup D του A \cup B μεγέθους 2k. Μόνο που κάθε τέτοιο σύνολο E μπορεί να προκύψει με πολλούς τρόπους. Πιο συγκεκριμένα αν |A \cap E| = k+r τότε το E μπορεί να προκύψει με ακριβώς \displaystyle{ \binom{k+r}{k}} τρόπους. [Ακριβώς έναν τρόπο για κάθε υποσύνολο του A \cap E μεγέθους k.]

Τώρα θα επιλέξω πάλι ένα σύνολο E του A \cup B αλλά διαφορετικά.

Πρώτα επιλέγω ένα j με 0 \leqslant j \leqslant k.
Μετά επιλέγω ένα υποσύνολο J του B με j στοιχεία.
Μετά επιλέγω ένα υποσύνολο E του (A\cup B)\setminus J μεγέθους 2k.
Επαναλαμβάνω το ίδιο \displaystyle{ \binom{r}{j}} φορές.

Συνολικά το πιο πάνω μπορώ να το κάνω με
\displaystyle{ \sum_{j=0}^k \binom{k}{j}^2 \binom{m+k-j}{2k}. }
τρόπους.

Πάλι το τελικό αποτέλεσμα είναι η επιλογή ενός υποσυνόλου E του A \cup B μόνο που κάθε E μπορεί να προκύψει με αρκετούς τρόπους. Πιο συγκεκριμένα αν |A \cap E| = k+r τότε το E μπορεί να προκύψει με
\displaystyle{ \sum_{j=0}^k \binom{r}{j} \binom{k}{j}}
τρόπους. Το άθροισμα από j=0 έως k υπάρχει διότι κάνω πρώτα την επιλογή του j. Το \displaystyle{ \binom{k}{j}} υπάρχει διότι το J πρέπει να είναι υποσύνολο του B \setminus E το οποίο έχει k στοιχεία. Τέλος το \displaystyle{ \binom{r}{j}} υπάρχει διότι επαναλαμβάνω την διαδικασία τόσες φορές.

Όμως
\displaystyle{ \sum_{j=0}^k \binom{r}{j} \binom{k}{j} =  \sum_{j=0}^k \binom{r}{j} \binom{k}{k-j} = \binom{k+r}{k}}

Οπότε είτε την πρώτη διαδικασία κάνω είτε την δεύτερη κάθε σύνολο E θα το πάρω τις ίδιες φορές. Οπότε ο αριθμός των διαφορετικών τρόπων που μπορώ να κάνω τν πρώτη διαδικασία ισούται με τον αριθμό των τρόπων που μπορώ να κάνω την δεύτερη. Το ζητούμενο έπεται.


Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες