Kombinatoryka




Kombinatoryka
Kombinatoryka zajmuje się zagadnieniami

przeliczenia
(określenia liczby elementów),
wyliczenia
(wypisania wszystkich elementów),
optymalizacji
zbiorów skończonych. Do kombinatoryki zalicza się teorię grafów.


1  Zagadnienia przeliczenia
Przeliczenie polega na określeniu liczby elementów pewnego zbioru.
Najprostsze przykłady są jednocześnie podstawowymi wzorami elementarnej
kombinatoryki:

Przykład 1. Kombinacje. Zbiór k-elementowych podzbiorów zbioru
n-elementowego. Liczba jego elementów, czyli liczba
k-elementowych podzbiorów zbioru n-elementowego (zwanych
kombinacjami n po k) oznaczana jest symbolem
Cnk i wyraża się wzorem:








Cnk
=
ćŁ
nk
�ł
=
n!

k!(n-k)!
=
n(n-1)·¼·(n-k+1)

k!
.W
szczególności dla k > n liczba kombinacji
Cnk jest równa 0. Ważne jest, że
zliczamy podzbiory, czyli kolejność elementów w zliczanych obiektach jest
nieistotna.
Rzeczywiście, jeśli n = 0 lub n = 1 to łatwo sprawdzić, że
liczby:






















ćŁ
00
�ł
= 1











ćŁ
10
�ł
= 1










ćŁ
11
�ł
= 1
są
równe liczbom:


C00 pustych podzbiorów zbioru pustego,
C10 pustych podzbiorów zbioru
jednoelementowego i
C11 jednoelementowych podzbiorów zbioru
jednoelementowego.
Załóżmy, że wzór na liczb kombinacji jest słuszny dla pewnej liczby n
i wszystkich k � {0,1,¼,n}. Policzymy podzbiory k-elementowe zbioru,
mającego n+1 elementów. Wyróżnijmy w tym zbiorze jeden element - nazwijmy
go (n+1)-szym elementem. Pozostałe elementy tworzą zbiór
n-elementowy. Zbiór wszystkich k-elementowych podzbiorów można
teraz podzielić na dwa rozłączne podzbiory:


pierwszy składa się z tych podzbiorów k-elementowych, do których
(n+1)-szy element nie należy; są więc one k-elementowymi
podzbiorami zbioru n-elementowego i jest ich




ćŁ
nk
�ł
drugi składa się z tych podzbiorów k-elementowych, do których
(n+1)-szy element należy; każdy z nich powstaje z jednoznacznie
określonego (k-1)-elementowego podzbioru zbioru n-elementowego
przez dołączenie (n+1)-szego elementu; zatem takich podzbiorów jest
tyle, co (k-1)-elementowych podzbiorów zbioru n-elementowego -
jest ich




ćŁ
nk-1
�ł
.
łącznie zbiór kombinacji n+1 po k ma








Cn+1k =




ćŁ
nk
�ł
+




ćŁ
nk-1
�ł
=




ćŁ
n+1k
�łelementów.
Na zasadzie indukcji matematycznej wzór na liczbę kombinacji jest prawdziwy dla
każdej liczby naturalnej n.

Przykład 2. Permutacje. Zbiór Sn wszystkich
wzajemnie jednoznacznych funkcji odwzorowujących zbiór n-elementowy na
siebie.Wzajemnie jednoznaczne odwzorowanie f:X® X nazywamy permutacją zbioru X. Jeśli
X = {1,2,¼,n}, to permutacja f
odpowiada sposobowi ustawienia jego elementów w ciąg (bez powtórzeń) ( f(1),f(2),¼,f(n)). Odwrotnie,
każde takie ustawienie w ciąg określa wzajemnie jednoznaczną funkcję f:
f(x) to jest x-ty wyraz cigu. Na przykład ciąg (1,2,¼,n) w naturalnej kolejności odpowiada funkcji
tożsamościowej f(x) = x. Często wygodnie jest zapisywać
permutację f za pomocą tabelki funkcji f:








f =
�









1




2




¼




n





f(1)





f(2)





¼




f(n)
��ł
.Jeśli
górny wiersz tabelki jest w naturalnej kolejności, to dolny jest ciągiem,
odpowiadajcym permutacji f. Tabelka ma tę przewagę nad ciągiem, że zmiana
kolejności wypisywania elementów nie przeszkadza w odczytaniu permutacji -
odpowiada przestawieniu kolumn, które można z powrotem uporządkować:









�









3




4




2




1





2




3




4




1
��ł
=
�









1




2




3




4





1




4




2




3
��ł
.
Liczba | Sn| elementów zbioru
Sn permutacji zbioru n-elementowego wyraża się
wzorem:








| Sn| =
n!.
Rzeczywiście, zbiór S0 ma jeden element (ciąg pusty, mający
0 wyrazów) i 0! = 1; zbiór S1 ma jeden element (ciąg
jednowyrazowy) i 1! = 1. Załóżmy, że wzór na liczb permutacji jest prawdziwy dla
pewnej liczby naturalnej n. Wyróżnijmy (i nazwijmy (n+1)-szym)
jeden element zbioru (n+1)-elementowego; pozostałe elementy tworzą zbiór
n-elementowy. Każda permutacja zbioru (n+1)-elementowego powstaje
z jednoznacznie określonej permutacji zbioru n-elementowego, któr
znajdujemy wykreślając z tabelki (albo ciągu) (n+1)-szy element i
''dosuwając w lewo'' elementy dolnego wiersza tak, żeby nie było w nim pustego
miejsca:




























�









1





2





¼




i




¼




n





n+1






f(1)





f(2)





¼




f(i) =
n+1




¼




f(n)





f(n+1)
��ł











®






�










1





2





¼




i





¼




n





·





f(1)





f(2)





¼




·




¼




f(n)





f(n+1)
��ł












®






�










1





2





¼




i





¼




n






f(1)





f(2)





¼




f(i+1)





¼




f(n+1)
��ł


Zatem
jest n! możliwości utworzenia ciągu bez (n+1)-szego elementu.
Odtworzyć permutację (ciąg) z ciągu bez (n+1)-szego elementu można
dopisując (n+1)-szy element, przy czym można to zrobić na n+1
sposobów: (n+1)-szy element można dopisać na pocztąku (jako f(1)),
przed drugim (jako f(2)), ..., przed n-tym (jako
f(n)) albo na końcu (jako f(n+1)). Łącznie liczba
permutacji zbioru (n+1)-elementowego jest równa








| Sn+1| =
(n+1)| Sn| = (n+1)n! =
(n+1)!i wzór
na liczbę permutacji jest prawdziwy dla wszystkich liczb naturalnych n na
zasadzie indukcji matematycznej.
Uwaga. Permutacje jednego zbioru można ze sobą składać
(złożenie funkcji) i obliczać permutację odwrotną (funkcja odwrotna). Łatwo to
robić praktycznie za pomocą tabelek. W ten sposób zbiór
Sn z działaniem składania
okazuje się grupą, zwaną grupą symetryczną.

Przykład 3. Wariacje bez powtórzeń. Zbiór wszystkich funkcji
różnowartościowych zbioru k-elementowego w zbiór
n-elementowy.Funkcje różnowartościowe określone w zbiorze
k-elementowym o wartościach w zbiorze n-elementowym nazywamy
k-wyrazowymi wariacjami bez powtórzeń n elementów. Dla pary
liczb naturalnych n, k liczbę elementów zbioru k-wyrazowych
wariacji bez powtórzeń n elementów oznaczamy
Vnk. Jeśli zbiorem
k-elementowym jest zbiór {1,2,¼,k}, to
wariacja bez powtórzeń fjest ciągiem k-wyrazowym (
f(1),f(2),¼ ,f(k))
elementów zbioru n-elementowego. Liczba
Vnk k-wyrazowych wariacji bez
powtórzeń n elementów wyraża się wzorem





Vnk =
ćŁ
nk
�ł
k! =
n(n-1)·¼·(n-k+1)W
szczególności jeśli k > n, to
Vnk = 0.
Rzeczywiście, jeśli k = 0 lub k = 1 to łatwo sprawdzić, że
liczba




ćŁ
n0
�ł
0! =
1jest liczbą
V0n pustych ciągów elementów zbioru
n-elementowego,




ćŁ
n1
�ł
1! =
njest liczbą
V1n jednowyrazowych ciągów elementów zbioru
n-elementowego. Jeśli dla pewnej liczby k zachodzi równość




ćŁ
nk
�ł
k! =
nto każdy ciąg k-wyrazowy
można przedłużyć do ciągu (k+1)-wyrazowego na tyle sposobów, ile
elementów zbioru n-elementowego nie występuje w tym ciągu, czyli na
n-k sposobów. Łącznie jest więc








Vnk+1 =
(n-k)Vnk =
(n-k)
ćŁ
nk
�ł
k! =
(n-k)

k+1

ćŁ
nk
�ł
(k+1)! =
ćŁ
nk+1
�ł
(k+1)! ciągów
(k+1)-wyrazowych i wzór na liczbę wariacji bez powtórzeń jest słuszny dla
wszystkich liczb naturalnych k.

Przykład 4. Wariacje z powtórzeniami. Zbiór wszystkich funkcji ze zbioru
k-elementowego w zbior n-elementowy. Elementy tego zbioru
nazywamy k-wyrazowymi wariacjami z powtórzeniami n
elementów. Liczbę k-wyrazowych wariacji z powtórzeniami n
elementów oznaczamy Wnk i obliczamy
według wzoru








Wnk =
nkktóry
jest (z definicji) prawdziwy dla wszystkich zbiorów (w tym nieskończonych) jeśli
przyjć umowę, że 00 = 1 (jedna - pusta - funkcja ze zbioru pustego w
zbiór pusty).


Między wymienionymi wzorami jest szereg zależności.


Przykład 5. Pemutacja zbioru {1,2,¼,n} jest n-wyrazową wariacją bez powtórzeń
n elementów i








| Sn| = n! =

ćŁ
nn
�ł
n! =
Vnn.

Przykład 6. k-wyrazowa wariacja n-elementów wyznacza
kombinację n elementów po k - wystarczy zapomnieć o kolejności
elementów, czyli przyporzdkować funkcji różnowartosciowej f:{1,2,¼,k}®{1,2,¼,n} jej obraz (zbiór wartości). Wariacje bez
powtórzeń wyznaczajce tę samą kombinację różnią się kolejności wyrazów, więc
jedną kombinację daje k! wariacji. Zatem








Vnk =
ćŁ
nk
�ł
k! =
Cnk·k!.

Przykład 7. Zbiór wszystkich podzbiorów zbioru X oznaczamy
2X i nazywamy zbiorem potęgowym zbioru X. Jeśli
zbiór X ma n elementów, | X| = n, to liczbę jego
podzbiorów | 2X| można obliczyć tak:








| 2X| =

ćŁ
n0
�ł
+
ćŁ
n1
�ł
+
¼
+
ćŁ
nk
�ł
= (1+1)n = 2n = 2|
X|
.Jeśli
X = {1,2,¼,n}, to można też każdemu
podzbiorowi Y zbioru X przyporządkować wzajemnie jednoznacznie
n wyrazową wariację z powtórzeniami dwóch elementów (0 i 1), zwaną
funkcją charakterystyczną tego podzbioru:








fY(x) =
��Ł









1 gdy x � Y





0 gdy x �
Y
.Zatem









�
2X� =
W2n = 2n =
2| X|
.
Wzór








�
2X� = 2|X|
jest (z
definicji) prawdziwy dla dowolnego zbioru X.


Zbiory permutacji, kombinacji i wariacji zaliczamy do schematów
kombinatorycznych. Poza wymienionymi podstawowymi schematami
kombinatorycznymi jest wiele prostych i bardzo użytecznych, np. schematy
przegródkowe:


Przykład 8. Obliczyć liczbę jednomianów n zmiennych
x1,x2, ¼,xn stopnia d.Jednomian
stopnia d jest iloczynem d czynników. Kolejność czynników w
iloczynie jest nieistotna, więc można przyjąć, że zmienne w iloczynie wystepują
w naturalnym porządku. Wstawmy do ciągu czynników iloczynu n-1
dodatkowych wyrazów - przegródek: między ostatnim x1 a
pierwszym x2, między ostatnim x2 a pierwszym
x3, itd. Teraz można wszystkie zmienne zastąpić jedną zmienną
x - przegródki pozwalają odtworzyć jednomian: każdy x przed
pierwszą przegródką trzeba zastapić przez x1, każdy x
między pierwszą a drugą przegródką - przez x2, itd. Zatem
jednomianów jest tyle samo, co ciągów złożonych z d liter x i
n-1 przegródek.Ale takich ciągów jest tyle, ile podzbiorów
d-elementowych (miejsc na x-y) zbioru
(n-1+d)-elementowego (numerów wyrazów ciągu). Zatem szukaną liczbą
jest




ćŁ
n+d-1d
�ł


Jest też wiele użytecznych, ale nie prostych schematów kombinatorycznych.


Przykład 9. Zbiór wszystkich funkcji ze zbioru n-elementowego
na zbiór k-elementowy. Liczb elementów tego zbioru oznaczamy symbolem
S(n,k). Liczby S(n,k) nazywamy
liczbami Stirlinga drugiego rodzaju. Można je obliczać za pomocą funkcji
tworzącej









¥ �n =
0 
S(n,k)
xn

n!
=
(ex-1)
k

k!
lub
rekurencyjnie:

















S(n,n) = 1
dla n ł 0,
S(n,0) = 0 dla n > 0,






S(n,k) =
S(n-1,k-1) +
kS(n-1,k).


Przykład 10. Liczba relacji równoważności w zbiorze
n-elementowym, mających k klas abstrakcji jest równa
S(n,k). Liczba rozbić zbioru n-elementowego na
k podzbiorów (parami rozłącznych) jest równa S(n,k).
Liczba wszystkich relacji równoważności w zbiorze n-elementowym (i
wszystkich rozbić zbioru n-elementowego) jest równa








B(n) =
n �k =
0 
S(n,k).Liczby
B(n) nazywamy liczbami Bella. Liczby Bella można obliczać
rekurencyjnie:








B(n+1) =
n �k =
0 

ćŁ
nk
�ł
B(k).


2  Zagadnienia wyliczenia
Tu ograniczymy się tylko do przykładów.

Przykład 11. Aby sprawdzić metodą zero-jedynkową czy jest tautologią
schemat zdaniowy w którym występuje n zmiennych zdaniowych, trzeba
wypisac wszystkie możliwe wartościowania tych zmiennych zdaniowych, czyli
wszystkie możliwe n-wyrazowe ciągi zer i jedynek. Takich ciągów jest
W2n = 2n. Już dla n
= 10 jest to pokaźna liczba 1024 sztuk. 2n parami różnych
n-wyrazowych ciągów zer i jedynek stanowią rozwinięcia dwójkowe liczb
całkowitych od 0 do 2n-1, w których puste miejsca z przodu
zapełniono zerami. Dla n = 4 są to:

















0 = 0000




4 = 0100




8 = 1000




12 = 1100






1 = 0001




5 = 0101




9 = 1001




13 = 1101






2 = 0010




6 = 0110




10 = 1010





14 = 1110






3 = 0011




7 = 0111




11 = 1011





15 =
1111
.

Przykład 12. Do wypisania wszystkich
Cnk kombinacji po k elementów
ze zbioru {1,2,¼,n} można użyć wielomianu
n+1 zmiennych








(1+y1x)(1+y2x)·¼·(1+ynx).Po
otwarciu nawiasów i uprządkowaniu według potęg zmiennej x w nawiasie jako
współczynnik przy xk odczytujemy sumę iloczynów po
k różnych zmiennych yi. Numery tych zmiennych w
jednym iloczynie tworzą kombinację, a we wszystkich iloczynach - wszystkie
kombinacje, np. dla n = 4, k = 2:








(1+y1x)(1+y2x)(1+y3x)(1+y4x)






















=




y1y2y3y4x4+(
( ( y1+y2)
y3+y1y2)
y4+y1y2y3)
x3+















( (
y1+y2+y3)
y4+(
y1+y2)
y3+y1y2)
x2+ (
y1+y2+y3+y4)
x+1
ma
współczynnik
y3y4+y2y4+y1y4+y2y3+y1y3+y1y2
przy x2, więc szukanymi kombinacjami są

















34




24




14





23




13




12
.



Powrót do FAQ