Fiszki – Kombinatoryka

Kiedy można po prostu dodać liczby możliwości?

Gdy liczone grupy są rozłączne i razem obejmują wszystkie dopuszczalne wyniki.

Co zrobić, gdy grupy mają wspólne elementy?

Po dodaniu liczebności dwóch grup odejmij raz liczebność ich części wspólnej, aby każdy wynik liczyć tylko raz.

Liczebność sumy dwóch zbiorów

\(|A\cup B|=|A|+|B|-|A\cap B|\).

Znaczenie symbolu rozłączności

\(A\cap B=\varnothing\): zbiory nie mają wspólnych elementów.

Co oznaczają czynniki w regule mnożenia?

Liczby możliwości na kolejnych etapach tworzenia pełnego wyniku. Na danym etapie liczba kontynuacji musi być taka sama dla każdego wcześniejszego dopuszczalnego wyboru.

Czy reguła mnożenia działa bez powtórzeń?

Tak. Na przykład wybór dwóch różnych osób do różnych ról z pięciu daje \(5\cdot4=20\), bo po pierwszym wyborze zawsze pozostają cztery osoby.

Kod długości k z n znaków z powtórzeniami

\(n^k\), jeśli każdy znak wolno użyć na każdej pozycji.

Nierówne liczby kontynuacji

Rozdziel rozłączne przypadki, policz każdy i dodaj wyniki.

Jak uniknąć podwójnego liczenia?

Ustal, kiedy dwa opisy oznaczają ten sam wynik, i stosuj rozłączne przypadki lub korektę części wspólnej.

Na czym polega liczenie przez dopełnienie?

Liczymy wszystkie wyniki, a następnie odejmujemy te, które nie spełniają warunku.

Co najmniej jedno zero w kodzie

Wszystkie kody minus kody bez zera.

Kontrola wyniku z ograniczeniami

Nie może być większy niż liczba wszystkich wyników bez ograniczeń.

Co oznacza silnia?

Dla dodatniego całkowitego n jest iloczynem kolejnych liczb od 1 do n. Przyjmujemy również \(0!=1\).

Dlaczego dzielimy przez silnie liczności powtarzających się liter?

Zamiany jednakowych liter nie zmieniają widocznego napisu. Dzielenie usuwa wielokrotne policzenie tych samych ustawień.

Permutacje n różnych elementów

\(n!\).

Permutacje z powtórzeniami

\(\frac{n!}{n_1!\cdots n_k!}\), gdzie \(n_1+\cdots+n_k=n\).

Czym wariacja różni się od kombinacji?

W wariacji kolejność lub role zmieniają wynik, a w kombinacji liczy się tylko skład grupy.

Czy wariacja musi wybierać mniej elementów, niż jest dostępnych?

Nie. Bez powtórzeń można wybrać także wszystkie; wtedy wariacja jest permutacją. Z powtórzeniami liczba pozycji może przekraczać liczbę dostępnych elementów.

Wariacje bez powtórzeń

\(V_n^k=\frac{n!}{(n-k)!}\), przy \(0\leq k\leq n\).

Wariacje z powtórzeniami

\(n^k\).

Dlaczego w kombinacjach dzielimy przez k silnia?

Każdą grupę k różnych elementów można ustawić na \(k!\) sposobów. Przy wyborze bez kolejności te ustawienia są jednym wynikiem.

Kiedy nie wolno liczyć komisji zwykłą kombinacją?

Gdy wybranym osobom przydzielamy różne role. Wtedy sam skład nie opisuje pełnego wyniku.

Liczba kombinacji

\(\binom nk=\frac{n!}{k!(n-k)!}\).

Symetria kombinacji

\(\binom nk=\binom n{n-k}\).

Co liczymy w pełnym drzewku możliwości?

Końcowe ścieżki lub równoważnie liście, ponieważ każdy z nich opisuje jeden pełny wynik.

Czy zawsze można pomnożyć liczby gałęzi z kolejnych poziomów?

Tylko gdy na każdym etapie liczba kontynuacji jest stała. W nieregularnym drzewku trzeba policzyć oddzielne przypadki.

Dwa kolejne rzuty monetą

Cztery ścieżki: OO, OR, RO, RR.

Dokładnie jeden orzeł w dwóch rzutach

Dwie ścieżki: OR i RO.

Dlaczego zero na początku wymaga osobnej uwagi?

W zapisie liczby nie tworzy dodatkowej pozycji znaczącej. Liczba wielocyfrowa musi zaczynać się cyfrą niezerową.

Dlaczego często zaczynamy wybór od ostatniej cyfry?

Ostatnia cyfra rozstrzyga parzystość lub podzielność przez pięć, więc jej wybór od razu uwzględnia główne ograniczenie.

Podzielność przez pięć

Ostatnia cyfra to 0 lub 5.

Podzielność przez trzy

Suma cyfr jest podzielna przez trzy.

Dlaczego przy parze stojącej razem trzeba mnożyć przez dwa?

Blok dwóch różnych osób może mieć kolejność AB albo BA. Każde ustawienie bloku daje dwie różne kolejności osób.

Jak liczyć ustawienia przy okrągłym stole?

Jeśli obroty uznajemy za te same ustawienia, ustalamy jedną osobę i ustawiamy pozostałe na \((n-1)!\) sposobów. Przy ponumerowanych miejscach ta reguła nie obowiązuje.

Dwie wskazane osoby obok siebie w szeregu

\(2!(n-1)!\) dla n różnych osób.

Dwie wskazane osoby nie obok siebie

\(n!-2!(n-1)!\) dla n różnych osób w szeregu.

Od czego zacząć zadanie kombinatoryczne?

Opisz jeden pełny wynik, sprawdź znaczenie kolejności, dopuszczenie powtórzeń i wszystkie ograniczenia.

Jak rozumieć co najmniej jeden element danego rodzaju?

Dopuszczamy jeden, dwa i więcej takich elementów. Często najłatwiej odjąć od wszystkich wyników te bez ani jednego.

Grupa bez przydzielonych ról

Kolejność wyboru nie tworzy nowego wyniku.

Rozłączne przypadki i kolejne etapy

Przypadki dodajemy; stałe liczby możliwości kolejnych etapów mnożymy.