Άθροισμα γινομένων διωνυμικών

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

Μου προέκυψε από κατασκευή μοντέλου δειγματοληψίας. Ενδεχομένως να έχει ξανατεθεί εδώ στο

.

Να δείξετε ότι $\displaystyle \sum_{r=k}^{k+b}\binom{r}{k}\binom{n-r}{b-r+k}=\binom{n+1}{b}.$

#2

Για να έχει νόημα το αριστερά μέλος πρέπει $k \geqslant 0$ (αλλιώς για r = k

το $\binom{r}{k}$ δεν έχει νόημα) και $k \leqslant n-b$ (αλλιώς για r=k+b

το $\binom{n-r}{b-r+k}$ δεν έχει νόημα).

Θα δούμε με πόσους τρόπους μπορούμε να επιλέξουμε n+1-b

στοιχεία από το σύνολο $\{1,2,\ldots,n+1\}$ ώστε το (k+1)

-οστό στοιχείο να είναι το r+1

.

Από τα πρώτα

στοιχεία πρέπει να επιλέξουμε τα

και από τα τελευταία n-r

πρέπει να επιλέξουμε τα (n+1-b)-(k+1) = n-b-k

. Επομένως υπάρχουν $\displaystyle \binom{r}{k}\binom{n-r}{n-b-k} = \binom{r}{k}\binom{n-r}{b+k-r}$

Ας παρατηρήσουμε ότι $k \in \{0,1,\ldots,n-b\}$ και $r \in \{k,k+1,\ldots,k+b\}$ . Το μόνο που δεν είναι προφανές είναι ότι $r \leqslant k+b$ . Για να το δούμε παρατηρούμε ότι πρέπει στα τελευταία n-r

στοιχεία να επιλέξουμε n-b-k

επομένως θέλουμε $r \leqslant b+k$ .

Προσθέτουμε τώρα από r=k

ως

για να πάρουμε

$\displaystyle \sum_{r=k}^{b+k} \binom{r}{k}\binom{n-r}{b+k-r} = \binom{n+1}{n+1-b} = \binom{n+1}{b}$

όπως θέλαμε.

miltosk · #3

Λάμπρος Κατσάπας έγραψε: Δευ Απρ 13, 2020 1:17 am Μου προέκυψε από κατασκευή μοντέλου δειγματοληψίας. Ενδεχομένως να έχει ξανατεθεί εδώ στο .

Να δείξετε ότι $\displaystyle \sum_{r=k}^{k+b}\binom{r}{k}\binom{n-r}{b-r+k}=\binom{n+1}{b}.$

Έχοντας δει παρόμοια σε γενήτριες συναρτήσεις (άσκηση στο κεφάλαιο δηλαδή), μπορεί αυτό να δειχθεί με τη χρήση γενήτριας συνάρτησης;

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

miltosk έγραψε: Δευ Απρ 13, 2020 4:15 pm
Λάμπρος Κατσάπας έγραψε: Δευ Απρ 13, 2020 1:17 am Μου προέκυψε από κατασκευή μοντέλου δειγματοληψίας. Ενδεχομένως να έχει ξανατεθεί εδώ στο .

Να δείξετε ότι $\displaystyle \sum_{r=k}^{k+b}\binom{r}{k}\binom{n-r}{b-r+k}=\binom{n+1}{b}.$
Έχοντας δει παρόμοια σε γενήτριες συναρτήσεις (άσκηση στο κεφάλαιο δηλαδή), μπορεί αυτό να δειχθεί με τη χρήση γενήτριας συνάρτησης;

Γεια!

Υπόδειξη:
1) Για a>0

είναι $\displaystyle \binom{-a}{m}=(-1)^m\binom{a+m-1}{m}.$

2) Διακριτή συνέλιξη - Cauchy product.

3) $\displaystyle(1+x)^{-a}(1+x)^{-b}=(1+x)^{-(a+b)}.$

4) Άλλαξε τη σειρά άθροισης να ξεκινά από το

* Είναι ''γεννήτρια''.

miltosk · #5

Λάμπρος Κατσάπας έγραψε: Δευ Απρ 13, 2020 6:44 pm
miltosk έγραψε: Δευ Απρ 13, 2020 4:15 pm
Λάμπρος Κατσάπας έγραψε: Δευ Απρ 13, 2020 1:17 am Μου προέκυψε από κατασκευή μοντέλου δειγματοληψίας. Ενδεχομένως να έχει ξανατεθεί εδώ στο .

Να δείξετε ότι $\displaystyle \sum_{r=k}^{k+b}\binom{r}{k}\binom{n-r}{b-r+k}=\binom{n+1}{b}.$
Έχοντας δει παρόμοια σε γενήτριες συναρτήσεις (άσκηση στο κεφάλαιο δηλαδή), μπορεί αυτό να δειχθεί με τη χρήση γενήτριας συνάρτησης;
Γεια!

Υπόδειξη:
1) Για είναι $\displaystyle \binom{-a}{m}=(-1)^m\binom{a+m-1}{m}.$

2) Διακριτή συνέλιξη - Cauchy product.

3) $\displaystyle(1+x)^{-a}(1+x)^{-b}=(1+x)^{-(a+b)}.$

4) Άλλαξε τη σειρά άθροισης να ξεκινά από το

* Είναι ''γεννήτρια''.

Ας μείνω στη συνδυαστική προσέγγιση γ λυκείου είμαι αλλά ευχαριστώ για το ενδιαφέρον.

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

Ας μείνω στη συνδυαστική προσέγγιση γ λυκείου είμαι αλλά ευχαριστώ για το ενδιαφέρον.

Νόμιζα ότι μιλούσα με φοιτητή. Θα σου γράψω μια λύση βασισμένη στην υπόδειξη το συντομότερο δυνατό. Δεν έχω internet και αναγκάζομαι να γράφω από κινητό.

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

Αλλάζοντας τα όρια του αθροίσματος ώστε να ξεκινά η άθροιση από το

βρίσκουμε ότι το άθροισμά μας γράφεται

$\displaystyle \sum_{j=0}^{b}\binom{k+j}{j}\binom{n-k-j}{b-j}.$
Ισχύει $(1-x)^{-(k+1)}(1-x)^{-(n-b-k+1)} =(1-x)^{-(n-b+2)} .$

Όμως

$\displaystyle(1-x)^{-(k+1)}(1-x)^{-(n-b-k+1)}$

$\displaystyle=\left [\sum_{j=0}^{\infty }(-1)^j\binom{-(k+1)}{j}x^j \right ] \cdot \left [\sum_{l=0}^{\infty }(-1)^l\binom{-(n-b-k+1)}{l}x^l \right ]$

$\displaystyle = \sum_{j=0}^{\infty }\sum_{l=0}^{\infty } \binom{k+j}{j}\binom{n-b-k+l}{l}x^j x^l$

$\displaystyle=\sum_{m=0}^{\infty }\left (\sum_{w=0}^{m }\binom{k+w}{w}\binom{n-b-k+m-w}{m-w} \right )x^m$

όπου για m=b

γίνεται

$\displaystyle\sum_{b=0}^{\infty }\left (\sum_{w=0}^{b }\binom{k+w}{w}\binom{n-k-w}{b-w} \right )x^b .$

Aπό την άλλη

$\displaystyle (1-x)^{-(n-b+2)}=\sum_{b=0}^{\infty }(-1)^b\binom{-(n-b+2)}{b}x^b$

$\displaystyle =\sum_{b=0}^{\infty }\binom{n-b+2+b-1}{b}x^b$

$\displaystyle \sum_{b=0}^{\infty }\binom{n+1}{b}x^b.$

Εξισώνοντας τους συντελεστές παίρνουμε το ζητούμενο.

Άθροισμα γινομένων διωνυμικών

Άθροισμα γινομένων διωνυμικών

Re: Άθροισμα γινομένων διωνυμικών

Re: Άθροισμα γινομένων διωνυμικών

Re: Άθροισμα γινομένων διωνυμικών

Re: Άθροισμα γινομένων διωνυμικών

Re: Άθροισμα γινομένων διωνυμικών

Re: Άθροισμα γινομένων διωνυμικών

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