Matematyka dyskretna 1/Ćwiczenia 5: Współczynniki dwumianowe: Różnice pomiędzy wersjami

Wersja z 09:06, 2 wrz 2006

Współczynniki dwumianowe

Ćwiczenie 1

Wskaż największy wyraz w $n$ -tym wierszu Trójkąta Pascala i odpowiedź uzasadnij.

Wskazówka

Największym wyrazem w $n$ -tym wierszu jest wyraz środkowy $(\binom{n}{⌊ n / 2 ⌋}) = (\binom{n}{⌈ n / 2 ⌉})$ . Korzystając ze wzoru na postać zwartą współczynnika dwumianowego, pokaż $(\binom{n}{k}) < (\binom{n}{k + 1})$ dla $k < ⌊ n / 2 ⌋$ .

Rozwiązanie

Ponieważ $(\binom{n}{k}) = (\binom{n}{n - k})$ , dla $n ⩾ k ⩾ 0$ , to aby pokazać, że największym wyrazem w $n$ -tym wierszu jest $(\binom{n}{⌊ n / 2 ⌋}) = (\binom{n}{⌈ n / 2 ⌉})$ , wystarczy pokazać, że

(\binom{n}{k}) < (\binom{n}{k + 1}),

dla $k < ⌊ \frac{n}{2} ⌋$ . Nierówność ta jest równoważna kolejno

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \frac{n!}{k!(n-k)!}&<\frac{n!}{(k+1)!(n-k-1)!},\\ \frac{1}{n-k}&<\frac{1}{k+1},\\ k+1&<n-k,\\ k&<\frac{n-1}{2}. \endaligned}

Ostatnia nierówność zachodzi dla $k < ⌊ \frac{n}{2} ⌋$ , zatem wszystkie poprzednie też zachodzą.

Ćwiczenie 2

Posługując się interpretacją kombinatoryczną pokaż, że

(\binom{n}{0}) (\binom{n}{k}) + (\binom{n}{1}) (\binom{n - 1}{k - 1}) + \dots + (\binom{n}{k}) (\binom{n - k}{0}) = 2^{k} (\binom{n}{k}) .

Wskazówka

Rozważ liczbę kolorowań $k$ rozróżnialnych obiektów wybranych spośród $n$ , przy użyciu dwu kolorów.

Rozwiązanie

Policzmy kolorowania $k$ rozróżnialnych obiektów wybranych spośród $n$ , przy użyciu dwu kolorów (biały i czarny). Podzbiór $k$ -elementowy $n$ -elementowego zbioru obiektów można wybrać na $(\binom{n}{k})$ sposobów i każdy taki podzbiór możemy pokolorować na $2^{k}$ sposobów. Zatem liczba interesujących nas kolorowań to $2^{k} (\binom{n}{k})$ .

Policzmy nasze kolorowania inną metodą. Zauważmy, iż dowolne kolorowanie posiada $i$ obiektów białych i $k - i$ czarnych dla pewnego $i \in {0, \dots, k}$ . Zatem każde kolorowanie możemy jednoznacznie otrzymać wybierając najpierw $i$ obiektów spośród wszystkich $n$ (i kolorując je na biało), a później z pozostałych $n - i$ obiektów wybierając $k - i$ (kolorując je na czarno). Możemy to zrobić na $(\binom{n}{i}) (\binom{n - i}{k - i})$ sposobów, czyli sumując po wszystkich możliwych wartościach $i$ otrzymujemy $\sum_{i = 0}^{k} (\binom{n}{i}) (\binom{n - i}{k - i})$ .

Ćwiczenie 3

Posługując się interpretacją kombinatoryczną pokaż, że

{(\binom{n}{0})}^{2} + {(\binom{n}{1})}^{2} + \dots + {(\binom{n}{n})}^{2} = (\binom{2 n}{n}) .

Wskazówka

Rozważ liczbę wyborów $n$ osób z $2 n$ -osobowej grupy złożonej z $n$ mężczyzn i $n$ kobiet.

Rozwiązanie

Rozważmy na ile sposobów możemy wybrać $n$ osób z grupy $n$ mężczyzn i $n$ kobiet. Oczywiście, z jednej strony, sposobów wyboru $n$ spośród $2 n$ osób jest $(\binom{2 n}{n})$ . Alternatywnie zauważmy, że wybierając $n$ osób wybieramy $i$ mężczyzn i $n - i$ kobiet dla pewnego $i \in {0, \dots, n}$ . Dla ustalonego $i$ możemy to wykonać na $(\binom{n}{i}) (\binom{n}{n - i}) = {(\binom{n}{i})}^{2}$ sposobów, zatem sumarycznie liczba możliwości to $\sum_{i = 0}^{n} {(\binom{n}{i})}^{2}$ , co było do pokazania.

Ćwiczenie 4

Posługując się interpretacją kombinatoryczną pokaż, że

(\binom{n}{1}) + 2 (\binom{n}{2}) + \dots + n (\binom{n}{n}) = n 2^{n - 1} .

Wskazówka

Rozważ liczbę wyborów z grupy $n$ osób podzbioru z wyznaczonym w nim przywódcą.

Rozwiązanie

Rozważmy na ile sposobów można wybrać z grupy $n$ osób podzbiór z wyznaczonym w nim przywódcą. Z jednej strony możemy najpierw wybrać przywódcę spośród $n$ osób, a później dobrać do niego dowolny podzbiór zbioru pozostałych $n - 1$ osób. Możemy to zrobić na $n 2^{n - 1}$ sposobów.

Z drugiej strony możemy najpierw wybrać niepusty podzbiór $i$ -elementowy (dla $i \in {1, \dots, n}$ ) zbioru $n$ osób, a potem wybrać spośród nich przywódcę na jeden z $i$ sposobów. Sumując po wszystkich $i$ możemy wykonać to na $\sum_{i = 0}^{n} i (\binom{n}{i})$ sposobów, co było do pokazania.

Ćwiczenie 5

Posługując się interpretacją kombinatoryczną pokaż, że

1^{2} {(\binom{n}{1})}^{2} + 2^{2} {(\binom{n}{2})}^{2} + \dots + n^{2} (\binom{n}{n}) = n^{2} (\binom{2 n - 2}{n - 1}) .

Wskazówka

Rozważ liczbę wyborów z grupy $2 n$ osobowej złożonej z $n$ mężczyzn i $n$ kobiet podzbioru, w którym liczba kobiet i mężczyzn jest równa i ponadto, w którym wyróżnionych jest dwóch przywódców jeden mężczyzna i jedna kobieta.

Rozwiązanie

Dla rozgrzewki rozważmy, na ile sposobów z grupy $2 n$ osób złożonej z $n$ mężczyzn i $n$ kobiet można wybrać podzbiór osób, w którym liczba mężczyzn i kobiet jest równa. Nietrudno zauważyć, iż jest to $\sum_{i = 0}^{n} {(\binom{n}{i})}^{2}$ , a z Ćwiczenia 3 wiemy, że $\sum_{i = 0}^{n} {(\binom{n}{i})}^{2} = (\binom{2 n}{n})$ .

Zastanówmy się teraz z kolei na ile sposobów można wybrać z tej samej $2 n$ osobowej grupy podzbiór, w którym liczba mężczyzn i kobiet jest równa i dodatkowo wśród wybranych jest wyróżnionych dwóch przywódców: jeden mężczyzna i jedna kobieta.

Dla ustalonego $i \in {1, \dots, n}$ możemy najpierw wybrać $i$ kobiet i $i$ mężczyzn na ${(\binom{n}{i})}^{2}$ sposobów, a potem spośród nich wyłonić przywódców na $i^{2}$ sposobów. Zatem sumarycznie możemy dokonać wyboru na $\sum_{i = 1}^{n} i^{2} {(\binom{n}{i})}^{2}$ .

Alternatywnie możemy najpierw wybrać przywódcę jednego spośród $n$ mężczyzn i jednej spośród $n$ kobiet na $n^{2}$ sposobów, a potem uzupełnić wybrańców dobierając im $i$ mężczyzn i tyle samo kobiet, dla $i \in {0, \dots, n - 1}$ . Z początkowej naszej refleksji możemy to zrobić na $(\binom{2 n - 2}{n - 1})$ sposobów. Podsumowując, interesującego nas wyboru możemy dokonać na $n^{2} (\binom{2 n - 2}{n - 1})$ , co było do pokazania.

<flash>file=SW 8.CW1.swf|width=250|height=250</flash>

<div.thumbcaption>SW 8.CW1.swf

Ćwiczenie 6

Ile prostokątów zawiera się w kratce $n \times n$ ? Dla przykładu w kratce $2 \times 2$ jest ich $9$ .

Wskazówka

Rozważ ile prostokątów w kratce $n \times n$ zawiera się w górnej lewej podkratce $m \times m$ (dla $m < n$ ), ale nie zawiera się w górnej lewej podkratce $(m - 1) \times (m - 1)$ .

Rozwiązanie

<flash>file=SW 8.CW3.swf|width=250|height=250</flash>

<div.thumbcaption>SW 8.CW3.swf

Policzmy ile prostokątów w kratce $n \times n$ położonych jest w lewej górnej podkratce $m \times m$ i przylega do chociaż jednej z wewnętrznych (czyli dolnej bądź prawej) krawędzi podkratki. Kilka przykładów takich prostokątów przedstawiamy poniżej dla $n = 5$ i $m = 4$ :

Prostokąt przylegający do prawej pionowej krawędzi podkratki $m \times m$ i nieprzylegający do dolnej poziomej krawędzi jest jednoznacznie wyznaczony przez wybór $1$ pionowej krawędzi spośród $m$ i dwu poziomych krawędzi spośród $m$ .

Zatem jest dokładnie $(\binom{m}{1}) (\binom{m}{2}) = \frac{m^{2} (m - 1)}{2}$ takich prostokątów. Analogicznie jest $\frac{m^{2} (m - 1)}{2}$ prostokątów przylegających do dolnej krawędzi podkratki $m \times m$ i nieprzylegających do prawej. W końcu jest dokładnie $m^{2}$ prostokątów leżących w prawym dolnym narożniku podkratki $m \times m$ , gdyż są one jednoznacznie wyznaczone przez wybór $1$ poziomej linii spośród $m$ i $1$ pionowej linii spośród $m$ .

Zatem w sumie jest

$\frac{m^{2} (m - 1)}{2} + \frac{m^{2} (m - 1)}{2} + m^{2} = m^{3},$

prostokątów w podkratce $m \times m$ przylegających do chociaż jednej wewnętrznej krawędzi. Sumując po $m \in {1, \dots, n}$ otrzymujemy liczbę wszystkich prostokątów w kratce $n \times n$ , czyli jest ich

$1^{3} + 2^{3} + \dots + n^{3} = {(\frac{n (n + 1)}{2})}^{2} .$

Ćwiczenie 7

Udowodnij, że:

$(- 4)^{n} (\binom{- \frac{1}{2}}{n}) = (\binom{2 n}{n}) .$

Wskazówka

Rozwiązanie

Dowód przez indukcję względem $n$ . Dla $n = 1$ mamy

$(- 4)^{1} (\binom{- \frac{1}{2}}{1}) = (- 4) \frac{- \frac{1}{2}}{1} = 2 = (\binom{2}{1}) .$

Ponadto:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned {2(n+1)\choose n+1} &=\frac{(2n+1)(2n+2)}{(n+1)^2}{2n\choose n}\\ &=\frac{2(2n+1)}{n+1}(-4)^n{-\frac{1}{2}\choose n}\\ &=(-4)^{n+1}\frac{(-\frac{1}{2}-n)}{n+1}{-\frac{1}{2}\choose n}\\ &=(-4)^{n+1}{-\frac{1}{2}\choose n+1}. \endaligned}

Ćwiczenie 8

Udowodnij, że:

$f_{n + 1} = \sum_{k = 0}^{n} (\binom{n - k}{k})$

gdzie $f_{n}$ jest $n$ -tą liczbą Fibonacci'ego

Wskazówka

Rozwiązanie

Dowód indukcyjny względem $n$ . Dla $n = 0$ i $n = 1$ mamy odpowiednio $f_{1} = 1 = (\binom{0}{0}) = 1$ i $f_{2} = 1 = 1 + 0 = (\binom{1}{0}) + (\binom{0}{1})$ . Ponadto:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned f_{n+2}&=f_n+f_{n+1}\\ &=\sum_{k=0}^{n-1}{n-1-k\choose k}+\sum_{k=0}^n{n-k\choose k}\\ &={n\choose 0}+\sum_{k=0}^{n-1}\left({n-1-k\choose k}+{n-(k+1)\choose k+1}\right)\\ &={n\choose0}+\sum_{k=0}^{n-1}{n-k\choose k+1}\\ &={n+1\choose0}+\sum_{k=1}^{n}{n+1-k\choose k}+ 0\\ &=\sum_{k=0}^{n}{n+1-k\choose k}+ {0 \choose n+1}\\ &=\sum_{k=0}^{n+1}{n+1-k\choose k}. \endaligned}

@@ Linia 1: / Linia 1: @@
 ==Współczynniki dwumianowe==
-{{cwiczenie|ex dwum srodkowy wyraz trojkata||
+{{cwiczenie|1|cw 1|
 Wskaż największy wyraz w <math>\displaystyle n</math>-tym wierszu Trójkąta Pascala i odpowiedź uzasadnij.
@@ Linia 19: / Linia 18: @@
 <math>\displaystyle {n\choose{\left\lfloor n/2 \right\rfloor}}={n\choose{\left\lceil n/2 \right\rceil}}</math>,
 wystarczy pokazać, że
 <center><math>\displaystyle {n\choose k}<{n\choose k+1},
 </math></center>
 dla <math>\displaystyle k<\left\lfloor \frac{n}{2} \right\rfloor</math>.
 Nierówność ta jest równoważna kolejno
 <center><math>\displaystyle \aligned \frac{n!}{k!(n-k)!}&<\frac{n!}{(k+1)!(n-k-1)!},\\
@@ Linia 31: / Linia 33: @@
 k&<\frac{n-1}{2}.
 \endaligned</math></center>
 Ostatnia nierówność zachodzi dla <math>\displaystyle k<\left\lfloor \frac{n}{2} \right\rfloor</math>,
@@ Linia 37: / Linia 40: @@
 </div></div>
-{{cwiczenie|ex dwum kolorowanie k podzbiorow n elementowego zbioru 2 kolorami||
+{{cwiczenie|2|cw 2|
+Posługując się interpretacją kombinatoryczną pokaż, że
-Posługując się interpretacją kombinatoryczną pokaż, że
 <center><math>\displaystyle {n\choose0}{n\choose k}+{n\choose1}{n-1\choose k-1}+\ldots+{n\choose k}{n-k\choose0}
 =2^k{n\choose k}.
 </math></center>
 }}
@@ Linia 70: / Linia 74: @@
 </div></div>
-{{cwiczenie|ex dwum wybranie n osob sposrod n mezczyzn i n kobiet||
+{{cwiczenie|3|cw 3|
+Posługując się interpretacją kombinatoryczną pokaż, że
-Posługując się interpretacją kombinatoryczną pokaż, że
 <center><math>\displaystyle {n\choose 0}^2+{n\choose1}^2+\ldots+{n\choose n}^2={2n\choose n}.
 </math></center>
 }}
@@ Linia 94: / Linia 99: @@
 </div></div>
-{{cwiczenie|ex dwum wybieranie podzbioru z przywodca||
+{{cwiczenie|4|cw 4|
+Posługując się interpretacją kombinatoryczną pokaż, że
-Posługując się interpretacją kombinatoryczną pokaż, że
 <center><math>\displaystyle {n\choose 1}+2{n\choose 2}+\ldots+n{n\choose n}=n2^{n-1}.
 </math></center>
 }}
@@ Linia 114: / Linia 120: @@
 </div></div>
-{{cwiczenie|ex dwum wybieranie podzbioru mezczyzn i kobiet z przywodcami||
+{{cwiczenie|5|cw 5|
+Posługując się interpretacją kombinatoryczną pokaż, że
-Posługując się interpretacją kombinatoryczną pokaż, że
 <center><math>\displaystyle 1^2{n\choose 1}^2+2^2{n\choose 2}^2+\ldots+n^2{n\choose n}=n^2{2n-2\choose n-1}.
 </math></center>
 }}
@@ Linia 135: / Linia 142: @@
 można wybrać podzbiór osób, w którym liczba mężczyzn i kobiet jest równa.
 Nietrudno zauważyć, iż jest to <math>\displaystyle \sum_{i=0}^n{n\choose i}^2</math>,
-a z Zadania [[##ex dwum wybranie n osob sposrod n mezczyzn i n kobiet|Uzupelnic ex dwum wybranie n osob sposrod n mezczyzn i n kobiet|]]
+a z [[#cw_3|Ćwiczenia 3]]
 wiemy, że <math>\displaystyle \sum_{i=0}^n{n\choose i}^2={2n\choose n}</math>.
@@ Linia 164: / Linia 171: @@
 </div>
-{{cwiczenie|ex dwum liczba prostokatow w kratce n na n||
+{{cwiczenie|6|cw 6|
 Ile prostokątów zawiera się w kratce <math>\displaystyle n\times n</math>?
 Dla przykładu w kratce <math>\displaystyle 2\times2</math> jest ich <math>\displaystyle 9</math>.
@@ Linia 206: / Linia 212: @@
 Zatem w sumie jest
 <center>
@@ Linia 211: / Linia 218: @@
 </math>
 </center>
 prostokątów w podkratce <math>\displaystyle m\times m</math> przylegających do chociaż jednej wewnętrznej krawędzi. Sumując po <math>\displaystyle m\in\left\lbrace 1,\ldots,n \right\rbrace</math> otrzymujemy liczbę wszystkich prostokątów w kratce <math>\displaystyle n\times n</math>, czyli jest ich
 <center>
@@ Linia 218: / Linia 227: @@
 </math>
 </center>
 </div></div>
-{{cwiczenie|ex dwum tozsamosc z 1/2 w indeksie gornym||
+{{cwiczenie|7|cw 7|
+Udowodnij, że:
-Udowodnij, że:
 <center>
@@ Linia 229: / Linia 239: @@
 </math>
 </center>
 }}
@@ Linia 239: / Linia 250: @@
 Dowód przez indukcję względem <math>\displaystyle n</math>.
 Dla <math>\displaystyle n=1</math> mamy
 <center>
@@ Linia 244: / Linia 256: @@
 </math>
 </center>
 Ponadto:
 <center>
@@ Linia 255: / Linia 269: @@
 \endaligned</math>
 </center>
 </div></div>
-{{cwiczenie|ex dwum sumka z fibonaccimi||
+{{cwiczenie|8|cw 8|
+Udowodnij, że:
-Udowodnij, że:
 <center>
@@ Linia 266: / Linia 281: @@
 </math>
 </center>
 gdzie <math>\displaystyle f_n</math> jest <math>\displaystyle n</math>-tą liczbą Fibonacci'ego
@@ Linia 285: / Linia 301: @@
 <math>\displaystyle f_1=1= {0\choose0}=1</math>  i <math>\displaystyle f_2=1=1+0={1\choose0}+{0\choose1}</math>.
 Ponadto:
 <center>
@@ Linia 296: / Linia 313: @@
 \endaligned</math>
 </center>
 </div></div>

Matematyka dyskretna 1/Ćwiczenia 5: Współczynniki dwumianowe: Różnice pomiędzy wersjami

Wersja z 09:06, 2 wrz 2006

Współczynniki dwumianowe

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia