Kombinatoryka

Kombinatoryka
Polecane artykuły
Procedura głosowania Permutacja Brzytwa Ockhama Koewolucja Złoty podział Prawa De Morgana Indukcja eliminacyjna Algorytm genetyczny Efekt domina

Dział matematyczny, który zajmuje się wyznaczaniem liczby elementów zbiorów skończonych, które są tworzone w określony sposób, np. zbiór kombinacji, permutacji, wariacji. Zajmuje się zliczaniem sposobów zajścia zdarzenia losowego.

Metody obliczania liczby wyników zdarzenia losowego

Liczbę możliwych wyników doświadczenia losowego można obliczać różnymi sposobami, między innymi:

• poprzez wypisanie wszystkich możliwości
• przy pomocy tabeli
• za pomocą grafu (drzewka)
• stosując reguły dodawania i mnożenia

Zasady stosowane w kombinatoryce

Podstawowa zasada kombinatoryki Podejmując kilka niezależnych decyzji częściowych, dotyczących jednego całościowego wyboru mnożymy liczby decyzji, jeśli jednak dokonujemy wyborów wykluczających się, to liczby wyborów należy dodać.

Reguła dodawania Jeśli mamy wybrać pewien element z dwóch zbiorów A i B, zbiór A ma m elementów, a zbiór B ma n elementów, wyboru można dokonać na dokładnie m+n sposobów, przy czym zbiory te nie mają wspólnych elementów - wykluczają się. Reguła mnożenia Jeśli pierwsza czynność może zakończyć się na jeden z m sposobów, a druga na jeden z n sposobów to liczba wszystkich możliwych wyników doświadczenia, które polega na wykonaniu po kolei dwóch czynności jest równa m⋅n. W ten sam sposób postępujemy w przypadku doświadczenie, które polega na wykonaniu po kolei trzech czynności, wtedy jednak liczba wszystkich możliwych wyników doświadczenia jest równa kmn.

Elementy kombinatoryki

Do elementów kombinatoryki zaliczamy:

• permutacje
• kombinacje
• wariacje bez powtórzeń
• wariacje z powtórzeniami

Wariacje, Permutacje, Kombinacje

Według CKE wariacje z powtórzeniami to:,, Liczba sposobów, na które z n różnych elementów można utworzyć ciąg, składający się z k niekoniecznie różnych wyrazów, jest równa n^k". W przypadku wariacji z powtórzeniami wybierane elementy mogą się powtarzać, a kolejność wybieranych elementów ma znaczenie.

Natomiast wariacją bez powtórzeń jest liczbą sposobów, na które można utworzyć ciąg z n różnych elementów, składający się z k różnych wyrazów, przy czym 1≤k≤n, jest równa: n!/(n-k)!. W przypadku wariacji bez powtórzeń istotna jest kolejność wybieranych elementów oraz to, że elementy nie mogą się powtarzać.

Permutacją nazywamy liczbę sposobów, na które n(n≥1) różnych elementów może zostać ustawiona w ciąg. Jest wyrażona za pomocą wzoru n!.

Kombinacją można nazwać liczbę sposobów, na które spośród n różnych elementów można wybrać ‘’k’’ elementów, przy czym 0≤k≤n, zapisujemy ją za pomocą Symbolu Newtona. W przypadku kombinacji kolejność elementów nie ma znaczenia.

Silnia liczby naturalnej

Silnią (n!) liczby naturalnej, która jest większa od jeden nazywamy iloczyn wszystkich liczb naturalnych dodatnich, które nie są większe od n.

Historia kombinatoryki

Dwa podstawowe zagadnienia kombinatoryki, jakimi są liczba prenumeracji i kombinacji mają długą historię. Rozważane były już tysiąc lat temu w Indiach, Chinach i krajach Islamu. Przez dłuższy czas kombinatoryka była częścią prozodii, logiki, a nawet kwestii związanych z codziennym życiem. Kombinatoryka zaczęła nabierać bardziej naukowego charakteru razem z rozwojem prawdopodobieństwa. Po raz pierwszy termin kombinatoryka pojawił się w publikacji ,, Dissertatio de Arte Combinatoria" autorstwa Leibzniz’a w 1666 roku. Dopiero w połowie XX wieku kombinatoryka staje się jednym z głównych nurtów matematyki.

Bibliografia

• Wybrane wzory matematyczne (2015), Warszawa
• Janiec E. (2006), Nowa Encyklopedia Podręczna PWN, "Wydawnictwo Naukowe PWN", s.441
• Nowoświat K.(2014), Matematyka Europejczyka,"Helion“
• Rutkowski J. (2021), Kombinatoryka i rachunek prawdopodobieństwa
• Zakrzewski M. (2018),Markowe Wykłady z Matematyki, "GiS", Wrocław, s.3

Autor: Aleksandra Potejko