Kombinatoryka i Liczenie: Matematyka Ile

Zasada mnożenia: reguła stojąca za każdym liczeniem

Praktycznie każda formuła na temat liczenia w matematyce opiera się na jednym pomysłu, który jest wielokrotnie stosowany: jeśli pierwszego wyboru można dokonać na a sposobów, a następnie drugiego, niezależnego wyboru na b sposobów, to cała sekwencja wyborów może nastąpić na a·b sposobów. Pięciodaniowe menu degustacyjne z 4 daniami przystępnymi, 3 zupami, 5 daniami głównymi, 2 deserami i 3 napojami ma 4·3·5·2·3 = 360 możliwych zamówień – nikt nie musi wypisywać 360 menu, aby to wiedzieć. Jest to zasada mnożenia, a silnia, permutacje i kombinacje są wszystkim skrótami do wielokrotnego stosowania jej bez prowadzenia księgowości.

Permutacje: kiedy kolejność ma znaczenie

Permutacja to uporządkowane ułożenie. Uporządkowanie wszystkich n różnych obiektów w szereg daje n możliwości dla pierwszej pozycji, n-1 dla drugiej (jedna została wykorzystana), n-2 dla trzeciej i tak dalej aż do 1 – iloczyn wynosi n silnia, oznaczaną jako n! Uporządkowanie tylko k z tych n obiektów przerywa iloczyn o k kroków wcześniej:

n! = n · (n-1) · (n-2) · … · 2 · 1        (0! = 1, by convention)

P(n,k) = n! / (n-k)!   — ordered arrangements of k items chosen from n

example: 3 medals awarded to 8 sprinters
P(8,3) = 8! / 5! = 8 · 7 · 6 = 336 possible podiums

Wybory: kiedy kolejność nie ma znaczenia

Wybór bez uwzględniania kolejności – to jest kombinacja, np. komitet, ręka z kart do pokera lub podzbiór. Każda grupa k elementów może być ułożona w k! różnych porządku, dlatego, jeśli policzymy uporządkowane układy P(n,k) i podzielimy przez k! powtórzonych liczeń, otrzymamy liczbę rozróżnialnych grup:

C(n,k) = P(n,k) / k! = n! / (k! · (n-k)!) – czyli "n po k" Przykład: ręka z pięciu kart z talii 52 kart. C(52,5) = 52! / (5! · 47!) = 2 598 960 możliwych rąk. C(n,k) nazywa się również współczynnikiem binomowym, ponieważ jest to dokładnie współczynnik wyrazu x^k przy rozwijaniu (1+x)^n – fakt znany jako twierdzenie Newtona o binome.

C(n,k) = P(n,k) / k! = n! / (k! · (n-k)!)   — read "n choose k"

example: a 5-card poker hand from a 52-card deck
C(52,5) = 52! / (5! · 47!) = 2,598,960 possible hands

Powtórzenia i zasada wędrownego gąszczu (pigeonhole principle)

Występują tu dwa ciągle pojawiające się rozszerzenia. Jeśli wybory mogą się powtarzać – np. 4-cyfrowy kod PIN lub kodony DNA składające się z 3 zasad z {A,C,G,T} – stosuje się bezpośrednio zasadę mnożenia bez dzielenia: n^k wszystkich sekwencji (10 000 kodów PIN, 4³ = 64 kodony). Jeśli zamiast tego rozdzielamy identyczne przedmioty do różnych pojemników (np. 10 identycznych naklejek wśród 4 dzieci), to liczba wynosi kombinację "gwiazdy i pręty" C(n+k-1, k-1), ponieważ w rzeczywistości wybieramy, gdzie umieścić k-1 separatorów spośród n+k-1 otworów.

Zasada wędrownego gąszczu (pigeonhole principle) jest ulubionym dowodem istnienia w kombinatoryce: jeśli umieszczamy więcej niż n elementów w n pojemnikach, to co najmniej jeden pojemnik zawiera dwie lub więcej elementów – nie potrzeba żadnej formuły, wystarczy porównanie sum. Brzmi to trywialnie i zaskakująco dobrze udowadnia głębokie rezultaty, od gwarantowania, że dwóch osób w Londynie ma wspólny zestaw daty urodzinowej i godziny, po ograniczanie algorytmów kompresji: nie można bezstratnie skompresować każdego możliwego pliku, ponieważ istnieje więcej plików wejściowych niż krótszych plików wyjściowych do ich mapowania.

Gdzie liczenie naprawdę ma znaczenie

Te wzory stanowią podstawę arytmetyczną prawdopodobieństwa (prawdopodobieństwo zwykle jest równe liczbie korzystnych przypadków podzielonej przez liczbę wszystkich przypadków), szacunków przestrzeni kluczy kryptograficznych, granic kolizji w haszach oraz analizy złożoności algorytmu, gdzie liczenie liczby możliwych wejść lub stanów określa, jak szybko może przebiegać przeszukiwanie siłowe. Symulacja na tej stronie pozwala zmieniać n i k i obserwować, jak liczba rośnie – silniejsze funkcje wyrostkowe rosną tak szybko, że C(60,30), problem związany z niewielkim komitetem, już przekracza liczbę atomów w ludzkim ciele.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Combinatorics & Counting i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.