Własność symbolu Newtona. Dowód.
-
- Użytkownik
- Posty: 1185
- Rejestracja: 13 paź 2012, o 17:34
- Płeć: Kobieta
- Lokalizacja: tu i tam
- Podziękował: 528 razy
- Pomógł: 5 razy
Własność symbolu Newtona. Dowód.
\(\displaystyle{ \sum_{r=0}^{n} {r \choose k} = {n+1 \choose k+1}}\)
DOWÓD : (a raczej nieudolna próba)
\(\displaystyle{ X = \{1,2,...,n,n+1\}}\)
\(\displaystyle{ L : {0 \choose k} + {1 \choose k} + {2 \choose k} +...+ {n \choose k}+ {n+1 \choose k}}\)
\(\displaystyle{ A \subseteq X , |A|=k , |X|=n+1}\)
\(\displaystyle{ j=min(A)}\)
Podzbiory k-elementowe, takie, że \(\displaystyle{ 1=min(A)}\), to wszystkie podzbiory zawierające el 1.
Liczba takich podzbiorów : \(\displaystyle{ {n+1 \ choose k}}\)
Podzbiory k-elemntowe, takie, że \(\displaystyle{ 2=min(A)}\), to wszystkie podzbiory zawierające el 2 i nie zawierające el 1.
Liczba takich podzbiorów : \(\displaystyle{ {n+2-1 \choose k} = {n+1 \choose k}}\)
Podzbiory k-elemntowe, tak, że \(\displaystyle{ 3=min(A)}\), to wszystkie podzbiory zawierające el.3 i nie zawierające el.2 i 1
Liczba takich podzbiorów : \(\displaystyle{ {n \choose k}}\)
\(\displaystyle{ 4=min(A)}\)
\(\displaystyle{ {n+4-3-2-1 \choose k} = {n-2 \choose k}}\)
\(\displaystyle{ 5=min(A)}\)
\(\displaystyle{ {n+5-4-3-2-1 \choose k} = {n-5 \choose k}}\)
\(\displaystyle{ 6=min(A)}\)
\(\displaystyle{ {n+6-5-4-3-2-1 \choose k} = {n-9 \choose k}}\)
...
\(\displaystyle{ n=min(A)}\)
\(\displaystyle{ {n+n-(n-1)-...-1 \choose k} = {n+n-n+1-...-1 \choose k}}\)
I co dalej? Nie mam pomysłu. Podpowiedź do zadania było użycie funkcji : j=min(A)
DOWÓD : (a raczej nieudolna próba)
\(\displaystyle{ X = \{1,2,...,n,n+1\}}\)
\(\displaystyle{ L : {0 \choose k} + {1 \choose k} + {2 \choose k} +...+ {n \choose k}+ {n+1 \choose k}}\)
\(\displaystyle{ A \subseteq X , |A|=k , |X|=n+1}\)
\(\displaystyle{ j=min(A)}\)
Podzbiory k-elementowe, takie, że \(\displaystyle{ 1=min(A)}\), to wszystkie podzbiory zawierające el 1.
Liczba takich podzbiorów : \(\displaystyle{ {n+1 \ choose k}}\)
Podzbiory k-elemntowe, takie, że \(\displaystyle{ 2=min(A)}\), to wszystkie podzbiory zawierające el 2 i nie zawierające el 1.
Liczba takich podzbiorów : \(\displaystyle{ {n+2-1 \choose k} = {n+1 \choose k}}\)
Podzbiory k-elemntowe, tak, że \(\displaystyle{ 3=min(A)}\), to wszystkie podzbiory zawierające el.3 i nie zawierające el.2 i 1
Liczba takich podzbiorów : \(\displaystyle{ {n \choose k}}\)
\(\displaystyle{ 4=min(A)}\)
\(\displaystyle{ {n+4-3-2-1 \choose k} = {n-2 \choose k}}\)
\(\displaystyle{ 5=min(A)}\)
\(\displaystyle{ {n+5-4-3-2-1 \choose k} = {n-5 \choose k}}\)
\(\displaystyle{ 6=min(A)}\)
\(\displaystyle{ {n+6-5-4-3-2-1 \choose k} = {n-9 \choose k}}\)
...
\(\displaystyle{ n=min(A)}\)
\(\displaystyle{ {n+n-(n-1)-...-1 \choose k} = {n+n-n+1-...-1 \choose k}}\)
I co dalej? Nie mam pomysłu. Podpowiedź do zadania było użycie funkcji : j=min(A)
-
- Użytkownik
- Posty: 2203
- Rejestracja: 15 lis 2012, o 00:13
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 43 razy
- Pomógł: 526 razy
Własność symbolu Newtona. Dowód.
P: Liczba \(\displaystyle{ \left( k+1\right)}\)-elementowych podzbiorów zbioru \(\displaystyle{ \left( n+1\right)}\)-elementowego.
Spróbuj sprytnie zapisać lewą stronę, żeby była równoliczna z prawą, czyli uzależnij liczbę \(\displaystyle{ \left( k+1\right)}\)-elementowych podzbiorów zbioru \(\displaystyle{ \left( n+1\right)}\)-elementowego z zapisem po lewej stronie.
Spróbuj sprytnie zapisać lewą stronę, żeby była równoliczna z prawą, czyli uzależnij liczbę \(\displaystyle{ \left( k+1\right)}\)-elementowych podzbiorów zbioru \(\displaystyle{ \left( n+1\right)}\)-elementowego z zapisem po lewej stronie.
-
- Użytkownik
- Posty: 2203
- Rejestracja: 15 lis 2012, o 00:13
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 43 razy
- Pomógł: 526 razy
Własność symbolu Newtona. Dowód.
Trochę pokręciłaś. Rozważ takie zbiory:
\(\displaystyle{ X=\left[ n+1\right]}\)
\(\displaystyle{ A_r=\left\{ S \subseteq X:\left| S\right|=k+1 \wedge \max S=r+1 \right\}}\)
Od razu widać, że liczba \(\displaystyle{ \left( k+1\right)}\)-elementowych podzbiorów \(\displaystyle{ X}\) wynosi \(\displaystyle{ {n+1 \choose k+1}}\)
Teraz spróbuj z tym połączyć rodzinę zbiorów \(\displaystyle{ A_r}\)
\(\displaystyle{ X=\left[ n+1\right]}\)
\(\displaystyle{ A_r=\left\{ S \subseteq X:\left| S\right|=k+1 \wedge \max S=r+1 \right\}}\)
Od razu widać, że liczba \(\displaystyle{ \left( k+1\right)}\)-elementowych podzbiorów \(\displaystyle{ X}\) wynosi \(\displaystyle{ {n+1 \choose k+1}}\)
Teraz spróbuj z tym połączyć rodzinę zbiorów \(\displaystyle{ A_r}\)
-
- Użytkownik
- Posty: 2203
- Rejestracja: 15 lis 2012, o 00:13
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 43 razy
- Pomógł: 526 razy
Własność symbolu Newtona. Dowód.
Myślę, że wersja z \(\displaystyle{ \max}\) jest prostsza i bardziej intuicyjna.
Wskazówka do połączenia obydwu stron.\(\displaystyle{ L}\): zbiór podzbiorów:
1) \(\displaystyle{ k+1}\) elementowych takich, że \(\displaystyle{ \max A=2}\)
2) \(\displaystyle{ k+1}\) elementowych takich, że \(\displaystyle{ \max A=3}\)
3) \(\displaystyle{ k+1}\) elementowych takich, że \(\displaystyle{ \max A=4}\)
...
Wskazówka do połączenia obydwu stron.\(\displaystyle{ L}\): zbiór podzbiorów:
1) \(\displaystyle{ k+1}\) elementowych takich, że \(\displaystyle{ \max A=2}\)
2) \(\displaystyle{ k+1}\) elementowych takich, że \(\displaystyle{ \max A=3}\)
3) \(\displaystyle{ k+1}\) elementowych takich, że \(\displaystyle{ \max A=4}\)
...
Ostatnio zmieniony 18 mar 2013, o 17:24 przez rafalpw, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 2203
- Rejestracja: 15 lis 2012, o 00:13
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 43 razy
- Pomógł: 526 razy
Własność symbolu Newtona. Dowód.
Na ile sposobów można wybrać \(\displaystyle{ \left( k+1\right)}\)-elementowy podzbiór\(\displaystyle{ A}\) zbioru \(\displaystyle{ \left[ n+1\right]}\) tak, aby \(\displaystyle{ \max A=r+1}\) ?
-
- Użytkownik
- Posty: 1185
- Rejestracja: 13 paź 2012, o 17:34
- Płeć: Kobieta
- Lokalizacja: tu i tam
- Podziękował: 528 razy
- Pomógł: 5 razy
Własność symbolu Newtona. Dowód.
Dziękuję Rafał za nowy pomysł, ale nie skorzystam.
Jakbyś mógł, to zerknij na to :
\(\displaystyle{ \sum_{r=0}^{n} {r \choose k} = {n+1 \choose k+1}}\)
L:\(\displaystyle{ {0 \choose k} + {1 \choose k} + ... + {n \choose k}}\)
|X|=n+1
\(\displaystyle{ |A|=k+1}\)
\(\displaystyle{ j=min(A)}\)
\(\displaystyle{ j=1=min(A)}\)
Podzbiory k-elemntowe, takie, że \(\displaystyle{ 1=min(A)}\), to wszystkie podzbiory zawierające ten element.
Elemntów w zbiorze X jest \(\displaystyle{ n+1}\), więc posiadając gwarantując sobie w zbiorze el 1, możemy wybrać ich na \(\displaystyle{ {n \choose k}}\) sposobów. Patrząc na naszą lewą stronę nierówności, jest to ostatni elemnt.
\(\displaystyle{ j=2=min(A)}\)
Podzbiorów k-elemntowych, takich, że \(\displaystyle{ 2=min(A)}\), to wszystke podzbiory zawierające 2 i nie zawierające 1. Możemy je wybrać \(\displaystyle{ {n -1 \choose k}}\) sposobów.
....
\(\displaystyle{ j=n-k+1=min(A)}\)
Te podzbiory możemy wybrać na \(\displaystyle{ {k \choose k}}\) sposobów.
To nie jest ostatni elemnt naszej sumy, jednak każdy zbiór zawierający większy element minimalny, będzie miał wartość 0, gdyż nie możemy wybrać więcej elemntów, niż mamy w zbiorze.
Z prawa dodawania wychodzi równość z prawą stroną.
Ogólny wzór na \(\displaystyle{ A_j = {n+1-j \choose k} , j\in\{1,...,n+1\}}\)
Proszę o takie merytoryczne sprawdzenie.
Jakbyś mógł, to zerknij na to :
\(\displaystyle{ \sum_{r=0}^{n} {r \choose k} = {n+1 \choose k+1}}\)
L:\(\displaystyle{ {0 \choose k} + {1 \choose k} + ... + {n \choose k}}\)
|X|=n+1
\(\displaystyle{ |A|=k+1}\)
\(\displaystyle{ j=min(A)}\)
\(\displaystyle{ j=1=min(A)}\)
Podzbiory k-elemntowe, takie, że \(\displaystyle{ 1=min(A)}\), to wszystkie podzbiory zawierające ten element.
Elemntów w zbiorze X jest \(\displaystyle{ n+1}\), więc posiadając gwarantując sobie w zbiorze el 1, możemy wybrać ich na \(\displaystyle{ {n \choose k}}\) sposobów. Patrząc na naszą lewą stronę nierówności, jest to ostatni elemnt.
\(\displaystyle{ j=2=min(A)}\)
Podzbiorów k-elemntowych, takich, że \(\displaystyle{ 2=min(A)}\), to wszystke podzbiory zawierające 2 i nie zawierające 1. Możemy je wybrać \(\displaystyle{ {n -1 \choose k}}\) sposobów.
....
\(\displaystyle{ j=n-k+1=min(A)}\)
Te podzbiory możemy wybrać na \(\displaystyle{ {k \choose k}}\) sposobów.
To nie jest ostatni elemnt naszej sumy, jednak każdy zbiór zawierający większy element minimalny, będzie miał wartość 0, gdyż nie możemy wybrać więcej elemntów, niż mamy w zbiorze.
Z prawa dodawania wychodzi równość z prawą stroną.
Ogólny wzór na \(\displaystyle{ A_j = {n+1-j \choose k} , j\in\{1,...,n+1\}}\)
Proszę o takie merytoryczne sprawdzenie.
-
- Użytkownik
- Posty: 2203
- Rejestracja: 15 lis 2012, o 00:13
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 43 razy
- Pomógł: 526 razy
Własność symbolu Newtona. Dowód.
To się zgadza.myszka9 pisze: To nie jest ostatni elemnt naszej sumy, jednak każdy zbiór zawierający większy element minimalny, będzie miał wartość 0, gdyż nie możemy wybrać więcej elementów, niż mamy w zbiorze.
To wymaga wyjaśnienia. To właśnie próbujesz pokazać. Myślę, że to nie jest takie oczywiste.myszka9 pisze: Z prawa dodawania wychodzi równość z prawą stroną.
Ogólnie rozumowanie dobre. Nie wiem, czemu nie spodobał Ci się mój sposób, biorąc pod uwagę, że jest prawie identyczny.
-
- Użytkownik
- Posty: 1185
- Rejestracja: 13 paź 2012, o 17:34
- Płeć: Kobieta
- Lokalizacja: tu i tam
- Podziękował: 528 razy
- Pomógł: 5 razy
Własność symbolu Newtona. Dowód.
Jest to sposób zliczenia wszystkich \(\displaystyle{ k+1}\) elementowych podzbiorów ze zbioru \(\displaystyle{ n+1}\) elementowego, ze względu na parametr \(\displaystyle{ r = n+1-j}\) , gdzie j jest elementem minimalnym pozbioru. Zbiór \(\displaystyle{ n+1}\) został podzielony na podzbiory ze względu właśnie na element minimalny.
?
?
-
- Użytkownik
- Posty: 2203
- Rejestracja: 15 lis 2012, o 00:13
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 43 razy
- Pomógł: 526 razy
Własność symbolu Newtona. Dowód.
To zdanie było kluczowe. Wszystkie \(\displaystyle{ \left( k+1\right)}\)-elementowe podzbiory można podzielić na:myszka9 pisze:Zbiór \(\displaystyle{ n+1}\) został podzielony na podzbiory ze względu właśnie na element minimalny.
\(\displaystyle{ \left( k+1\right)}\) -elementowe podzbiory, których elementem najmniejszym jest \(\displaystyle{ 1}\)
\(\displaystyle{ \left( k+1\right)}\) -elementowe podzbiory, których elementem najmniejszym jest \(\displaystyle{ 2}\)
...
Warto jeszcze dopowiedzieć, że te zbiory podzbiorów są rozłączne i dlatego można zastosować regułę dodawania.