Kombinacje

Wprowadzenie do kombinacji

W poprzednim filmie obliczyliśmy na ile różnych sposobów można

rozmieścić 5 osób po 3 krzesłach.

Na przykład, jeżeli to jest krzesło pierwsze,

to jest drugie i to jest trzecie.

W pierwszym krześle możemy usadzić jedną z 5 osób.

Wiemy, że nikt nie zajmuje jeszcze żadnego miejsca.

Po pierwszym wyborze możemy posadzić

już tylko jedną z 4 różnych osób na krześle drugim.

Dalej zostają nam tylko 3 osoby,

które możemy umieścić w krześle trzecim.

Całkowita liczba permutacji na które ludzie

mogą rozsiąść po różnych miejscach

-- jeżeli dbamy o kolejność siedzenia na krzesłach --

będzie równa 5 * 4 * 3.

Można też popatrzyć na to jako -- 5 * 4 * 3

-- to jest to samo co:

5 * 4 * 3 * 2 * 1 podzielone przez

2 * 1.

To samo co 5 silnia nad 2 silnia.

Teraz, skąd wzięło się to 2?

Jak 2 jest związane z 5 i 3?

Cóż, jest różnica tych dwóch liczb.

To jest to samo co 5 silnia

nad (5 - 3) silnia.

W ten sposób obliczamy jak wiele jest permutacji,

gdzie 5 rzeczy chcemy rozmieścić

po 3 miejscach.

To jest ogólny wzór, o którym dowiedzieliśmy się

w poprzednim filmie.

Zmienię kolory.

Jeżeli chcemy rozmieścić n rzeczy po k miejscach,

k musi być mniejsze lub równe n.

Tak naprawdę nie musi.

Na nasze potrzeby zróbmy takie założenie,

ponieważ bez takiego założenia moglibyśmy mieć problemy z naszym wzorem.

I to jest równe n silnia nad (n - k) silnia.

Zawsze zamiast zapamiętać ten wzór wolę go

wyprowadzić sobie go na miejscu.

Zawsze jest mi łatwiej dojść do tego na logikę,

5 osób/rzeczy mogłoby się znaleźć tutaj.

Jeżeli jedna jest tutaj zaklepana to zostają 4 możliwości

i po zajęciu kolejnego miejsca 3 możliwości na obsadzenie następnego.

Staram się myśleć o tym jako o braniu pierwszych k czynników

z n silnia.

W tym przypadku biorę pierwsze 3 wyrazy

z 5 silnia.

5 * 4 * 3.

W ten właśnie sposób myślę o permutacjach.

To działa wspaniale dopóki dbamy -- powiedzmy że mamy te osoby

A, B, C, D, E.

Te 5 osób ma się rozsiąść po krzesłach.

Permutacje działają świetnie dopóki chcemy liczyć permutację ABC

jako inną od ACB

inną od BAC

i inną od permutacji BCA.

Gdy liczyliśmy permutacje to interesowało nas

gdzie wybrane osoby będą siedzieć.

W poprzednim filmie liczyliśmy wszystko wielokrotnie, ponieważ ważne było

czy osoba A zajmie 1 miejsce,

a osoba B zajmie 2 miejsce.

Jeżeli zamienią się miejscami to musimy dodać nową permutację, prawda?

Tutaj na przykład się zamieniają.

Co jeżeli nas to nie interesuje?

Co jeżeli nie dbamy o to, kto siedzi na którym miejscu?

Chcemy po prostu wiedzieć na ile różnych sposobów

możemy wybrać 5 osób do siedzenia?

W zasadzie chcemy więc policzyć wszystkie sytuacje, gdy A, B i C

siedzą razem jako jedną sytuację.

Nie interesuje nas, kto zajmuje które krzesło.

Interesuje nas jedynie, że właśnie te 3 osoby w tym momencie siedzą.

Spośród wszystkich osób stanowią one podzbiór osób siedzących.

Tak więc pytaniem przestaje być: jak wiele jest różnych

permutacji lub na ile różnych sposobów możemy rozsadzić ludzi?

Pytaniem staje się: ile różnych 3-elementowych zbiorów

jesteśmy w stanie utworzyć ze zbioru 5-elementowego?

Być może przeskoczymy trochę,

ale to jest właśnie definicja kombinacji.

Kombinacja jest to permutacja,

w której nie obchodzi nas kolejność.

Jak obliczyć coś takiego?

Gdy obliczaliśmy permutacje korzystając z tego wzoru

liczyliśmy ABC, ACB, BAC,

BCA i popatrzmy...

Powinny znaleźć się jeszcze dwie permutacje.

CAB i CBA.

Liczyliśmy te 6 układów jako różne permutacje.

Ale w kombinacjach chcemy potraktować to wszystko

jako jedną kombinacje,

ponieważ nie dbamy o kolejność rozmieszczenia.

Dla każdej trójki różnych osób będzie 6 permutacji rozłożenia po siedzeniach,

które bierzemy pod uwagę,

gdy liczymy wszystkie możliwe permutacje.

Jeżeli chcemy znać liczbę kombinacji, musimy podzielić przez liczbę

sposóbów rozmieszczenia 3 osób po 3 krzesłach.

To jest zasadniczo to co tutaj zrobiliśmy.

Na ile różnych sposobów można porozmieszczać

3 osoby po 3 krzesłach?

Cóż, to jest kolejny problem oparty o permutacje.

Na pierwszym krześle możesz posadzić 3 osoby,

na drugim możesz posadzić 2 osoby,

a na ostatnim zostaje nam tylko jedna osoba.

To jest 3 silnia równa 6.

3 silnia równa 6.

Mam nadzieję, że nie namieszałem.

Gdy zajmowaliśmy się permutacjami

zliczaliśmy dodatkowo wszystkie możliwe układy w jakie wybrane osoby

mogą się rozsiąść po krzesłach.

Na ile różnych sposobów mogą się wybrani ludzie

porozmieszczać po krzesłach?

To będzie silnia z liczby miejsc,

ponieważ jeżeli mamy 3 osoby znajdujące się 3 miejscach

– albo dla odmiany 4 osoby w 4 miejscach.

Pierwsze miejsce mogą obsadzić 4 osoby,

drugie już 3, trzecie 2,

a na ostatnie zostaje już tylko 1.

Czyli silnia z liczby miejsc mówi nam ile

permutacji liczymy dodatkowo za każdym razem,

gdy mamy tych samych ludzi.

Coś podobnego do gry w "gorące krzesła" na tych samych krzesłach.

W celu obliczenia ilości kombinacji,

załóżmy, że mamy 5 osób.

Ile różnych 3-osobowych grup możemy posadzić na krzesłach?

I nie chcemy liczyć tych samych grup wielokrotnie.

Nie chcemy już liczyć wielokrotnie.

Nie wiem jakie słowo określa

policzenie czegoś 6 razy.

Odpowiada to wzorowi na permutację

podzielonemu przez wszystkie nadmiarowe zliczenia, których dokonaliśmy.

Dzielimy przez liczbę wszystkich możliwych sposobów

w jakie 3 osoby mogą rozsiąść się po 3 krzesłach.

I jest to 3 silnia.

Mam nadzieję, że jest to zrozumiałe.

Postaram się przerobić jeszcze kilka przykładów na następnych filmach.

I zdecydowanie zgłaszajcie się po nie,

jeżeli wydaje się to mylące.

Ogólnie, możemy się spytać:

na ile różnych sposobów możemy wybrać n rzeczy?

Lub jaka jest liczba kombinacji,

gdzie n rzeczy chcemy podzielić na zbiory r-elementowe, gdzie r jest mniejsze lub równe od n.

Będzie to równe liczbie wszystkich permutacji, które można stworzyć

poprzez porozmieszczanie n rzeczy po r miejscach, podzielonej przez r silnia.

Będziemy dzielić przez liczbę różnych sposobów na jakie r miejsc

może być między sobą przemieszanych,

ponieważ nie chcemy liczyć dodatkowo tych kombinacji.

Jeżeli więc wrócimy do tego wzoru --

mieliśmy wcześniej k, teraz zastąpiło je r.

Odpowiada to wzorowi na permutację

n silnia nad (n - r) silnia.

Podzielonemu przez r silnia.

To będzie równe -- pozwólcie, że to zapiszę.

Często zapisuje się to jako kombinacja r-elementowa zbioru n-elementowego (nCr).

Możemy to inaczej zapisać przy pomocy symbolu Newtona.

Zwanego również współczynnikiem wielomianowym.

Któremu również poświęcimy kilka filmów.

Ponieważ pojawia się również przy okazji wzorów

skróconego mnożenia dla różnych potęg wielomianów.

To jest równe n silnia

podzielone przez: r silnia razy (n - r) silnia.

Możesz to wykuć na pamięć --

szczególnie przydatne, jeżeli chcesz ten wzór wykorzystywać

szybko na testach.

Ważne jest jednak, by wiedzieć skąd bierze się ten wzór.

n silnia nad (n - r) silnia --

to jest wzór na permutacje.

Co oznacza ten wzór?

Oznacza tyle, że bierzemy pierwsze r

czynników z silni.

r największych czynników z n silnia.

Nic więcej nam nie mówi.

Kombinacje uzyskujemy poprzez podzielenie przez r silnia,

ponieważ chcemy podzielić przez wszystkie możliwe

sposoby rozlokowania się wybranych osób

po r krzesłach.

Lub rozmieszczenie piłek po r kubkach.

W tej sytuacji jeżeli chcemy wiedzieć ile różnych

3-osobowych grup da się wybrać spośród 5 osób,

to będzie 5 silnia przez 3 silnia

razy (5 - 3) silnia.

Odpowiada to 5 * 4 * 3 * 2 * 1 [czwórka pominięta na filmie]

3 silnia to po prostu 6.

Zajmiemy się tym za chwilę.

Podzielone przez 2 silnia --

2 * 1.

Zauważ, że to jest część wzięta z permutacji.

To wyrażenie pozbywa się po prostu dwóch najmniejszych czynników.

Zostaje nam 5 * 3.

Oj, tutaj powinno być jeszcze 4.

5 * 4 * 3, czyli liczba permutacji.

Teraz dzielimy to przez 6, ponieważ mamy 6 permutacji na każdą

3-elementową kombinację.

Może to być nieco mylące.

Niemniej jednak otrzymujemy 5 * 4 * 3 podzielone przez 6.

Ile to jest?

5 * 12 / 6, jest równe 5 * 2.

Mamy więc 10 możliwych sposobów, na stworzenie 3-elementowego zbioru

z grupy 5-elementowej grupy.

Do zobaczenia w następnym filmie.