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 C_n^k i wyraża się wzorem:

C_n^k =

ć
č

n
k

ö
ř

k!(n-k)!

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

W szczególności dla k > n liczba kombinacji C_n^k 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:

ć
č

0
0

ö
ř

= 1

ć
č

1
0

ö
ř

= 1

ć
č

1
1

ö
ř

= 1

są równe liczbom:

C₀⁰ pustych podzbiorów zbioru pustego,
C₁⁰ pustych podzbiorów zbioru jednoelementowego i
C₁¹ 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

ć
č n
k ö
ř
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

ć
č n
k-1 ö
ř .

łącznie zbiór kombinacji n+1 po k ma

C_n+1^k =

ć
č

n
k

ö
ř

ć
č

n
k-1

ö
ř

ć
č

n+1
k

ö
ř

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 S_n 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 =

ć
ç
č

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ć:

ć
ç
č

ö
÷
ř

ć
ç
č

ö
÷
ř

Liczba | S_n| elementów zbioru S_n permutacji zbioru n-elementowego wyraża się wzorem:

| S_n| = n!.

Rzeczywiście, zbiór S₀ ma jeden element (ciąg pusty, mający 0 wyrazów) i 0! = 1; zbiór S₁ 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:

ć
ç
č

n+1

f(1)

f(2)

f(i) = n+1

f(n)

f(n+1)

ö
÷
ř

ć
ç
č

f(1)

f(2)

f(n)

f(n+1)

ö
÷
ř

ć
ç
č

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

| S_n+1| = (n+1)| S_n| = (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 S_n 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 V_n^k. 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 V_n^k k-wyrazowych wariacji bez powtórzeń n elementów wyraża się wzorem

V_n^k =

ć
č

n
k

ö
ř

k! =

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

W szczególności jeśli k > n, to V_n^k = 0.

Rzeczywiście, jeśli k = 0 lub k = 1 to łatwo sprawdzić, że liczba

ć
č

n
0

ö
ř

0! =

jest liczbą V₀ⁿ pustych ciągów elementów zbioru n-elementowego,

ć
č

n
1

ö
ř

1! =

jest liczbą V₁ⁿ jednowyrazowych ciągów elementów zbioru n-elementowego. Jeśli dla pewnej liczby k zachodzi równość

ć
č

n
k

ö
ř

k! =

to 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

V_n^k+1 = (n-k)V_n^k = (n-k)

ć
č

n
k

ö
ř

k! =

(n-k)

k+1

ć
č

n
k

ö
ř

(k+1)! =

ć
č

n
k+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 W_n^k i obliczamy według wzoru

W_n^k = n^k

który jest (z definicji) prawdziwy dla wszystkich zbiorów (w tym nieskończonych) jeśli przyjć umowę, że 0⁰ = 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

| S_n| = n! =

ć
č

n
n

ö
ř

n! = V_nⁿ.

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

V_n^k =

ć
č

n
k

ö
ř

k! = C_n^k·k!.

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

| 2^X| =

ć
č

n
0

ö
ř

ć
č

n
1

ö
ř

ć
č

n
k

ö
ř

= (1+1)ⁿ = 2ⁿ = 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:

f_Y(x) =

ě
í
č

1 gdy x Î Y

0 gdy x Ď Y

Zatem

˝ 2^X˝ = W₂ⁿ = 2ⁿ = 2^{| X|}.

Wzór

˝ 2^X˝ = 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 x₁,x₂, ¼,x_n 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 x₁ a pierwszym x₂, między ostatnim x₂ a pierwszym x₃, 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 x₁, każdy x między pierwszą a drugą przegródką - przez x₂, 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-1
d

ö
ř

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)

xⁿ

(e^x-1) ^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

ć
č

n
k

ö
ř

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 W₂ⁿ = 2ⁿ. Już dla n = 10 jest to pokaźna liczba 1024 sztuk.
2ⁿ parami różnych n-wyrazowych ciągów zer i jedynek stanowią rozwinięcia dwójkowe liczb całkowitych od 0 do 2ⁿ-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 C_n^k kombinacji po k elementów ze zbioru {1,2,¼,n} można użyć wielomianu n+1 zmiennych

(1+y₁x)(1+y₂x)·¼·(1+y_nx).

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

(1+y₁x)(1+y₂x)(1+y₃x)(1+y₄x)

y₁y₂y₃y₄x⁴+( ( ( y₁+y₂) y₃+y₁y₂) y₄+y₁y₂y₃) x³+

( ( y₁+y₂+y₃) y₄+( y₁+y₂) y₃+y₁y₂) x²+ ( y₁+y₂+y₃+y₄) x+1

ma współczynnik y₃y₄+y₂y₄+y₁y₄+y₂y₃+y₁y₃+y₁y₂ przy x², więc szukanymi kombinacjami są

Powrót do FAQ