3. Kombinatoryka, zliczanie i generowanie obiektów kombinatorycznych, tożsamości kombinatoryczne, zasada włączania -wyłączania, podziały zbioru, liczby Stirlinga drugiego i pierwszego rodzaju.

Kombinatoryka pierwotnie elementarny dział teorii mnogości, którego przedmiotem było badanie różnych możliwych zestawień i ugrupowań, jakie można tworzyć z elementów dowolnego zbioru skończonego, np. zbioru liczb, liter, przedmiotów itp.; obecnie bardzo rozbudowana dyscyplina matematyczna badająca własności zbiorów skończonych; znajduje zastosowanie m.in. w teorii liczb, rachunku prawdopodobieństwa i informatyce. Stanowi jeden z działów matematyki dyskretnej.

Kombinatoryka zajmuje się zagadnieniami

• przeliczenia (określenia liczby elementów),

• wyliczenia (wypisania wszystkich elementów),

• optymalizacji

zbiorów skończonych.

Kombinatoryka posługuje się terminologią nie występującą w innych działach matematyki, stąd pozorna jej odrębność. Najważniejszym jej zadaniem jest konstruowanie spełniających pewne określone warunki odwzorowań jednego zbioru skończonego w drugi oraz znajdowanie wzorów na liczbę tych odwzorowań.

Zliczanie obiektów kombinatorycznych - funkcje i rozmieszczenia

Klasycznym problemem kombinatorycznym jest zadanie sformułowane następująco:

Dane są dwa zbiory skończone X i Y, przy czym
i
. Ile jest funkcji f: X→Y spełniających dane ograniczenia?

Inaczej problem ten można sformułować następująco:

• na ile sposobów można rozmieścić n obiektów (zbiór X - zbiór obiektów) w m pudełkach (zbiór Y - zbiór pudełek), y=f(x) określa numer pudełka dla obiektu x, albo

• na ile sposobów można pokolorować n obiektów (zbiór X - zbiór obiektów) m kolorami (zbiór Y - zbiór kolorów), y=f(x) określa kolor dla obiektu x.

Można przyjąć, że każdą funkcję f: X→Y, gdzie X={1,2,…,n} i Y={1,2,…,m} określamy jako ciąg wartości funkcji <f(1),f(2),…,f(n)>, co zapisujemy <y₁,y₂,…,y_n>.

Problem ten jest najprostszy jeżeli na rozmieszczenia nie nakładamy żadnych ograniczeń, ponieważ można udowodnić następujące twierdzenie:

Twierdzenie 1

Jeżeli
i
, to liczba wszystkich funkcji f: X→Y jest równa mⁿ.

Dowód

Przyjmując X={1,2,…,n} pytamy ile jest wszystkich ciągów <y₁,y₂,…,y_n> o wyrazach ze zbioru m elementowego Y.
Każdy wyraz możemy zapisać na m sposobów, co daje nam mm…m (n razy), czyli mⁿ.

Jeżeli ustalimy ograniczenie, że każde pudełko zawiera co najwyżej jeden obiekt to takie rozmieszczenia odpowiadają funkcjom różnowartościowym. Liczbę wszystkich funkcji różnowartościowych ze zbioru n-elementowego do zbioru m-elementowego oznaczamy przez [m]_n.

Twierdzenie 2

Jeżeli
,
i nm to liczba wszystkich funkcji różnowartościowych f: X→Y jest równa

[m]_n=m(m-1)(m-2)…(m-n+1),

przyjmujemy, że [m]₀=1.

Dowód

Przyjmując X={1,2,…,n} i nm, pytamy ile jest wszystkich różnowartościowych ciągów <y₁,y₂,…,y_n> o wyrazach ze zbioru m elementowego Y. Wyraz y₁ możemy zapisać na m sposobów, wyraz y₂ już tylko na m-1 sposobów, wyraz y₃ na m-2 sposoby itd. aż do wyrazu y_n który zapisuje się na m-(n-1) sposobów, co daje liczbę m(m-1)(m-2)…(m-n+1), czyli liczba wszystkich funkcji różnowartościowych wynosi [m]_n=m(m-1)(m-2)…(m-n+1).

Jeżeli n>m to [m]_n=0 i nie istnieje funkcja różnowartościowa
f: X→Y.

Jeżeli n=m, to każda funkcja różnowartościowa f: X→Y jest wzajemnie jednoznacznym odwzorowaniem zbioru X na zbiór Y, czyli jest bijekcją.

Twierdzenie 3

Jeżeli
i
, to liczba wszystkich bijekcji f: X Y jest równa

[n]_n=n(n-1)(n-2)…1 co oznaczamy przez n! (n silnia).

Dowód

Przyjmując
i
i podstawiając zamiast m, n do wzoru [m]_n=m(m-1)(m-2)…(m-n+1) otrzymujemy

[n]_n=n(n-1)(n-2)…1.

Jeżeli rozmieszczamy n obiektów w m pudełkach, przy czym każde pudełko zawiera ciąg (a nie jak poprzednio zbiór) obiektów, przy czym dwa rozmieszczenia uważa się za równe jeśli każde pudełko zawiera taki sam ciąg obiektów. Rozmieszczenia tego typu nazywa się rozmieszczeniami uporządkowanymi n obiektów w m pudełkach ich liczbę oznaczamy przez [m]ⁿ.

Twierdzenie 4

Liczba rozmieszczeń uporządkowanych n obiektów w m pudełkach wynosi

[m]ⁿ=m(m+1)…(m+n-1),

przyjmujemy, że [m]⁰=1.

Dowód

Konstruujemy rozmieszczenie uporządkowane przez kolejne dodawanie nowych obiektów. Pierwszy obiekt możemy rozmieścić na m sposobów, drugi na m+1 sposobów, gdyż można go umieścić w jednym z m-1 pustych pudełek lub w pudełku zawierającym pierwszy obiekt przed lub za tym obiektem. Ogólnie jeżeli zostało już rozmieszczone i-1 obiektów, przy czym dla k=1,2,…,m w k-tym pudełku znajduje się r_k obiektów, wtedy i-ty obiekt możemy dodać na r_k+1 sposobów do k-tego pudełka, co daje w sumie

(r₁+1)+(r₂+1)+…+(r_m+1)=(r₁+r₂+…+r_m)+m=i-1+m=m+i-1

możliwości. Wszystkich rozmieszczeń uporządkowanych jest więc [m]ⁿ=m(m+1)…(m+n-1).

Przykład

Rozmieścić dwa obiekty a, b w trzech pudełkach

Pudełko 1	Pudełko 2	Pudełko 3
a	b
a		b
b	a
b		a
	a	b
	b	a
ab
ba
	ab
	ba
		ab
		ba

[3]²=34=12.

Obiekty kombinatoryczne

Permutacje

Permutacją zbioru n-elementowego X nazywamy dowolną wzajemnie jednoznaczną funkcję f:X→X. Inaczej permutacją zbioru
n-elementowego X nazywamy dowolny różnowartościowy ciąg długości n o elementach ze zbioru X. Jeżeli upraszczając przyjmiemy, że X={1,2,…,n} to dowolną permutację f:X→X utożsamiać można z ciągiem <a₁,a₂,…,a_n>, gdzie a_i=f(i) dla i=1,2,…,n. Zbiór wszystkich permutacji tego zbioru oznaczamy przez P_n.

Na mocy twierdzenia 3 liczba wszystkich permutacji zbioru
n-elementowego X wynosi n!, czyli
.

Permutację zbioru n-elementowego X f:X→X, gdzie i=f(i) nazywamy permutacją identycznościową.

Kombinacje

Weźmy teraz pod uwagę skończony n-elementowy zbiór A,
każdy k-elementowy podzbiór zbioru A nazywamy k-elementową kombinacją bez powtórzeń zbioru n-elementowego, należy zauważyć, że kn. Liczbę wszystkich k-elementowych podzbiorów zbioru A oznaczamy przez
(n po k) i nazywamy współczynnikiem dwumiennym (współczynnikiem dwumianowym Newtona, symbolem Newtona).

Twierdzenie 5

Dowód

Każdy z [n]_k ciągów różnowartościowych długości k wyznacza podzbiór k-elementowy złożony z elementów występujących w tym ciągu, przy czym ten sam podzbiór A otrzymujemy z dokładnie k! ciągów, odpowiadających wszystkim permutacjom zbioru A.

Stąd
, korzystając teraz z twierdzenia 2 otrzymujemy

,

co przy zastosowaniu symbolu silni można zapisać w postaci

.

Dla skończonego n-elementowy zbióru A, można określić
k-elementowy podzbiór z powtórzeniami zbioru A, który nazywamy k-elementową kombinacją z powtórzeniami zbioru n-elementowego. Liczba wszystkich k-elementowych kombinacji z powtórzeniami zbioru n-elementowego A jest równa liczbie ciągów niemalejących długości k o elementach ze zbioru {1,2,…,n}, wynika to stąd, że elementy każdego podzbioru można jednoznacznie ustawić w ciąg niemalejący. Oznacza to, że liczba wszystkich k-elementowych kombinacji z powtórzeniami zbioru n-elementowego A wynosi

.

Wariacje

Każdy k-wyrazowy ciąg elementów n-elementowego zbioru A nazywamy k-elementową wariacją z powtórzeniami zbioru
n-elementowego. Na mocy twierdzenia 1 mamy, że liczba wszystkich k-wyrazowych wariacji z powtórzeniami zbioru
n-elementowego wynosi n^k.

Każdy k-wyrazowy ciąg różnych elementów n-elementowego zbioru A nazywamy k-elementową wariacją bez powtórzeń zbioru
n-elementowego. Na mocy twierdzenia 2 mamy, że liczba wszystkich k-wyrazowych wariacji bez powtórzeń zbioru n-elementowego wynosi [n]_k=n(n-1)…(n-k+1).

Tożsamości kombinatoryczne

1. [m]_n=(m-n+1)[m]_n-1

2. [m]_n=
   

3. [m]ⁿ=[m+n-1]_n

4. 
   symetria symbolu Newtona

5. 
   trójkąt Pascala

Tożsamości kombinatoryczne

6. 
   pochłanianie

7. 
   tożsamość Cauchy'ego

8. 
   , dla x, yR i nN.

Ponieważ liczba wszystkich podzbiorów zbioru n-elementowego A wynosi
, korzystając teraz ze wzoru dwumianowego mamy

,

czyli wyprowadziliśmy wzór na moc zbioru potęgowego P(A) skończonego n-elementowego zbioru A. Czyli
.

Zasada włączania -wyłączania

Zasada włączania - wyłączania pozwala znaleźć liczbę elementów zbioru A₁A₂…A_n, gdzie A_i (dla i=1,2,…,n) są zbiorami skończonymi. Sumę taką nazywamy sumą uogólnioną zbiorów A_i i oznaczamy przez
.

Proste przypadki zasady włączania i wyłączania:

Twierdzenie 6

Jeżeli n=2 to
.

Dowód

Jeżeli
oraz
i A₁A₂=, czyli
to liczba elementów zbioru A₁A₂ wynosi
-0 czyli
.

Jeżeli
oraz
i A₁A₂ oraz
to elementy wspólne liczone są w sumie
podwójnie i należy je odjąć czyli
.

Twierdzenie 7

Jeżeli n=3 to

Dowód

Wykorzystując twierdzenie 1 i prawo rozdzielności sumy i iloczynu zbiorów mamy:

A₁A₂A₃=(A₁A₂)A₃ co daje na mocy twierdzenia 1

oraz
i

co daje wzór

Uogólniając dla n można sformułować zasadę włączania - wyłączania następująco:

Zasada włączania-wyłączania

Aby wyznaczyć liczbę elementów zbioru
należy dodać do siebie liczności poszczególnych zbiorów A_i (włączanie), odjąć liczności wszystkich iloczynów zbiorów A_iA_j (wyłączanie), dodać liczności wszystkich iloczynów trzech zbiorów A_iA_jA_k (włączanie), odjąć liczności wszystkich iloczynów czterech zbiorów A_iA_jA_kA_l., itd.

Oznacza to że dodajemy liczności iloczynów nieparzystej liczby zbiorów a odejmujemy liczności iloczynów parzystej liczby zbiorów.

Można to zapisać następująco:

Podziały (rozkłady) zbioru

Podziałem (rozkładem) zbioru n - elementowego X na k bloków nazywamy dowolną rodzinę ={B₁, B₂,…, B_k} taką, że

1. B_i  , dla 1ik,

2. B₁B₂…B_k = X,

3. B_iB_j=.

Podzbiory B₁, B₂,…, B_k zbioru X nazywamy blokami podziału .

Zbiór wszystkich podziałów zbioru X na k bloków oznacza się _k(X), natomiast zbiór wszystkich podziałów przez (X). Zachodzą następujące własności:

(X)=₁(X)₂(X)…_k(X) oraz

zbiór {₁(X), ₂(X),…, _k(X)} jest podziałem zbioru (X).

Liczby Stirlinga drugiego rodzaju i pierwszego rodzaju

Liczbą Stirlinga drugiego rodzaju S(n,k) nazywamy liczbę podziałów zbioru n - elementowego na k bloków:

S(n,k)=
, gdzie
=n.

Przyjmujemy, że S(0,0)=1, gdyż pusta rodzina bloków jest podziałem zbioru pustego.

Przykład

Dla zbioru 4-elementowego X={1,2,3,4} mamy S(4,2)=7, ponieważ istnieją tylko następujące podziały zbioru X:

{{1,2,3}, {4}}, {{1,2,4}, {3}}, {{1,3,4}, {2}}, {{2,3,4}, {1}}, {{1,2}, {3,4}}, {{1,3}, {2,4}}, {{1,4}, {2,3}}.

Własności liczb Stirlinga drugiego rodzaju:

1. S(n,k)=0 dla k>n,

2. S(n, n) =1 dla n≥0,

3. S(n,0)=0 dla n>0,

4. S(n,1)=1 dla n>0,

5. S(n,k)=S(n-1,k-1)+kS(n-1,k) dla 0<k<n,

6. 
   , dla k>1,

7. 
   , dla n≥0,

8. 
   , dla n≥0.

Liczby Stirlinga drugiego rodzaju S(n,k)

n\k	2	3	4	5	6	7	8	9	10
2	1	0	0	0	0	0	0	0	0
3	3	1	0	0	0	0	0	0	0
4	7	6	1	0	0	0	0	0	0
5	15	25	10	1	0	0	0	0	0
6	31	90	65	15	1	0	0	0	0
7	63	301	350	140	21	1	0	0	0
8	127	966	1701	1050	266	28	1	0	0
9	255	3025	7770	6951	2646	462	36	1	0
10	511	9330	34105	42525	22827	5880	750	45	1

Liczbami Stirlinga pierwszego rodzaju s(n,k) nazywamy współczynniki przy kolejnych k-potęgach zmiennej x w wielomianie [x]_n, czyli

[x]_n=
.

Przyjmujemy, że s(0,0)=1.

Własności liczb Stirlinga pierwszego rodzaju:

1. s(n,k)=0 dla k>n,

2. s(n, n) =1 dla n≥0,

3. s(n,0)=0 dla n>0,

4. s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k) dla 0<k<n.

Liczby Stirlinga pierwszego rodzaju s(n,k)

n\k	1	2	3	4	5	6	7	8	9	10
2	-1	1	0	0	0	0	0	0	0	0
3	2	-3	1	0	0	0	0	0	0	0
4	-6	11	-6	1	0	0	0	0	0	0
5	24	-50	35	-10	1	0	0	0	0	0
6	-120	274	-225	85	-15	1	0	0	0	0
7	720	-1764	1624	-735	175	-21	1	0	0	0
8	-5040	13068	-13132	6769	-1960	322	-28	1	0	0
9	40320	-109584	118124	-67284	22449	-4536	546	-36	1	0
10	-362880	1026576	-1172700	723680	-269325	63273	-9450	870	-45	1

1-1

na

---