Permutacje i kombinacje, różne sposoby wybierania obiektów ze zbioru, zazwyczaj bez zamiany, w celu utworzenia podzbiorów. Ten wybór podzbiorów nazywa się permutacją, gdy kolejność wyboru jest czynnikiem, a kombinacja, gdy kolejność nie jest czynnikiem. Biorąc pod uwagę stosunek liczby pożądanych podzbiorów do liczby wszystkich możliwych podzbiorów dla wielu gier losowych w XVII wieku, francuscy matematycy Blaise Pascal i Pierre de Fermat dali impuls do rozwoju kombinatoryki i teorii prawdopodobieństwa.
kombinatoryka: współczynniki dwumianowe
n obiektów nazywa się permutacją n rzeczy wziętych r na raz. Liczba permutacji wynosi
Pojęcia i różnice między permutacjami i kombinacjami można zilustrować, badając wszystkie różne sposoby wyboru pary obiektów spośród pięciu wyróżnialnych obiektów - takich jak litery A, B, C, D i E. Jeśli oba wybrane litery i kolejność wyboru są brane pod uwagę, możliwe są następujące 20 wyniki:
Każda z tych 20 różnych możliwych opcji nazywana jest permutacją. W szczególności są one nazywane permutacjami pięciu obiektów pobranych po dwa na raz, a liczbę takich możliwych permutacji oznaczono symbolem 5 P 2 w brzmieniu „5 permut 2.” Ogólnie, jeśli jest n dostępnych obiektów, z którego można wybrać, permutacje (P) mają być tworzone przy użyciu K obiektów w czasie, wiele różnych możliwych permutacji jest oznaczona symbolem n P k. Wzór na jego ocenę to n P k = n! / (N - k)! Wyrażenie n! —Czyta „n silnia” - oznacza, że wszystkie kolejne dodatnie liczby całkowite od 1 do n włącznie należy pomnożyć razem, i 0! jest zdefiniowany jako równy 1. Na przykład, stosując tę formułę, liczba permutacji pięciu obiektów pobranych po dwa na raz wynosi
(Dla k = n, n P k = n! Zatem dla 5 obiektów istnieje 5! = 120 aranżacji.)
W przypadku kombinacji, k obiektów jest wybieranych ze zbioru n obiektów, aby tworzyć podzestawy bez uporządkowania. Kontrastując poprzedni przykład permutacji z odpowiednią kombinacją, podzbiory AB i BA nie są już odrębnymi wyborami; eliminując takie przypadki, pozostaje tylko 10 różnych możliwych podzbiorów - AB, AC, AD, AE, BC, BD, BE, CD, CE i DE.
Liczba takich podzbiorów jest oznaczona przez n C k, czytaj „n wybierz k”. Dla kombinacji, ponieważ k obiektów ma k! ustalenia, są k! nierozróżnialne permutacje dla każdego wyboru k obiektów; stąd dzieląc formułę permutacji przez k! daje następującą formułę kombinacji:
Jest to to samo co współczynnik dwumianowy (n, k) (patrz twierdzenie o dwumianach). Na przykład liczba kombinacji pięciu obiektów wykonanych po dwa na raz wynosi
Wzór na n P k i n C k nazywa formuły liczenia, ponieważ mogą one być wykorzystane do policzyć liczbę możliwych permutacji i kombinacji w danej sytuacji bez konieczności wymienić je wszystkie.
