Wersja z 2013–05–05

Część poprzednia Spis treści Część następna

Rozpoznawanie rodzaju zestawień

Właściwości poszczególnych typów zestawień obrazuje tabela:

  spośród wyciągamy czy zwracamy? czy notujemy kolejność?
permutacje bez powtórzeń n różnych elementów wszystkie nie tak
permutacje z powtórzeniami n elementów, w tym identyczne wszystkie nie tak
wariacje bez powtórzeń n różnych elementów k elementów, k < n nie tak
wariacje z powtórzeniami n różnych elementów k elementów tak tak
kombinacje bez powtórzeń n różnych elementów k elementów, k < n nie nie
kombinacje z powtórzeniami n różnych elementów k elementów tak nie

Uwaga! Słowo „element” ma tu inne znaczenie niż w szkolnej teorii mnogości (nauce o zbiorach), i dlatego w pięciu przypadkach dodano określenie „różny”. Dopóki mowa tylko o zbiorach (i ciągach), elementy identyczne uważamy za ten sam element – na przykład cztery identyczne trójkąty i dwa identyczne prostokąty tworzą zbiór dwuelementowy, a nie sześcioelementowy. Wprowadzenie pojęcia „multizbiór” sprawia, że konieczne staje się także liczenie powtórzeń elementów rozumianych w sposób klasyczny. Dla uniknięcia nieporozumień najlepiej mówić wówczas, że cztery identyczne trójkąty i dwa identyczne prostokąty to łącznie dwa elementy różne, ale sześć elementów, wliczając powtórzenia.

Koniecznie zwróćmy uwagę, że w wypadku permutacji z powtórzeniami znaczenie symbolu n jest inne niż dla pozostałych zestawień. Jeżeli mamy na przykład dane dwa (nierozróżnialne) trójkąty, trzy kwadraty i cztery koła, i mamy z takiego multizbioru ułożyć wariacje z powtórzeniami lub kombinacje z powtórzeniami, wówczas n oznacza ilość elementów rozumianych klasycznie, a zatem przyjmujemy n = 3. Jeśli jednak chodzi o ułożenie permutacji z powtórzeniami, wówczas musimy n potraktować jako sumę powtórzeń każdego z (różnych) elementów, a więc wówczas n = 9.

W przypadku wariacji z powtórzeniami i kombinacji z powtórzeniami sumaryczna liczba powtórzeń nie musi być (i zwykle nie jest) podana – bo też nie jest nam do niczego potrzebna. Można sobie wówczas wyobrazić, że dysponujemy dostatecznie dużą ilością kopii każdego z zestawianych elementów, co najmniej tyloma kopiami, ile wynosi długość konstruowanego zestawienia (k). Na przykład rozważmy zadanie, które polega na ułożeniu wszystkich możliwych trójwyrazowych wariacji z powtórzeniami z trójkątów, czworokątów i pięciokątów, przy czym figury mogą się powtarzać (k = 3, n = 3). Zauważmy przy okazji, że choć k = n, w zadaniu tym mowa jest o wariacjach z powtórzeniami, a nie o permutacjach z powtórzeniami, choćby dlatego, że nie wiemy, ile mamy trójkątów, ile czworokątów, a ile pięciokątów. Powiedzmy, że dysponujemy trzema fizycznymi modelami trójkąta (np. wyciętymi z papieru), trzema czworokąta i trzema pięciokąta, i tworzymy z nich zestawienia w ten sposób, że wykorzystujemy tylko 3 dowolne modele spośród posiadanych dziewięciu. Możemy jednak dysponować równie dobrze setką trójkątów, setką czworokątów i setką pięciokątów. Jest nieistotne, ile tak naprawdę posiadamy fizycznych kopii zestawianych obiektów, ważne jedynie, by było ich co najmniej 3 – tyle, ile wynosi długość konstruowanego zestawienia. Zresztą możemy nawet dysponować tylko jedną kopią każdej figury, i zwracać ją do puli po każdym wyciągnięciu, a powstające zestawienie rysować na kartce papieru.

Zadanie na tworzenie permutacji z powtórzeniami musiałoby wyglądać zupełnie inaczej, na przykład tak, że dysponowalibyśmy dokładnie dwoma nierozróżnialnymi trójkątami i jednym czworokątem, i mielibyśmy ułożyć z tego ciągi o długości 3, czyli wykorzystać wszystko, co mamy. Choć mamy do czynienia z dwoma typami figur, tym razem operujemy nie na zbiorze, lecz na multizbiorze, i dlatego przyjmujemy n = 3 (oraz n1 = 2, n2 = 1).

Aby ustalić rodzaj zestawień, które będziemy analizować, należy postępować według następującego algorytmu:

  1. Ustalamy, czy kolejność elementów w zestawieniach jest istotna, czy też nie. Jeżeli nie jest istotna, a zestawienia różnią się tylko składem, mamy do czynienia z kombinacjami i omijamy punkt b.
  2. Ustalamy, czy zestawienia różnią się tylko kolejnością elementów. Jeżeli tak, mamy do czynienia z permutacjami. Jeżeli różnią się nie tylko kolejnością elementów, ale także składem, nasze zestawienia to wariacje.
  3. Ustalamy, czy w zestawieniach elementy powtarzają się, czy też nie.

O jakich zestawieniach mowa w poniższych zadaniach? Rozwiązania podano na dole strony.

  1. Bierzemy 3 prostokąty, 2 koła i 4 trójkąty, i układamy je kolejno jeden za drugim w różnej kolejności.
  2. Z 32 liter polskiego alfabetu układamy dowolne, 5-literowe wyrazy.
  3. Spośród sześciu osób, tylko cztery mogą otrzymać zaproszenia.
  4. 10 osób ustawiamy w szeregu na różne sposoby.
  5. W urnie znajduje się 2 kule żółte i 5 zielonych. Wyciągamy 3 kule bez zwracania, notujemy ilość wyciągniętych kul żółtych i zielonych.
  6. W urnie znajdują się 2 kule żółte i 5 zielonych. Wyciągamy kolejno wszystkie kule bez zwracania i notujemy ich kolory w kolejności ciągnienia.
  7. W urnie znajduje się 7 kul, każda w innym kolorze. Wyciągamy kolejno wszystkie kule bez zwracania i notujemy ich kolory w kolejności ciągnienia.
  8. Losujemy 6 ponumerowanych kul z 49 (Duży Lotek).
  9. Z cyfr 1,2,3,4,5 układamy różne liczby pięciocyfrowe tak, aby żadna cyfra się nie powtarzała.
  10. Z cyfr 1,2,3,4,5 układamy różne liczby czterocyfrowe tak, aby żadna cyfra się nie powtarzała.
  11. Z cyfr 1,2,3,4,5 układamy różne liczby pięciocyfrowe. Cyfry mogą się powtarzać.
  12. Z cyfr 1,2,3,4,5 układamy różne liczby czterocyfrowe. Cyfry mogą się powtarzać.

Część poprzednia Spis treści Część następna