Kombinatoryka - matura-rozszerzona - Baza Wiedzy

Kombinatoryka

W zadaniach z rachunku prawdopodobieństwa często zdarza się, że musimy policzyć ilość przypadków, w jakich może występować zdarzenie. Służy do tego kombinatoryka - w tym rozdziale omówimy podstawowe jej pojęcia, takie jak permutacja, kombinacja, wariacja i wariacja z powtórzeniem.
 

Permutacje

Załóżmy, że mamy ciąg $$n$$ liczb, od $$0$$ do $$n-1$$. Chcielibyśmy wiedzieć, na ile sposobów da się postawić te liczby w ciągu, czyli poznać liczbę wszystkich jego permutacji.

Zauważmy, że pierwszy element możemy wybrać na $$n$$ sposobów. Drugi element: na $$n-1$$, trzeci: na $$n-2$$ i tak dalej. Wymnażając wszystkie te liczby otrzymujemy iloczyn $$1×2×3×4×...×(n-1)×n$$, który oznacza się symbolem $$n!$$ i nazywamy "silnią". Warto wspomnieć, że możemy ją także zdefiniować rekurencyjnie, jako ciąg $$n! = (n-1)!×n$$ i $$0! = 1$$.
 

Kombinacje (bez powtórzeń)

Zacznijmy od pytania: na ile sposobów jesteśmy w stanie wybrać trzy piłki ze zbioru 10 ponumerowanych piłek?

Pierwszą możemy wybrać na 10 sposobów. Drugą - na 9, trzecią na 8. Wydawałoby się, że odpowiedzią będzie więc $$10×9×8$$. Jednak sytuację, kiedy wybraliśmy piłki o numerach 0, 1 i 2 policzyliśmy kilka razy - na przykład w kolejności 0,1,2 i 0,2,1. Musimy więc podzielić otrzymaną liczbę przez ilość permutacji wybranego zbioru, czyli przez $$3! = 1×2×3 = 6$$. Ostatecznie dostajemy $${8×9×10}/{3!}$$.

Jednak jeśli zamiast 10 piłek mielibyśmy ich 1000, a zamiast wybierać 3 kazanoby nam wybrać 100, zapisanie tego w postaci takiego ułamka byłoby dość czasochłonne. Możemy jednak zauważyć, że zamiast pisać $$1000×(1000-1)×(1000-2)×...×(1000-99)$$, możemy po prostu napisać $${1000!}/{(1000-100)!}$$.

W ogólności wzór na ilość kombinacji będzie więc wyglądał tak:

$${n!}/{(n-k)!} × {1}/{k!} = {n!}/{(n-k)!k!}$$

Aby jeszcze bardziej uprościć zapis, taki ułamek będziemy oznaczali jako $$( able n;k)$$.
 

Kombinacje (z powtórzeniami)

Teraz czas na pytanie innego rodzaju: na ile sposobów jesteśmy w stanie wybrać dwie piłki spośród czterech, przy czym po wybraniu pierwszej wrzucamy ją spowrotem do worka?

Rozpisując wszystkie kombinacje można się przekonać, że isnieje ich dokładnie 10 - do "standardowych", które policzylibyśmy korzystając z poprzedniego podpunktu $$( able 4;2) = 6$$ należy dodać jeszcze cztery zawierające dwa takie same elementy: $$(0,0), (1,1), (2,2)$$ i $$(3,3)$$.

Jednak takie podejście nie zadziała w ogólności, ponieważ przy wybieraniu większej ilości piłek możemy mieć kombinacje składające się na przykład z trzech takich samych i dwóch innych.

Rozwiązanie zadania opiera się na pomyśle, aby każdej kombinacji przyporządkować pewien ciąg zer i jedynek. Liczba zer w ciągu będzie wynosiła $$n-1$$, jedynek - $$k$$.

Ciąg przyporządkowywujemy w ten sposób, że każda jedynka odpowiada elementowi o numerze równym ilości zer przed jedynką. Inaczej mówiąc: jeśli przed trzecią jedynką jest na przykład 5 zer, to znaczy to, że w kombinacji znajduje się piątka. Jako że ilość sposobów rozmieszczenia k jedynek na n+k-1 miejscach wynosi $$(n+k-1 choose k)$$, a każdy taki sposób odpowiada jednej kombinacji z powtórzeniami, to właśnie tyle jest kombinacji z powtórzeniami.

Przykład:

Załóżmy że $$n=5, k=3$$. Wtedy kombinacji $$(1,2,3)$$ odpowiada ciąg $$(0,1,0,1,0,1,0)$$. Kombinacji $$(0,2,2)$$ odpowiada zaś ciąg $$(1,0,0,1,1,0,0)$$.
 

Wariacje

Wariacje, w odróżnieniu od kombinacji, są ciągami, a nie zbiorami. Oznacza to, że kolejność ma w nich znaczenie: jedyną zmianą, jaką w takim razie wprowadzamy we wzorze jest usunięcie składnika $$k!$$. Ilość wariacji bez powtórzeń jest więc równa:
$${n!}/{(n-k)!}$$

zaś z powtórzeniami:
$$n^k$$, ponieważ na pierwsze miejsce można każdy z $$n$$ elementów, na drugi - także, itd.

Spis treści

Rozwiązane zadania
Oblicz objętość graniastosłupa prawidłowego...

a) Obliczmy pole trójkąta równobocznego:

`P_p = (3^2sqrt3)/4 = (9sqrt3)/4` 

 

Pomnóżmy przez wysokość:

`V = P_p * H = (9sqrt3)/4 * 5 = (45sqrt3)/4` 

 

b) Obliczmy pole podstawy:

`P_p = 4*6 = 24` 

 

Pomnóżmy przez wysokość:

`V = P_p * H = 24*4 = 96`  

 

c) W podstawie mamy sześciokąt foremny, jest złożony z sześciu trójkątów równobocznych, zatem pole podtawy to:

`P_p = 6P = 6*(4^2sqrt3)/4 = 6*4sqrt3 = 24sqrt3` 

 

Pomnóżmy przez wysokość:

`V = P_p * H = 24sqrt3 * 5 = 120 sqrt3` 

Wykres funkcji liniowej jest nachylony

`tgalpha=-sqrt3\ \ \ =>\ \ \ -tgalpha=sqrt3\ \ \ =>\ \ \ tg(180^o-alpha)=sqrt3\ \ \ =>\ \ \ 180^o-alpha=60^o\ \ \ =>\ \ \ alpha=180^o-60^o=120^o`

 

`odp.\ C`

Zbiory A, B i C są skończone

`a)` 

Jeżeli iloczyn zbiorów jest zbiorem pustym, to te zbiory nie mają żadnych wspólnych elementów. Oznacza to, że żaden element zbioru A nie będzie znajdował się w zbiorze B oraz żaden element zbioru B nie będzie znajdował się w zbiorze A. Sumując elementy zbiorów A i B, każdy element będzie liczony tylko raz (bo iloczyn jest zbiorem pustym), więc liczba elementów sumy zbiorów A i B jest równie sumie liczby elementów zbioru A i liczby elementów zbioru B. 

 

 

`b)` 

Jeśli zbiory A i B mają iloczyn różny od zbioru pustego, to dodając liczbę elementów zbioru A i liczbę elementów zbioru B elementy należące do obu zbiorów są liczone podwójnie (raz są liczone jako elementy zbioru A, a raz jako elementy zbioru B). Dlatego musimy odjąć liczbę elementów należących do iloczynu zbiorów A i B. 

Możemy rozwiązać to zadanie na diagramie. Będziemy oznaczać plusami i minusami. 

Krok po kroku rozpiszemy prawą stronę równości:

`overline(overline(A))+overline(overline(B))-overline(overline(AnnB))` 

 

Zaznaczmy plusy w tych częściach diagramu, które wchodzą w skład zbioru A. 

Następnie zaznaczmy plusy w tych częściach diagramu, które wchodzą w sklad zbioru B. 

Następnie mamy odjąć te części, które należą do iloczynu zbiorów A i B, zaznaczmy więc minus w odpowiednim miejscu. 

Ostatecznie, każda część diagramu została policzona tylko raz (plus z minusem dają zero, w środkowej części mamy 2 plusy i 1 minus, czyli 1 plus), więc otrzymaliśmy sumę zbiorów A i B. 

Równość jest prawdziwa. 

 

`ul("uwaga")` 

Zauważmy, że korzystając z tego podpunktu łatwo można uzasadnić podpunkt a). Jeśli iloczyn zbiorów A i B jest zbiorem pustym, to liczba elementów tego iloczynu wynosi zero, więc wtedy:

`overline(overline(AuuB))=overline(overline(A))+overline(overline(B))-overline(overline(AnnB))=overline(overline(A))+overline(overline(B))-0=overline(overline(A))+overline(overline(B))` 

 

 

`c)` 

Podobnie jak poprzednio, rozwiążemy zadanie na diagramie. 

Krok po kroku rozpiszemy prawą stronę równości:

`overline(overline(A))+overline(overline(B))+overline(overline(C))-overline(overline(AnnB))-overline(overline(AnnC))-overline(overline(BnnC))+overline(overline(AnnBnnC))` 

 

Zaznaczmy plusy w tych częściach diagramu, które wchodzą w skład zbioru A. 

Następnie zaznaczmy plusy w tych częściach diagramu, które wchodzą w sklad zbioru B. 

Zaznaczmy plusy (na zielono) w tych częściach diagramu, które wchodzą w sklad zbioru C. 

Następnie mamy odjąć te części, które należą do iloczynu zbiorów A i B, zaznaczmy więc minusy (na czerwono) w odpowiednim miejscu. 

Następnie mamy odjąć te części, które należą do iloczynu zbiorów A i C, zaznaczmy więc minusy (na fioletowo) w odpowiednim miejscu. 

Następnie mamy odjąć te części, które należą do iloczynu zbiorów B i C, zaznaczmy więc minusy (na żółto) w odpowiednim miejscu. 

Na końcu należy dodać jeszcze część należącą do iloczynu zbiorów A, B i C. Zaznaczamy więc plus (na granatowo) w odpowiednim miejscu. 

Ostatecznie, każda część diagramu została policzona tylko raz (plus z minusem dają zero):

Otrzymaliśmy więc sumę zbiorów A, B i C. 

Równość jest prawdziwa. 

Wyznacz sumę wielomianów

`b)` 

`(5x^3-6x^2+2)+(2x^3+4x^2+5x-3)=ul(ul(ul(5x^3)))-ul(ul(6x^2))+ul(2)+ul(ul(ul(2x^3)))+ul(ul(4x^2))+5x-ul(3)=7x^3-2x^2+5x-1` 

 

`c)` 

`(-x^3+x^2-6x+8)+(4x^3+6x-7)=ul(ul(ul(-x^3)))+x^2-ul(ul(6x))+ul8+ul(ul(ul(4x^3)))+ul(ul(6x))-ul7=3x^3+x^2+1`    

Ciąg ...

`lim_(n->oo)a_n=lim_(n->oo)(bn-6)/((1-b)n+3)=lim_(n->oo)n/n*(b-6/n)/(1-b+3/n)=lim_(n->oo)(b-6/n)/(1-b+3/n)`  

`"Dla b=1:"` 

`lim_(n->oo)(b-6/n)/(1-b+3/n)=lim_(n->oo)(1-6/n)/(3/n)=oo`   

`"Licznik dąży do 1, natomiast mianownik dąży do zera. Tym samym całe wyrażenie dąży do nieskończoności."` 

 

`"Odpowiedź C."`   

  

a) Dany jest prostokąt o bokach długości

`a)`

`x*y=20\ \ \ =>\ \ \ y=20/x`

Obliczmy współrzędne kilku punktów należących do wykresu tej funkcji:

`x=2\ \ \ =>\ \ \ y=20/2=10\ \ \ =>\ \ \ (2,\ 10)`

`x=4\ \ \ =>\ \ \ y=20/4=5\ \ \ =>\ \ \ (4,\ 5)`

`x=5\ \ \ =>\ \ \ y=20/5=4\ \ \ =>\ \ \ (5,\ 4)`

`x=8\ \ \ =>\ \ \ y=20/8=5/2=2 1/2\ \ \ =>\ \ \ (8,\ 2 1/2)`

`x=10\ \ \ =>\ \ \ y=20/10=2\ \ \ =>\ \ \ (10,\ 2)`

 

  

 

 

 

`b)`

`1/2*x*y=9\ \ \ |*2`

`xy=18`

`y=18/x`

 

Obliczamy współrzędne paru punktów należących do wykresu: 

`x=2\ \ \ =>\ \ \ y=18/2=9\ \ \ =>\ \ \ (2,\ 9)`

`x=3\ \ \ =>\ \ \ y=18/3=6\ \ \ =>\ \ \ (3,\ 6)`

`x=4\ \ \ =>\ \ \ y=18/4=9/2=4 1/2\ \ \ =>\ \ \ (4,\ 4 1/2)`

`x=6\ \ \ =>\ \ \ y=18/6=3\ \ \ =>\ \ \ (6,\ 3)`

`x=9\ \ \ =>\ \ \ y=18/9=2\ \ \ =>\ \ \ (9,\ 2)`

 

Dany jest wielomian

`"założenia:"\ \ \ w(x)=ax^3+bx^2+cx+d\ \ \ (a,\ b,\ c,\ d in C)`

`\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ w(0),\ w(1)\ - \ "liczby nieparzyste"`

`"teza:"\ "wielomian"\ w\ "nie ma pierwiastków całkowitych"`

`"dowód:"`

`w(0)=a*0^3+b*0^2+c*0+d=a*0+b*0+c*0+d=d\ \ -\ \ "liczba nieparzysta"`

`w(1)=a*1^3+b*1^2+c*1+d=a+b+c+d\ \ \ -\ \ \ "liczba nieparzysta"`

 

Przypuśćmy, że wielomian w ma jednak pewien pierwiastek całkowity. Jeśli taki pierwiastek istnieje, to musi być on dzielnikiem wyrazu wolnego, czyli dzielnikiem liczby nieparzystej d. Wszystkie dzielniki liczby nieparzystej także są nieparzyste, a więc pierwiastek wielomianu w jest liczbą nieparzystą. Oznaczmy zatem ten pierwiastek jako 2k+1 (k - liczba całkowita).

Jeśli 2k+1 jest pierwiastkiem wielomianu, to wartość w(2k+1) powinna być równa 0. Sprawdźmy, czy rzeczywiście tak jest (skorzystamy ze wzorów skróconego mnożenia na sześcian sumy oraz kwadrat sumy).

`w(2k+1)=a*(2k+1)^3+b*(2k+1)^2+c*(2k+1)+d=`

`\ \ \ \ \ \ \ \ \ \ \ \ \ \ =a*((2k)^3+3*(2k)^2*1+3*2k*1^2+1^3)+b*((2k)^2+2*2k*1+1^2)+c*(2k+1)+d=`

`\ \ \ \ \ \ \ \ \ \ \ \ \ \ =a(8k^3+12k^2+6k+1)+b(4k^2+4k+1)+c(2k+1)+d=`

Uporządkujmy wielomian ze względu na k:

`\ \ \ \ \ \ \ \ \ \ \ \ \ \ =8ak^3+(12a+4b)k+(6a+4b+2c)k+(a+b+c+d)=`

`\ \ \ \ \ \ \ \ \ \ \ \ \ \ =ul(2*4ak^3+2*(6a+2b)k+2*(3a+2b+c)k)+(a+b+c+d)=`

Z podkreślonego wyrażenia wyciągamy 2 przed nawias: 

`\ \ \ \ \ \ \ \ \ \ \ \ \ \ =#underbrace(#underbrace(2(4ak^3+(6a+2b)k+(3a+2b+c)k))_("liczba parzysta")+#underbrace((a+b+c+d))_("liczba nieparzysta"))_("liczba nieparzysta")`

Z założenia wiemy, że a+b+c+d jest liczbą nieparzystą, suma liczby parzystej i nieparzystej jest liczbą nieparzystą. Otrzymaliśmy więc, że wartość w(2k+1) jest liczbą nieparzystą, co jest sprzecznością (bo przecież ta wartość miała być równa 0, a liczba 0 jest przecież parzysta).      

Wyznacz zbiory

`a)`

`AuuB=(1,\ 6)`

`AnnB=(2,\ 4)`

`A\\B=(1,\ 2>>`

`B\\A=<<4,\ 6)`

 

 

 

`b)`

`AuuB=<<-4,\ 3)`

`AnnB={1}`

`A\\B=<<-4,\ 1)`

`B\\A=(1,\ 3)`

 

 

`c)`

 

`AuuB=<<-5,\ 3>>`

`AnnB=<<1,\ 3>>`

`A\\B=emptyset`

`B\\A=<<-5,\ 1)`

 

 

`d)`

`AuuB=(-3,\ 2>>`

`AnnB=(-1,\ 2>>`

`A\\B=(-3,\ -1>>`

`B\\A=emptyset`

Kąt między ramionami trójkąta równoramiennego...

Rysunek:

`tg \ 60^o = b/h` 

`hsqrt3 = b` 

`h = b/sqrt3 * sqrt3/sqrt3 = (sqrt3b)/3` 

 

`sin60^o = b/a` 

`sqrt3/2 = b/a` 

`a = (2b)/sqrt3 * sqrt3/sqrt3 = (2sqrt3b)/3` 

 

Największa ściana boczna to prostokąt o bokach 2b, 2a. Jego pole to:

`P= 2a*2b = 4ab = 4*(2sqrt3b)/3 * b = (8sqrt3b^2)/3` 

 

Pole podstawy to:

`P_p = 1/2*2b*h = b * (sqrt3b)/3 = (sqrt3b^2)/3` 

 

Stosunek pola największej ściany bocznej do pola podstawy:

`(P)/(P_p) = ((8sqrt3b^2)/3)/((sqrt3b^2)/3) = (8sqrt3b^2)/3 *3/(sqrt3b^2) = 8` 

Narysuj obraz trójkąta ABC ...

`a)` 

`alpha=90^o` 

`A-"środek obrotu"` 

 

`b)` 

`alpha=90^o` 

`O-"środek obrotu"` 

`c)` 

`alpha=180^o` 

`D-"środek obrotu"`