Na lekcji zapoznasz się z podstawowymi pojęciami
kombinatoryki: permutacjami, kombinacjami i wariacjami.
Permutacje
Wybierz, za pomocą trójkącików 
liczbę elementów
zbioru n = 2, a następnie zaznacz kropką 
permutacje i naciśnij
"Dalej" lub "Automatycznie".
Otrzymałeś zbiór {A, B} oraz dwa
ciągi 2-elementowe: AB i BA. Ciągi te
nazywamy permutacjami elementów zbioru {A, B}.
Permutacje powstają więc z przestawiania elementów
danego zbioru. Liczba permutacji zbioru 2-elementowego
wynosi 2, co zapisujemy symbolicznie P2
= 2.
Wybierz n = 3 i naciśnij "Czyść" i
"Dalej".
Dla zbioru {A, B, C}
otrzymałeś sześć permutacji.
Spróbuj odkryć zasadę przestawiania elementów podczas
tworzenia permutacji oraz uzasadnić, że liczba permutacji
zbioru 3-elementowego to P3 = 6.
Przestawianie elementów A, B, C
wykonywane jest następująco: ustawiamy element A
na początku i wykonujemy dwie permutacje elementów B
i C, następnie ustawiamy na pierwszym miejscu
element B i wykonujemy dwie permutacje
elementów A i C, na koniec ustawiamy
na pierwszym miejscu element C i znów
wykonujemy dwie permutacje elementów A i B.
Ponieważ na pierwszym miejscu może stać każdy z
trzech elementów i dla każdego z nich istnieją dwie
permutacje pozostałych elementów, więc liczba
wszystkich permutacji to P3 = 3 .
2 = 6.
Utwórz wszystkie permutacje zbioru 4-elementowego {A,
B, C, D} i uzasadnij, że ich
liczba wynosi P4 = 4 .
6 = 24. Wynik sprawdź za pomocą programu.
Gdy element A stoi na pierwszym miejscu, to z
pozostałych trzech elementów B, C, D
możemy utworzyć 6 permutacji. Analogicznie jest dla
każdego innego elementu, zatem łącznie mamy P4
= 4 . 6 = 24 permutacje.
Wyprowadź wzór na liczbę permutacji zbioru n-elementowego.
Analogicznie do zbioru 4-elementowego, możemy
wyznaczyć liczbę permutacji zbioru 5-elementowego: P5
= 5 . 24 = 120. Dla zbioru
6-elementowego otrzymamy: P6 = 6 .
120 = 720. Zatem dla zbioru n-elementowego
otrzymujemy: Pn = n
. Pn-1.
Jest to wzór rekurencyjny, z którego łatwo otrzymać
wzór ogólny: Pn = n
. Pn-1
= n . (n -
1) . Pn-2
= n . (n
- 1) . (n - 2) .
Pn-3 = . . . = n
. (n - 1) .
(n - 2) . ... .
1.
Iloczyn 1 . 2
. 3 .
... . n
oznaczamy symbolem n!
i czytamy n
silnia.
Liczba permutacji zbioru n-elementowego
wynosi: Pn
= n!
Zadanie 1
Na ile sposobów można potasować talię 24 kart?
Zadanie 2
Pewien zbiór ma n elementów, a liczba jego
permutacji jest n-cyfrowa. Ile wynosi n?
Zadanie 3
Ile razy więcej jest permutacji 6-elementowych niż
permutacji 4-elementowych?
Zadanie 4
Na ile sposobów można dołożyć do ciągu
4-elementowego A, B, C, D
dwa nowe elementy E i F?
Wariacje bez powtórzeń
Aby wyznaczyć wariacje, należy określić, ile
elementów danego zbioru ma tworzyć każdą wariację.
Jeśli wariacje są "bez powtórzeń", to elementy
wchodzące w skład wariacji nie mogą się powtarzać.
Utworzymy wariacje 2-elementowe bez powtórzeń ze zbioru
3-elementowego.
Wpisz do programu n = 3 i k = 2 oraz
zaznacz kropką
wariacje bez powtórzeń i naciśnij "Czyść" oraz
"Dalej".
Otrzymałeś 6 wariacji bez powtórzeń. Zauważ, że
wariacją jest zarówno AB, jak i BA.
Analogicznie jest dla pozostałych wariacji. W wariacjach
kolejność odgrywa istotną rolę, dlatego wariacje, tak
jak i permutacje, należy utożsamiać z ciągami.
Wpisz n = 4 i k = 2.
Otrzymałeś 12 wariacji, czyli 12 ciągów 2-wyrazowych.
Zauważ, że 12 = 4 . 3.
Wybierz n = 4 i k = 3.
Otrzymałeś 24 wariacje, z których każda jest
3-wyrazowym ciągiem. Zauważ, że 24 = 4 .
3 . 2.
Liczba wariacji k-elementowych
bez powtórzeń ze zbioru n-elementowego
wyraża się wzorem
n .
(n - 1) .
... . (n
- k + 1).
Uzasadnienie jest proste. Jeśli mamy zbudować
wszystkie ciągi k-elementowe bez powtórzeń,
mając n elementów, to pierwszy wyraz można
wybrać ze wszystkich elementów na n sposobów,
drugi wyraz można wybrać z pozostałych elementów na n
- 1 sposobów, trzeci na n - 2 sposobów, itd.,
a w końcu k-ty wyraz na n - k
+ 1 sposobów.
Zadanie 5
Sprawdź za pomocą programu, że dla n = 6 i k
= 3, otrzymujemy 6 . 5 .
4 wariacji.
Zadanie 6
Danych jest 5 osób oznaczonych literami: A, B,
C, D, E.
A
B
C
D
E
a) Ile jest
możliwości przyznania tym osobom 3 nagród?
Zakładamy, że
1 osoba może otrzymać 1 nagrodę i nagrody są różne.
b) Ile jest
możliwości przyznania tym osobom 4 nagród?
c) Ile jest
możliwości przyznania tym osobom 5 nagród?
Zadanie 7
Dla jakich n i k,
liczba wariacji k-elementowych bez powtórzeń ze
zbioru n-elementowego, jest równa liczbie
permutacji n-elementowych?
Zadanie 8
Sprawdź za pomocą programu, że liczbę wariacji bez
powtórzeń można zapisać w postaci: 
. Spróbuj
uzasadnić ten wzór i podać jego interpretację.
Zadanie 9
Masz dany zbiór 3-elementowy {A, B, C}
oraz wszystkie jego permutacje: ABC, ACB, BAC,
BCA, CAB, CBA. Sprawdź, czy
skreślając w każdej z tych permutacji pierwszy element,
otrzymasz prawidłową listę wariacji 2-elementowych.
Zadanie 10
Masz dany zbiór 4-elementowy {A, B, C,
D} oraz wszystkie jego permutacje: ABCD, ABDC,
ACBD, ACDB, ADBC, ADCB, BACD,
BADC, BCAD, BCDA, BDAC, BDCA,
CABD, CADB, CBAD, CBDA, CDAB,
CDBA, DABC, DACB, DBAC, DBCA,
DCAB, DCBA. Zauważ, że skreślając w
każdej z tych permutacji dwa pierwsze elementy, nie
otrzymasz prawidłowej listy wariacji 2-elementowych. Jakie
jeszcze skreślenia należy wykonać, aby lista była
prawidłowa?
Wariacje z powtórzeniami
Wpisz do programu n = 3, k = 2 i utwórz
wariacje z powtórzeniami.
Otrzymałeś 9 ciągów 2-elementowych, wśród
których 3 ciągi: AA, BB i CC
zawierają powtarzające się elementy.
Wykonaj serię przykładów na wariacje z powtórzeniami,
przyjmując różne wartości n i k.
Spróbuj podać wzór na liczbę wariacji w zależności od n
i k.
Liczba wariacji k-elementowych
ze zbioru n-elementowego
wynosi nk.
Uzasadnienie wzoru jest analogiczne jak dla wariacji
bez powtórzeń: mając danych n elementów,
można zbudować wszystkie ciągi k-elementowe z
powtarzającymi się elementami, wybierając pierwszy
wyraz spośród wszystkich elementów, drugi wyraz
również spośród wszystkich elementów, itd. Łącznie
mamy więc 
= nk
sposobów.
Zadanie 11
Ile wariacji 6-elementowych z powtórzeniami można
utworzyć, mając 20 elementów?
Zadanie 12
Liczba wariacji 3-elementowych z powtórzeniami,
utworzonych z elementów pewnego zbioru, wynosi 8000. Ile
elementów ma ten zbiór?
Zadanie 13
Liczba wariacji 2-elementowych z powtórzeniami,
utworzonych z elementów pewnego zbioru, jest większa od
liczby wariacji 2-elementowych bez powtórzeń, utworzonych z
elementów tego samego zbioru. Ile elementów ma zbiór,
jeżeli ta różnica jest równa:
a) 3; b) 7; c)
25; d) k?
Zadanie 14
Ile wyrazów można ułożyć z 25 liter, zakładając,
że spółgłoski i samogłoski występują na przemian,
jeżeli wyrazy mają się składać z:
a) 5 liter; b) 7 liter?
Zadanie 15
Ile jest różnych bajtów? Bajt to słowo ośmiobitowe,
czyli złożone z ośmiu cyfr 0 lub 1.
Kombinacje bez powtórzeń
Aby wyznaczyć kombinacje, należy określić, ile
elementów danego zbioru ma tworzyć kombinacje. Wyrażenie
"bez powtórzeń" oznacza, że elementy wchodzące
w skład kombinacji nie mogą się powtarzać.
Utworzymy kombinacje 2-elementowe ze zbioru
3-elementowego.
Wybierz n = 3 i k = 2 oraz zaznacz
kropką
kombinacje bez powtórzeń i naciśnij "Czyść" i
"Dalej".
Otrzymałeś tylko 3 kombinacje bez powtórzeń.
Zauważ, że jeśli została wypisana kombinacja AB,
to BA nie jest już wypisywana, ponieważ jest
to ta sama kombinacja. Pamiętaj, że w kombinacjach
kolejność występowania elementów nie jest istotna.
Wybierz n = 4 i k = 3.
Otrzymałeś 4 kombinacje, czyli wszystkie możliwe
podzbiory 3-elementowe. Zauważ, że jeśli kombinacja ABC
została wypisana, to nie jest już wypisywana np. CBA,
ponieważ jest to ta sama kombinacja.
Aby wyprowadzić wzór na liczbę kombinacji bez
powtórzeń, należy zauważyć, że jeśli danych jest 6
wariacji 3-elementowych, np. ABC, ACB, BAC,
BCA, CAB, CBA, to odpowiada im
jedna kombinacja ABC. Zatem kombinacji k-elementowych
jest k! razy mniej niż wariacji k-elementowych,
ponieważ na tyle sposobów można permutować zbiór k-elementowy.
Liczba kombinacji bez powtórzeń wyraża się
wzorem 
.
Wyrażenie to oznacza się często symbolem 
i czyta "n
po k".
Zadanie 16
Ile jest kombinacji 10-elementowych ze zbioru
14-elementowego?
Zadanie 17
Na ile sposobów z talii 24 kart można wybrać:
a) 6 kart; b) 12 kart; c)
18 kart?
Zadanie 18
Dany jest zbiór 10-elementowy. Podaj parę różnych
liczb k1 i k2, dla
których liczba kombinacji k1-elementowych
jest równa liczbie kombinacji k2-elementowych.
Kombinacje z powtórzeniami
Wybierz n = 3 i k = 2 oraz zaznacz
kropką
kombinacje z powtórzeniami i naciśnij "Czyść" i
"Dalej".
Otrzymałeś 6 kombinacji 2-elementowych z
powtórzeniami, w których występują elementy A,
B, C. Kolejność występowania
elementów nie jest istotna, np. dla kombinacji AC
nie jest wypisywana kombinacja CA, gdyż jest to
ta sama kombinacja.
Dlaczego liczba kombinacji wynosi 6? Spróbuj to
wywnioskować z następującego zestawienia:
AA, AB,
AC, BB,
BC, CC
- wszystkie kombinacje 2-elementowe z powtórzeniami,
AD, AB,
AC, BD,
BC, CD
- zmieniając powtarzające się elementy na nowy element
D, otrzymujemy kombinacje bez powtórzeń. Zatem
liczba 2-elementowych kombinacji z powtórzeniami ze
zbioru 3-elementowego jest równa liczbie 2-elementowych
kombinacji bez powtórzeń ze zbioru 4-elementowego.
Sprawdź to za pomocą programu!
Wybierz n = 4 i k = 3.
Otrzymałeś 20 kombinacji 3-elementowych z
powtórzeniami ze zbioru 4-elementowego {A, B,
C, D}:
AAA, AAB, AAC, AAD, ABB, ABC, ABD,
ACC, ACD,
ADD, BBB, BBC, BBD, BCC, BCD, BDD, CCC, CCD, CDD, DDD.
Zmieniając powtarzające się elementy na nowe elementy E
i F, otrzymujemy kombinacje bez powtórzeń:
AEF, AEB, AFC, AED, ABF, ABC, ABD,
ACE, ACD,
ADF, BEF, BEC, BFD, BCF, BCD, BDE, CEF, CED, CDF, DEF.
Zatem liczba 3-elementowych kombinacji z powtórzeniami
ze zbioru 4-elementowego jest równa liczbie
3-elementowych kombinacji bez powtórzeń ze zbioru
6-elementowego. Sprawdź to za pomocą programu!
Liczba k-elementowych
kombinacji z powtórzeniami ze zbioru n-elementowego
jest równa liczbie k-elementowych
kombinacji bez powtórzeń ze zbioru n+k-1-elementowego.
Podstawiając do wzoru w miejsce n
wyrażenie n+k-1,
otrzymujemy wzór na liczbę kombinacji
k-elementowych z powtórzeniami ze
zbioru n-elementowego:
.
Zadanie 19
Ile razy więcej jest kombinacji 2-elementowych z
powtórzeniami ze zbioru 10-elementowego, niż kombinacji
10-elementowych z powtórzeniami ze zbioru 2-elementowego?
Zadanie 20
Z talii 24 kart wybieramy kolejno 4 karty, zwracając za
każdym razem wylosowaną kartę do talii. Ile różnych
układów 4 kart można w ten sposób otrzymać?
Zadanie 21
Mamy trzy rodzaje owoców: jabłka, gruszki i pomarańcze.
Ile różnych paczek można utworzyć, jeśli każda paczka
ma zawierać 5 owoców?
Zadanie 22
W loterii jest 100 losów, w tym 4 wygrywające. Losy
wygrywające są równorzędne. 25 osób kupiło po 4 losy.
Ile jest różnych rozkładów losów wygrywających?
Zadanie 23
| Niech n = 5, 6, 7, 8; k
= 5. Który wykres przedstawia liczbę:
a) permutacji;
b) wariacji bez powtórzeń;
c) wariacji z powtórzeniami;
d) kombinacji bez powtórzeń;
e) kombinacji z powtórzeniami?
|
 |
Zadanie 24
| Niech n = 5; k = 1,
2, 3, 4, 5. Który wykres przedstawia liczbę:
a) permutacji;
b) wariacji bez powtórzeń;
c) wariacji z powtórzeniami;
d) kombinacji bez powtórzeń;
e) kombinacji z powtórzeniami?
|
 |
Obliczenia kombinatoryczne w
arkuszu kalkulacyjnym
Poniżej przedstawiamy sposoby wyznaczania liczby
permutacji, wariacji i kombinacji za pomocą arkusza
kalkulacyjnego. Zwracamy uwagę, że wariacje bez powtórzeń
i kombinacje bez powtórzeń są określone, gdy n
jest większe od k.
Programowanie obliczeń
kombinatorycznych w języku Pascal
Poniżej przedstawiamy program w języku Pascal,
wykonujący obliczanie liczby permutacji, wariacji i
kombinacji.
program Kombinatoryka;
uses crt;
var n,k:integer;
function silnia(s:integer):real;
var i:integer; x:real;
begin
x:=1;
for i:=1 to s do x:=x*i; silnia:=x;
end;
begin
clrScr;
n:=8; k:=5;
writeLn(' n = ',n);
writeLn(' k = ',k);
writeLn(' permutacje: ',silnia(n):7:0);
writeLn(' wariacje bez powtorzen:
',silnia(n)/silnia(n-k):7:0);
writeLn(' wariacje z powtorzeniami:
',exp(k*ln(n)):7:0);
writeLn(' kombinacje bez powtorzen:
',silnia(n)/silnia(k)/silnia(n-k):7:0);
writeLn('kombinacje z powtorzeniami:
',silnia(n+k-1)/silnia(k)/silnia(n-1):7:0);
readLn;
end.
Po uruchomieniu tego programu otrzymujemy
następujące wyniki:
Odpowiedzi
1. 24!
= 620 448 401 733 239 439 360 000.
2.
22 lub 23, lub 24.
3. 30.
4. 30.
5. Wpisując
do programu n = 6 i k = 3, otrzymujemy 120
= 6 . 5 .
4 wariacji.
6. a)
60; b) 120; c) 120.
7.
k = n - 1 lub k = n.
8.
= 
= (n - k
+ 1) . . . . .
(n - 1) . n. Ze
wzoru wynika, że wariacji k-elementowych
ze zbioru n-elementowego jest (n-k)!
razy mniej niż wszystkich permutacji. Np. wariacji
2-elementowych ze zbioru 5-elementowego jest 6 razy mniej
niż wszystkich permutacji tego zbioru. Sprawdź to!
10.
Należy jeszcze skreślić po jednym z każdej pary
powtarzających się ciągów 2-elementowych. Powinno
pozostać 12 wariacji.
11. 64
000 000.
12.
20.
13. a)
3; b) 7; c) 25; d)
k.
14.
a) 250 000; b) 25 000 000.
15. 28
= 256 (bajt składa się z 8 bitów; bit to "0" lub
"1").
16.
1001.
17. a) 134
596; b) 2 704 156; c) 134
596.
18.
Np. 1 i 9; 2 i 8, itp. Wniosek: = 
. (Zobacz też lekcję "Newton - Pascal -
Sierpiński - Fibonacci".)
19. 5.
20. 17
550.
21. 21.
22.
a) A; b) C; c)
B; d) E; e) D.
23. a)
A; b) C; c) B; d)
E; e) D.