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

Aktualna wersja na dzień 21:50, 11 wrz 2023

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

\begin{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} . \end{aligned}

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} = 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.

Ć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

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:

$\begin{aligned} (\binom{2 (n + 1)}{n + 1}) & = \frac{(2 n + 1) (2 n + 2)}{(n + 1)^{2}} (\binom{2 n}{n}) \\ = \frac{2 (2 n + 1)}{n + 1} (- 4)^{n} (\binom{- \frac{1}{2}}{n}) \\ = (- 4)^{n + 1} \frac{(- \frac{1}{2} - n)}{n + 1} (\binom{- \frac{1}{2}}{n}) \\ = (- 4)^{n + 1} (\binom{- \frac{1}{2}}{n + 1}) . \end{aligned}$

Ć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:

$\begin{aligned} f_{n + 2} & = f_{n} + f_{n + 1} \\ = \sum_{k = 0}^{n - 1} (\binom{n - 1 - k}{k}) + \sum_{k = 0}^{n} (\binom{n - k}{k}) \\ = (\binom{n}{0}) + \sum_{k = 0}^{n - 1} ((\binom{n - 1 - k}{k}) + (\binom{n - (k + 1)}{k + 1})) \\ = (\binom{n}{0}) + \sum_{k = 0}^{n - 1} (\binom{n - k}{k + 1}) \\ = (\binom{n + 1}{0}) + \sum_{k = 1}^{n} (\binom{n + 1 - k}{k}) + 0 \\ = \sum_{k = 0}^{n} (\binom{n + 1 - k}{k}) + (\binom{0}{n + 1}) \\ = \sum_{k = 0}^{n + 1} (\binom{n + 1 - k}{k}) . \end{aligned}$

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

Aktualna wersja na dzień 21:50, 11 wrz 2023

Współczynniki dwumianowe

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 2: / Linia 2: @@
 {{cwiczenie|1|cw 1|
-Wskaż największy wyraz w <math>\displaystyle n</math>-tym wierszu Trójkąta Pascala i odpowiedź uzasadnij.
+Wskaż największy wyraz w <math>n</math>-tym wierszu Trójkąta Pascala i odpowiedź uzasadnij.
 }}
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
-Największym wyrazem w <math>\displaystyle n</math>-tym wierszu jest wyraz środkowy
+Największym wyrazem w <math>n</math>-tym wierszu jest wyraz środkowy
-<math>\displaystyle {n \choose {\left\lfloor n/2 \right\rfloor}}={n \choose {\left\lceil n/2 \right\rceil}}</math>.
+<math>{n \choose {\left\lfloor n/2 \right\rfloor}}={n \choose {\left\lceil n/2 \right\rceil}}</math>.
 Korzystając ze wzoru na postać zwartą współczynnika dwumianowego,
-pokaż <math>\displaystyle {n\choose k}<{n\choose k+1}</math> dla <math>\displaystyle k<\left\lfloor n/2 \right\rfloor</math>.
+pokaż <math>{n\choose k}<{n\choose k+1}</math> dla <math>k<\left\lfloor n/2 \right\rfloor</math>.
 </div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-Ponieważ <math>\displaystyle {n\choose k}={n\choose n-k}</math>, dla <math>\displaystyle n\geqslant k\geqslant0</math>,
+Ponieważ <math>{n\choose k}={n\choose n-k}</math>, dla <math>n\geqslant k\geqslant0</math>,
-to aby pokazać, że największym wyrazem w <math>\displaystyle n</math>-tym wierszu jest
+to aby pokazać, że największym wyrazem w <math>n</math>-tym wierszu jest
-<math>\displaystyle {n\choose{\left\lfloor n/2 \right\rfloor}}={n\choose{\left\lceil n/2 \right\rceil}}</math>,
+<math>{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},
+<center><math>{n\choose k}<{n\choose k+1}</math>,</center>
-</math></center>
-dla <math>\displaystyle k<\left\lfloor \frac{n}{2} \right\rfloor</math>.
+dla <math>k<\left\lfloor \frac{n}{2} \right\rfloor</math>.
 Nierówność ta jest równoważna kolejno
-<center><math>\displaystyle \begin{align} \frac{n!}{k!(n-k)!}&<\frac{n!}{(k+1)!(n-k-1)!},\\
+<center><math>\begin{align} \frac{n!}{k!(n-k)!}&<\frac{n!}{(k+1)!(n-k-1)!},\\
 \frac{1}{n-k}&<\frac{1}{k+1},\\
 k+1&<n-k,\\
@@ Linia 35: / Linia 34: @@
-Ostatnia nierówność zachodzi dla <math>\displaystyle k<\left\lfloor \frac{n}{2} \right\rfloor</math>,
+Ostatnia nierówność zachodzi dla <math>k<\left\lfloor \frac{n}{2} \right\rfloor</math>,
 zatem wszystkie poprzednie też zachodzą.
@@ Linia 44: / Linia 43: @@
-<center><math>\displaystyle {n\choose0}{n\choose k}+{n\choose1}{n-1\choose k-1}+\ldots+{n\choose k}{n-k\choose0}
+<center><math>{n\choose0}{n\choose k}+{n\choose1}{n-1\choose k-1}+\ldots+{n\choose k}{n-k\choose0}
-=2^k{n\choose k}.
+=2^k{n\choose k}</math></center>
-</math></center>
@@ Linia 52: / Linia 50: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
-Rozważ liczbę kolorowań <math>\displaystyle k</math> rozróżnialnych obiektów wybranych spośród <math>\displaystyle n</math>,
+Rozważ liczbę kolorowań <math>k</math> rozróżnialnych obiektów wybranych spośród <math>n</math>,
 przy  użyciu dwu kolorów.
 </div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-Policzmy kolorowania <math>\displaystyle k</math> rozróżnialnych obiektów wybranych spośród <math>\displaystyle n</math>,
+Policzmy kolorowania <math>k</math> rozróżnialnych obiektów wybranych spośród <math>n</math>,
 przy  użyciu dwu kolorów (biały i czarny).
-Podzbiór <math>\displaystyle k</math>-elementowy <math>\displaystyle n</math>-elementowego zbioru obiektów można wybrać
+Podzbiór <math>k</math>-elementowy <math>n</math>-elementowego zbioru obiektów można wybrać
-na <math>\displaystyle {n\choose k}</math> sposobów i każdy taki podzbiór możemy pokolorować na <math>\displaystyle 2^k</math> sposobów.
+na <math>{n\choose k}</math> sposobów i każdy taki podzbiór możemy pokolorować na <math>2^k</math> sposobów.
-Zatem liczba interesujących nas kolorowań to <math>\displaystyle 2^k{n\choose k}</math>.
+Zatem liczba interesujących nas kolorowań to <math>2^k{n\choose k}</math>.
 Policzmy nasze kolorowania inną metodą.
-Zauważmy, iż dowolne kolorowanie posiada <math>\displaystyle i</math> obiektów białych
+Zauważmy, iż dowolne kolorowanie posiada <math>i</math> obiektów białych
-i <math>\displaystyle k-i</math> czarnych dla pewnego <math>\displaystyle i\in\left\lbrace 0,\ldots,k \right\rbrace</math>.
+i <math>k-i</math> czarnych dla pewnego <math>i\in\left\lbrace 0,\ldots,k \right\rbrace</math>.
-Zatem każde kolorowanie możemy jednoznacznie otrzymać wybierając najpierw <math>\displaystyle i</math>
+Zatem każde kolorowanie możemy jednoznacznie otrzymać wybierając najpierw <math>i</math>
-obiektów spośród wszystkich <math>\displaystyle n</math> (i kolorując je na biało),
+obiektów spośród wszystkich <math>n</math> (i kolorując je na biało),
-a później z pozostałych <math>\displaystyle n-i</math> obiektów wybierając <math>\displaystyle k-i</math> (kolorując je na czarno).
+a później z pozostałych <math>n-i</math> obiektów wybierając <math>k-i</math> (kolorując je na czarno).
-Możemy to zrobić na <math>\displaystyle {n\choose i}{n-i\choose k-i}</math> sposobów,
+Możemy to zrobić na <math>{n\choose i}{n-i\choose k-i}</math> sposobów,
-czyli sumując po wszystkich możliwych wartościach <math>\displaystyle i</math>
+czyli sumując po wszystkich możliwych wartościach <math>i</math>
-otrzymujemy <math>\displaystyle \sum_{i=0}^k{n\choose i}{n-i\choose k-i}</math>.
+otrzymujemy <math>\sum_{i=0}^k{n\choose i}{n-i\choose k-i}</math>.
 </div></div>
@@ Linia 78: / Linia 76: @@
-<center><math>\displaystyle {n\choose 0}^2+{n\choose1}^2+\ldots+{n\choose n}^2={2n\choose n}.
+<center><math>{n\choose 0}^2+{n\choose1}^2+\ldots+{n\choose n}^2={2n\choose n}</math></center>
-</math></center>
@@ Linia 85: / Linia 82: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
-Rozważ liczbę wyborów <math>\displaystyle n</math> osób z <math>\displaystyle 2n</math>-osobowej grupy złożonej z <math>\displaystyle n</math> mężczyzn i <math>\displaystyle n</math> kobiet.
+Rozważ liczbę wyborów <math>n</math> osób z <math>2n</math>-osobowej grupy złożonej z <math>n</math> mężczyzn i <math>n</math> kobiet.
 </div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-Rozważmy na ile sposobów możemy wybrać <math>\displaystyle n</math> osób z grupy <math>\displaystyle n</math> mężczyzn i <math>\displaystyle n</math> kobiet.
+Rozważmy na ile sposobów możemy wybrać <math>n</math> osób z grupy <math>n</math> mężczyzn i <math>n</math> kobiet.
-Oczywiście, z jednej strony, sposobów wyboru <math>\displaystyle n</math> spośród <math>\displaystyle 2n</math> osób jest <math>\displaystyle {2n\choose n}</math>.
+Oczywiście, z jednej strony, sposobów wyboru <math>n</math> spośród <math>2n</math> osób jest <math>{2n\choose n}</math>.
-Alternatywnie zauważmy, że wybierając <math>\displaystyle n</math> osób wybieramy <math>\displaystyle i</math> mężczyzn i <math>\displaystyle n-i</math> kobiet
+Alternatywnie zauważmy, że wybierając <math>n</math> osób wybieramy <math>i</math> mężczyzn i <math>n-i</math> kobiet
-dla pewnego <math>\displaystyle i\in\left\lbrace 0,\ldots,n \right\rbrace</math>.
+dla pewnego <math>i\in\left\lbrace 0,\ldots,n \right\rbrace</math>.
-Dla ustalonego <math>\displaystyle i</math> możemy to wykonać na <math>\displaystyle {n\choose i}{n\choose n-i}={n\choose i}^2</math>
+Dla ustalonego <math>i</math> możemy to wykonać na <math>{n\choose i}{n\choose n-i}={n\choose i}^2</math>
 sposobów, zatem sumarycznie liczba możliwości to
-<math>\displaystyle \sum_{i=0}^n{n\choose i}^2</math>, co było do pokazania.
+<math>\sum_{i=0}^n{n\choose i}^2</math>, co było do pokazania.
 </div></div>
@@ Linia 103: / Linia 100: @@
-<center><math>\displaystyle {n\choose 1}+2{n\choose 2}+\ldots+n{n\choose n}=n2^{n-1}.
+<center><math>{n\choose 1}+2{n\choose 2}+\ldots+n{n\choose n}=n2^{n-1}</math></center>
-</math></center>
@@ Linia 110: / Linia 106: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
-Rozważ liczbę wyborów z grupy <math>\displaystyle n</math> osób podzbioru z wyznaczonym w nim przywódcą.
+Rozważ liczbę wyborów z grupy <math>n</math> osób podzbioru z wyznaczonym w nim przywódcą.
 </div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-Rozważmy na ile sposobów można wybrać z grupy <math>\displaystyle n</math> osób podzbiór z wyznaczonym w nim przywódcą. Z jednej strony możemy najpierw wybrać przywódcę spośród <math>\displaystyle n</math> osób, a później dobrać do niego dowolny podzbiór zbioru pozostałych <math>\displaystyle n-1</math> osób. Możemy to zrobić na <math>\displaystyle n2^{n-1}</math> sposobów.
+Rozważmy na ile sposobów można wybrać z grupy <math>n</math> osób podzbiór z wyznaczonym w nim przywódcą. Z jednej strony możemy najpierw wybrać przywódcę spośród <math>n</math> osób, a później dobrać do niego dowolny podzbiór zbioru pozostałych <math>n-1</math> osób. Możemy to zrobić na <math>n2^{n-1}</math> sposobów.
-Z drugiej strony możemy najpierw wybrać niepusty podzbiór <math>\displaystyle i</math>-elementowy (dla <math>\displaystyle i\in\left\lbrace 1,\ldots,n \right\rbrace</math>) zbioru <math>\displaystyle n</math> osób, a potem wybrać spośród nich przywódcę na jeden z <math>\displaystyle i</math> sposobów. Sumując po wszystkich <math>\displaystyle i</math> możemy wykonać to na <math>\displaystyle \sum_{i=0}^ni{n\choose i}</math> sposobów, co było do pokazania.
+Z drugiej strony możemy najpierw wybrać niepusty podzbiór <math>i</math>-elementowy (dla <math>i\in\left\lbrace 1,\ldots,n \right\rbrace</math>) zbioru <math>n</math> osób, a potem wybrać spośród nich przywódcę na jeden z <math>i</math> sposobów. Sumując po wszystkich <math>i</math> możemy wykonać to na <math>\sum_{i=0}^ni{n\choose i}</math> sposobów, co było do pokazania.
 </div></div>
@@ Linia 124: / Linia 120: @@
-<center><math>\displaystyle 1^2{n\choose 1}^2+2^2{n\choose 2}^2+\ldots+n^2{n\choose n}^n=n^2{2n-2\choose n-1}.
+<center><math>1^2{n\choose 1}^2+2^2{n\choose 2}^2+\ldots+n^2{n\choose n}^n=n^2{2n-2\choose n-1}</math></center>
-</math></center>
@@ Linia 131: / Linia 126: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
-Rozważ liczbę wyborów z grupy <math>\displaystyle 2n</math> osobowej złożonej z <math>\displaystyle n</math> mężczyzn i <math>\displaystyle n</math> kobiet
+Rozważ liczbę wyborów z grupy <math>2n</math> osobowej złożonej z <math>n</math> mężczyzn i <math>n</math> 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.
@@ Linia 138: / Linia 133: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-Dla rozgrzewki rozważmy, na ile sposobów z grupy <math>\displaystyle 2n</math> osób
+Dla rozgrzewki rozważmy, na ile sposobów z grupy <math>2n</math> osób
-złożonej z <math>\displaystyle n</math> mężczyzn i <math>\displaystyle n</math> kobiet
+złożonej z <math>n</math> mężczyzn i <math>n</math> 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 <math>\displaystyle \sum_{i=0}^n{n\choose i}^2</math>,
+Nietrudno zauważyć, iż jest to <math>\sum_{i=0}^n{n\choose i}^2</math>,
 a z [[#cw_3|Ćwiczenia 3]]
-wiemy, że <math>\displaystyle \sum_{i=0}^n{n\choose i}^2={2n\choose n}</math>.
+wiemy, że <math>\sum_{i=0}^n{n\choose i}^2={2n\choose n}</math>.
 Zastanówmy się teraz z kolei na ile sposobów można wybrać
-z tej samej <math>\displaystyle 2n</math> osobowej grupy podzbiór,
+z tej samej <math>2n</math> 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 <math>\displaystyle i\in\left\lbrace 1,\ldots,n \right\rbrace</math> możemy najpierw wybrać <math>\displaystyle i</math> kobiet i <math>\displaystyle i</math> mężczyzn
+Dla ustalonego <math>i\in\left\lbrace 1,\ldots,n \right\rbrace</math> możemy najpierw wybrać <math>i</math> kobiet i <math>i</math> mężczyzn
-na <math>\displaystyle {n\choose i}^2</math> sposobów,
+na <math>{n\choose i}^2</math> sposobów,
-a potem spośród nich wyłonić przywódców na <math>\displaystyle i^2</math> sposobów.
+a potem spośród nich wyłonić przywódców na <math>i^2</math> sposobów.
-Zatem sumarycznie możemy dokonać wyboru na <math>\displaystyle \sum_{i=1}^ni^2{n\choose i}^2</math>.
+Zatem sumarycznie możemy dokonać wyboru na <math>\sum_{i=1}^ni^2{n\choose i}^2</math>.
-Alternatywnie możemy najpierw wybrać przywódcę jednego spośród <math>\displaystyle n</math> mężczyzn
+Alternatywnie możemy najpierw wybrać przywódcę jednego spośród <math>n</math> mężczyzn
-i jednej spośród <math>\displaystyle n</math> kobiet na <math>\displaystyle n^2</math> sposobów,
+i jednej spośród <math>n</math> kobiet na <math>n^2</math> sposobów,
-a potem uzupełnić wybrańców dobierając im <math>\displaystyle i</math> mężczyzn i tyle samo kobiet,
+a potem uzupełnić wybrańców dobierając im <math>i</math> mężczyzn i tyle samo kobiet,
-dla <math>\displaystyle i\in\left\lbrace 0,\ldots,n-1 \right\rbrace</math>.
+dla <math>i\in\left\lbrace 0,\ldots,n-1 \right\rbrace</math>.
-Z początkowej naszej refleksji możemy to zrobić na <math>\displaystyle {2n-2\choose n-1}</math> sposobów.
+Z początkowej naszej refleksji możemy to zrobić na <math>{2n-2\choose n-1}</math> sposobów.
-Podsumowując, interesującego nas wyboru możemy dokonać na <math>\displaystyle n^2{2n-2\choose n-1}</math>,
+Podsumowując, interesującego nas wyboru możemy dokonać na <math>n^2{2n-2\choose n-1}</math>,
 co było do pokazania.
 </div></div>
-<div class="thumb tright"><div style="width:250px;">
+[[File:SW 8.CW1.svg|250x250px|thumb|right|SW 8.CW1.swf]]
-<flash>file=SW 8.CW1.swf|width=250|height=250</flash>
-<div.thumbcaption>SW 8.CW1.swf</div></div>
-</div>
 {{cwiczenie|6|cw 6|
-Ile prostokątów zawiera się w kratce <math>\displaystyle n\times n</math>?
+Ile prostokątów zawiera się w kratce <math>n\times n</math>?
-Dla przykładu w kratce <math>\displaystyle 2\times2</math> jest ich <math>\displaystyle 9</math>.
+Dla przykładu w kratce <math>2\times2</math> jest ich <math>9</math>.
 }}
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
-Rozważ ile prostokątów w kratce <math>\displaystyle n\times n</math> zawiera się w górnej lewej podkratce
+Rozważ ile prostokątów w kratce <math>n\times n</math> zawiera się w górnej lewej podkratce
-<math>\displaystyle m\times m</math> (dla <math>\displaystyle m<n</math>),
+<math>m\times m</math> (dla <math>m<n</math>),
-ale nie zawiera się w górnej lewej podkratce <math>\displaystyle (m-1)\times(m-1)</math>.
+ale nie zawiera się w górnej lewej podkratce <math>(m-1)\times(m-1)</math>.
 </div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-<div class="thumb tleft"><div style="width:250px;">
+[[File:SW 8.CW2.svg|250x250px|thumb|left|SW 8.CW2.swf]]
-<flash>file=SW 8.CW2.swf|width=250|height=250</flash>
-<div.thumbcaption>SW 8.CW2.swf</div></div>
-</div>
-<div class="thumb tright"><div style="width:250px;">
+[[File:SW 8.CW3.svg|250x250px|thumb|right|SW 8.CW3.swf]]
-<flash>file=SW 8.CW3.swf|width=250|height=250</flash>
-<div.thumbcaption>SW 8.CW3.swf</div></div>
-</div>
-Policzmy ile prostokątów w kratce <math>\displaystyle n\times n</math> położonych jest w lewej górnej podkratce
+Policzmy ile prostokątów w kratce <math>n\times n</math> położonych jest w lewej górnej podkratce
-<math>\displaystyle m\times m</math> i przylega do chociaż jednej z wewnętrznych (czyli dolnej bądź prawej)
+<math>m\times m</math> 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 <math>\displaystyle n=5</math> i <math>\displaystyle m=4</math>:
+Kilka przykładów takich prostokątów przedstawiamy poniżej dla <math>n=5</math> i <math>m=4</math>:
-Prostokąt przylegający do prawej pionowej krawędzi podkratki <math>\displaystyle m\times m</math> i nieprzylegający do dolnej poziomej krawędzi jest jednoznacznie wyznaczony przez wybór <math>\displaystyle 1</math> pionowej krawędzi spośród <math>\displaystyle m</math> i dwu poziomych krawędzi spośród <math>\displaystyle m</math>.
+Prostokąt przylegający do prawej pionowej krawędzi podkratki <math>m\times m</math> i nieprzylegający do dolnej poziomej krawędzi jest jednoznacznie wyznaczony przez wybór <math>1</math> pionowej krawędzi spośród <math>m</math> i dwu poziomych krawędzi spośród <math>m</math>.
-Zatem jest dokładnie <math>\displaystyle {m\choose 1}{m\choose 2}=\frac{m^2(m-1)}{2}</math> takich prostokątów. Analogicznie jest <math>\displaystyle \frac{m^2(m-1)}{2}</math> prostokątów przylegających do dolnej krawędzi podkratki <math>\displaystyle m\times m</math> i nieprzylegających do prawej. W końcu jest dokładnie <math>\displaystyle m^2</math> prostokątów leżących w prawym dolnym narożniku podkratki <math>\displaystyle m\times m</math>, gdyż są one jednoznacznie wyznaczone przez wybór <math>\displaystyle 1</math> poziomej linii spośród <math>\displaystyle m</math> i <math>\displaystyle 1</math> pionowej linii spośród <math>\displaystyle m</math>.
+Zatem jest dokładnie <math>{m\choose 1}{m\choose 2}=\frac{m^2(m-1)}{2}</math> takich prostokątów. Analogicznie jest <math>\frac{m^2(m-1)}{2}</math> prostokątów przylegających do dolnej krawędzi podkratki <math>m\times m</math> i nieprzylegających do prawej. W końcu jest dokładnie <math>m^2</math> prostokątów leżących w prawym dolnym narożniku podkratki <math>m\times m</math>, gdyż są one jednoznacznie wyznaczone przez wybór <math>1</math> poziomej linii spośród <math>m</math> i <math>1</math> pionowej linii spośród <math>m</math>.
 Zatem w sumie jest
@@ Linia 207: / Linia 193: @@
 <center>
-<math>\displaystyle \frac{m^2(m-1)}{2}+\frac{m^2(m-1)}{2}+m^2=m^3,
+<math>\frac{m^2(m-1)}{2}+\frac{m^2(m-1)}{2}+m^2=m^3</math>,
-</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
+prostokątów w podkratce <math>m\times m</math> przylegających do chociaż jednej wewnętrznej krawędzi. Sumując po <math>m\in\left\lbrace 1,\ldots,n \right\rbrace</math> otrzymujemy liczbę wszystkich prostokątów w kratce <math>n\times n</math>, czyli jest ich
 <center>
-<math>\displaystyle 1^3+2^3+\ldots+n^3 = \left( \frac{n(n+1)}{2} \right)^2.
+<math>1^3+2^3+\ldots+n^3 = \left( \frac{n(n+1)}{2} \right)^2</math>
-</math>
 </center>
@@ Linia 228: / Linia 212: @@
 <center>
-<math>\displaystyle (-4)^n{-\frac{1}{2}\choose n}={2n\choose n}.
+<math>(-4)^n{-\frac{1}{2}\choose n}={2n\choose n}</math>
-</math>
 </center>
@@ Linia 240: / Linia 223: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-Dowód przez indukcję względem <math>\displaystyle n</math>.
+Dowód przez indukcję względem <math>n</math>.
-Dla <math>\displaystyle n=1</math> mamy
+Dla <math>n=1</math> mamy
 <center>
-<math>\displaystyle (-4)^1{-\frac{1}{2}\choose 1}=(-4)\frac{-\frac{1}{2}}{1}=2={2\choose 1}.
+<math>(-4)^1{-\frac{1}{2}\choose 1}=(-4)\frac{-\frac{1}{2}}{1}=2={2\choose 1}</math>
-</math>
 </center>
@@ Linia 254: / Linia 236: @@
 <center>
-<math>\displaystyle \begin{align} {2(n+1)\choose n+1}
+<math>\begin{align} {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}\\
@@ Linia 270: / Linia 252: @@
 <center>
-<math>\displaystyle f_{n+1}=\sum_{k=0}^{n}{n-k\choose k}
+<math>f_{n+1}=\sum_{k=0}^{n}{n-k\choose k}
 </math>
 </center>
-gdzie <math>\displaystyle f_n</math> jest <math>\displaystyle n</math>-tą liczbą Fibonacci'ego
+gdzie <math>f_n</math> jest <math>n</math>-tą liczbą Fibonacci'ego
 }}
@@ Linia 285: / Linia 267: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-<div class="thumb tright"><div style="width:250px;">
+[[File:SW 8.CW4.svg|250x250px|thumb|right|SW 8.CW4.swf]]
-<flash>file=SW 8.CW4.swf|width=250|height=250</flash>
-<div.thumbcaption>SW 8.CW4.swf</div></div>
-</div>
-Dowód indukcyjny względem <math>\displaystyle n</math>. Dla <math>\displaystyle n=0</math> i <math>\displaystyle n=1</math> mamy odpowiednio
+Dowód indukcyjny względem <math>n</math>. Dla <math>n=0</math> i <math>n=1</math> mamy odpowiednio
-<math>\displaystyle f_1=1= {0\choose0}=1</math>  i <math>\displaystyle f_2=1=1+0={1\choose0}+{0\choose1}</math>.
+<math>f_1=1= {0\choose0}=1</math>  i <math>f_2=1=1+0={1\choose0}+{0\choose1}</math>.
 Ponadto:
 <center>
-<math>\displaystyle \begin{align} f_{n+2}&=f_n+f_{n+1}\\
+<math>\begin{align} 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)\\