Współczynniki dwumianowe

[Martino19]

Nie mam pojęcia jak podejść do zadania:
Udowodnij algebraicznie(rachunkowo) oraz kombinatorycznie, że \(\displaystyle{ \sum_{i=0}^{n-k} {n \choose i} {n-i \choose k} = 2 ^{n-k} {n \choose k} .}\)

[Premislav]

Dowód algebraiczny:
nietrudno obliczyć, że
\(\displaystyle{ {n \choose i}{n-i \choose k}= \frac{n!}{i!k!(n-i-k)!}= {n \choose k} \cdot \frac{(n-k)!}{i!(n-i-k)!} =\\={n \choose k}\cdot {n-k \choose i}}\)
a zatem
\(\displaystyle{ \sum_{i=0}^{n-k} {n \choose i} {n-i \choose k} ={n \choose k} \sum_{i=0}^{n-k}{n-k \choose i}={n \choose k}2^{n-k}}\)

[Martino19]

Dzięki Premislav, a kombinatorycznie jakbym mógł do tego podejść ?

[Premislav]

No cóż, nie jestem specjalistą od dowodów kombinatorycznych, że tak sobie pozwolę na zgrabny eufemizm. Ale spróbujmy.
Mamy zbiór n-elementowy. Chcemy w nim wyróżnić dokładnie \(\displaystyle{ k}\) elementów, a pozostałe \(\displaystyle{ n-k}\) podzielić na dwie kategorie (np. prima sort i prima aprilis). Możemy więc postąpić tak:
na \(\displaystyle{ {n \choose k}}\) sposobów wybieramy \(\displaystyle{ k}\) spośród \(\displaystyle{ n}\) elementów, które wyróżnimy. Dla każdego z pozostałych \(\displaystyle{ n-k}\) mamy dwa wybory: albo trafi do pierwszej kategorii, albo do drugiej, czyli tych \(\displaystyle{ n-k}\) elementów możemy podzielić na dwie kategorie na \(\displaystyle{ 2^{n-k}}\) sposobów. Co łącznie daje nam \(\displaystyle{ 2^{n-k}{n \choose k}}\) sposobów przeprowadzenia naszej czynności (prawa strona).

Z drugiej strony można na to spojrzeć inaczej: najpierw wybieramy \(\displaystyle{ i}\) elementów \(\displaystyle{ 0\le i\le n-k}\), by pozostałych było co najmniej \(\displaystyle{ k}\)), którym przypiszemy pierwszą kategorię, a spośród pozostałych \(\displaystyle{ n-i}\) elementów zbioru \(\displaystyle{ n}\)-elementowego dokładnie \(\displaystyle{ k}\) wyróżniamy (wyróżnione wybieramy na \(\displaystyle{ {n-i \choose k}}\) sposobów), a pozostałym automatycznie przypisujemy drugą kategorię (lewa strona).

[tomwanderer]

a kombinatorycznie jakbym mógł do tego podejść ?

To może ja dodam coś od siebie:

Umawiasz się ze swoim najlepszym kumplem na degustację piwa. Ponieważ jest to Twój najlepszy kumpel, on za wszystko płaci. Chcecie spróbować jak najwięcej różnych piw, więc Twój kumpel kupuje tylko po jednej butelce danego rodzaju. W dodatku postanowił zrobić Ci niespodziankę i dopiero jak do niego przyjdziesz do jego pokoju w akademiku, to się dowiesz, jakie kupił piwa oraz ile.

Przychodzisz do kumpla, piwa leżą już schłodzone w lodówce. Zaglądasz do lodówki i mówisz?
\(\displaystyle{ -}\) Co?! Kupiłeś aż \(\displaystyle{ n}\) piw? Wszystkich dziś nie wypijemy, za dużo. Proponuję, abyśmy dzisiaj wypili dokładnie \(\displaystyle{ k}\) piw, a resztę ewentualnie jutro, a ile jutro wypijemy to się jeszcze zobaczy, bo jak będę miał mocnego kaca to jutro za dużo nie wypiję i może się okazać, że nawet w te 2 dni nie uda się wypić tych \(\displaystyle{ n}\) piw...

Kumpel po chwili namysłu przyznaje Ci rację - dziś degustujecie \(\displaystyle{ k}\) butelek piw, a jutro pewną ilość od \(\displaystyle{ 0}\) do \(\displaystyle{ n-k}\).
Pytanie: Na ile sposobów możecie wybrać piwa do degustacji na najbliższe dwa dni?

Odpowiedź nr 1 (prawa strona równości):
Na dzisiaj macie \(\displaystyle{ {n \choose k}}\) wyborów - to jest jasne. Pozostaje wybrać pewną ilość piw spośród \(\displaystyle{ n-k}\) piw, które zostaną na następny dzień. Ale ile konkretnie - nie wiadomo, tzn. macie pełną dowolność. A to możecie zrobić na \(\displaystyle{ 2^{n-k}}\) sposobów - każdy wybór można utożsamić z ciągiem zer i jedynek długości \(\displaystyle{ n-k}\), gdzie np. jeżeli \(\displaystyle{ n-k}\) jest równe 5, to ciąg \(\displaystyle{ 01101}\) oznacza wybór trzech piw - drugiego, trzeciego i piątego, zgodnie z kolejnością w jakiej będą leżały na półce w lodówce po pierwszym dniu degustacji No a takich ciągów jest właśnie \(\displaystyle{ 2^{n-k}}\).

Odpowiedź nr 2 (lewa strona równości):
Zauważasz (słusznie zresztą), że zostawianie piw w lodówce na następny dzień może nie skończyć się za dobrze. Po co kusić współlokatorów z pokoju? Lepiej schować te piwa choćby pod poduszkę, prawda? No ale ile ich schować?
Idziecie więc do jasnowidza, który jest w stanie przewidzieć, w jakim stanie będziecie następnego dnia, a co za tym idzie, ile piw zdołacie wypić. On wam powie, że zdołacie wypić \(\displaystyle{ i}\) piw, gdzie \(\displaystyle{ 0\leq i \leq n-k.}\) Wtedy strategia wyboru może być taka:
wiedząc, ile piw macie przeznaczyć na drugi dzień, najpierw wybieracie \(\displaystyle{ i}\) piw na ten drugi dzień degustacji, żeby je schować przed współlokatorami z akademika. Jak już wybierzecie \(\displaystyle{ i}\) piw na drugi dzień, to pozostanie wybrać \(\displaystyle{ k}\) piw spośród pozostałych \(\displaystyle{ n-i}\) piw na pierwszy dzień degustacji. No i pozostaje wszystko zsumować po \(\displaystyle{ i}\) od \(\displaystyle{ 0}\) do \(\displaystyle{ n-k}\), bo jasnowidz może powiedzieć dowolną liczbę z tego przedziału