Załóżmy, że masz n typów elementów i chcesz wybrać zbiór r z nich. Możemy chcieć te przedmioty w określonej kolejności. Te zbiory elementów nazywamy permutacjami. Jeśli kolejność nie ma znaczenia, nazywamy zestaw kombinacji kolekcji. Dla obu kombinacji i permutacji możesz rozważyć przypadek, w którym wybierzesz niektóre z n typów więcej niż raz, co nazywa się „z powtórzeniem”, lub przypadek, w którym każdy typ wybierasz tylko raz, co nazywa się „nie powtórzenie'. Celem jest umiejętność policzenia możliwych kombinacji lub permutacji w danej sytuacji.
Zamówienia i Silnia
Funkcja silni jest często używana podczas obliczania kombinacji i permutacji. N! oznacza N×(N–1)×...×2×1. Na przykład 5! = 5×4×3×2×1 = 120. Liczba sposobów zamawiania zestawu elementów jest silnia. Weź trzy litery a, b i c. Masz trzy możliwości wyboru na pierwszą literę, dwie na drugą i tylko jedną na trzecią. Innymi słowy, w sumie 3×2×1 = 6 zamówień. Ogólnie jest n! sposoby zamawiania n sztuk.
Permutacje z powtórzeniami
Załóżmy, że masz trzy pokoje, które zamierzasz pomalować, a każdy z nich zostanie pomalowany na jeden z pięciu kolorów: czerwony (r), zielony (g), niebieski (b), żółty (y) lub pomarańczowy (o). Możesz wybrać każdy kolor tyle razy, ile chcesz. Masz do wyboru pięć kolorów dla pierwszego pokoju, pięć dla drugiego i pięć dla trzeciego. Daje to w sumie 5×5×5 = 125 możliwości. Ogólnie rzecz biorąc, liczba sposobów wybrania grupy r elementów w określonej kolejności z n powtarzalnych wyborów wynosi n^r.
Permutacje bez powtórzeń
Załóżmy teraz, że każdy pokój będzie miał inny kolor. Możesz wybrać jeden z pięciu kolorów dla pierwszego pokoju, cztery dla drugiego i tylko trzy dla trzeciego. Daje to 5×4×3 = 60, co akurat daje 5!/2!. Ogólnie rzecz biorąc, liczba niezależnych sposobów wybierania r elementów w określonej kolejności z n niepowtarzalnych wyborów wynosi n!/(n–r)!.
Kombinacje bez powtórzeń
Następnie zapomnij o tym, który pokój ma jaki kolor. Wystarczy wybrać trzy niezależne kolory dla schematu kolorów. Kolejność nie ma tu znaczenia, więc (czerwony, zielony, niebieski) jest taki sam jak (czerwony, niebieski, zielony). Dla każdego wyboru trzech kolorów są 3! sposoby ich zamawiania. Zmniejszasz więc liczbę permutacji o 3! aby uzyskać 5!/(2!×3!) = 10. Ogólnie rzecz biorąc, możesz wybrać grupę r elementów w dowolnej kolejności z wyboru n niepowtarzalnych wyborów na n!/[(n–r)!×r!] sposobów.
Kombinacje z powtórzeniem
Na koniec musisz stworzyć schemat kolorów, w którym możesz używać dowolnego koloru tyle razy, ile chcesz. Sprytny kod księgowy pomaga w tym zadaniu liczenia. Użyj trzech iksów do reprezentowania pomieszczeń. Twoja lista kolorów jest reprezentowana przez „rgbyo”. Wymieszaj X ze swoją listą kolorów i skojarz każdy X z pierwszym kolorem po lewej stronie. Na przykład rgXXbyXo oznacza, że pierwszy pokój jest zielony, drugi zielony, a trzeci żółty. X musi mieć co najmniej jeden kolor po lewej stronie, więc istnieje pięć dostępnych miejsc dla pierwszego X. Ponieważ lista zawiera teraz X, dostępnych jest sześć miejsc dla drugiego X i siedem dostępnych miejsc dla trzeciego X. W sumie jest 5×6×7 = 7!/4! sposoby pisania kodu. Kolejność sal jest jednak dowolna, więc tak naprawdę jest tylko 7!/(4!×3!) unikalnych aranżacji. Ogólnie rzecz biorąc, możesz wybrać r elementów w dowolnej kolejności z n powtarzalnych wyborów na (n+r–1)!/[(n–1)!×r!] sposobów.