Kombinatoryka i matematyka dyskretna

Cała kombinatoryka pierwszego roku to odpowiedź na dwa pytania: czy kolejność ma znaczenie i czy wolno powtarzać. Reszta — trójkąt Pascala, zasada włączeń i wyłączeń, rekurencje — wynika z tych dwóch. Każda liczba w tym module jest sprawdzana przez wyliczenie: aplikacja generuje obiekty i je zlicza, zamiast tylko podstawiać do wzoru.

n! · nᵏ · C(n,k)

Zliczanie

Pięć podstawowych schematów naraz, z drzewem wyboru i kontrolą przez wyliczenie

kolejność? powtórzenia?

C(n,k)

Trójkąt Pascala

Tożsamość Pascala z podświetlonymi rodzicami, sumy wierszy i fraktal Sierpińskiego mod 2

C(n,k) = C(n−1,k−1) + C(n−1,k)

|A∪B∪C|

Włączenia i wyłączenia

Konkretne liczby 1…N i podzielność przez 2, 3, 5 — wzór kontra bezpośrednie zliczenie

Σ|Aᵢ| − Σ|Aᵢ∩Aⱼ| + …

aₙ = f(aₙ₋₁, …)

Rekurencje

Fibonacci i złota proporcja, wieża Hanoi z faktycznym generowaniem ruchów

Fₙ₊₁/Fₙ → φ, Hₙ = 2ⁿ−1

Σ deg(v) = 2|E|

Grafy

Stopnie wierzchołków, lemat o uściskach dłoni, drzewo rozpinające i składowe

|E| = |V| − 1 dla drzewa

δ(q, a) → q′

Automaty i sieci Petriego

Automat sprawdzony przeglądem wszystkich słów, sieć Petriego z pełną analizą osiągalności

wzajemne wykluczanie dowiedzione

ZADANIA

Przykłady krok po kroku

Wybór komisji, włączenia-wyłączenia, rozwiązanie rekurencji Fibonacciego

3 rozwiązane zadania

Pięć schematów zliczania

Wszystko sprowadza się do dwóch pytań: czy kolejność ma znaczenie i czy wolno powtarzać elementy.

wariacje z powt.: nᵏ
wariacje bez powt.: n!/(n−k)!
permutacje: n!
kombinacje: C(n,k)
kombinacje z powt.: C(n+k−1, k)

n (rozmiar zbioru) 5

k (rozmiar wyboru) 3

wariacje z powtórzeniami nᵏ–

wariacje bez powtórzeń–

kombinacje C(n,k)–

kombinacje z powtórzeniami–

permutacje n!–

drzewo wyboru (pierwsze poziomy)

porównanie schematów (skala logarytmiczna)

Trójkąt Pascala

Każdy element to suma dwóch nad nim — i to jest cały dowód wzoru dwumianowego.

C(n,k) = C(n−1,k−1) + C(n−1,k)
Σₖ C(n,k) = 2ⁿ

liczba wierszy 14

n (wiersz) 7

k (pozycja) 3

Kolorowanie

C(n,k)–

C(n−1,k−1) + C(n−1,k)–

suma wiersza n = 2ⁿ–

suma naprzemienna Σ(−1)ᵏC(n,k)–

kliknij komórkę, żeby ją wybrać

Zasada włączeń i wyłączeń

|A∪B∪C| = |A|+|B|+|C|
− |A∩B| − |A∩C| − |B∩C|
+ |A∩B∩C|

Dodajemy pojedyncze zbiory, ale wtedy części wspólne policzyliśmy dwukrotnie — odejmujemy je; wtedy część potrójna zniknęła zupełnie — dodajemy z powrotem.

zakres liczb 1 … N 120

dzielnik a 2

dzielnik b 3

dzielnik c 5

|A|+|B|+|C|–

− pary–

+ trójka–

wynik ze wzoru–

bezpośrednie zliczenie–

diagram Venna z faktycznymi licznościami

Relacje rekurencyjne

Fₙ = Fₙ₋₁ + Fₙ₋₂, F₁ = F₂ = 1
Fₙ = (φⁿ − ψⁿ)/√5 (wzór Bineta)

Hₙ = 2·Hₙ₋₁ + 1, H₀ = 0
Hₙ = 2ⁿ − 1

Rekurencja opisuje, jak rośnie ciąg; wzór jawny mówi, jak szybko.

n (Fibonacci) 10

liczba krążków w wieży Hanoi 4

ruch nr 0

Fₙ–

Fₙ ze wzoru Bineta–

Fₙ₊₁/Fₙ (→ φ = 1,618…)–

ruchów Hanoi: 2ⁿ − 1–

faktycznie wygenerowanych ruchów–

Fibonacci: wartości i iloraz kolejnych wyrazów

wieża Hanoi po wybranej liczbie ruchów

Grafy: stopnie, drzewo rozpinające, składowe

Σ_{v} deg(v) = 2·|E| (lemat o uściskach dłoni)
drzewo: spójny i |E| = |V| − 1

Suma stopni liczy każdą krawędź dwa razy — stąd natychmiastowy wniosek, że wierzchołków nieparzystego stopnia jest parzyście wiele.

Graf

liczba wierzchołków 8

gęstość (dla grafu losowego) 0.35

|V| / |E|–

Σ deg(v)–

Σ deg(v) = 2|E| ?–

wierzchołków nieparzystego stopnia–

składowe spójności–

krawędzi w lesie rozpinającym–

graf; grubsze krawędzie = las rozpinający (BFS)

Automaty i sieci Petriego

Widok

Automat deterministyczny czyta słowo litera po literze i po każdej przechodzi do stanu wskazanego przez funkcję przejścia δ(q, a). Słowo jest akceptowane, gdy po ostatniej literze automat stoi w stanie akceptującym (podwójne kółko).

Język

Słowo wejściowe (litery a, b)

Przeczytane litery 0

Przykład 1 — komisja z ograniczeniem

Z grupy 7 kobiet i 5 mężczyzn wybieramy 4-osobową komisję. Ile jest komisji zawierających co najmniej jedną kobietę i co najmniej jednego mężczyznę?

1. Wszystkich komisji: C(12,4) = 12·11·10·9/(4·3·2·1) = 11880/24 = 495.
2. Komisje bez mężczyzn (same kobiety): C(7,4) = 7·6·5·4/24 = 840/24 = 35.
3. Komisje bez kobiet (sami mężczyźni): C(5,4) = 5.
4. Te dwa zbiory są rozłączne (komisja nie może być jednocześnie samymi kobietami i samymi mężczyznami), więc odejmujemy je bez poprawek:
495 − 35 − 5 = 455.
5. Kontrola przez rozbicie na przypadki (k kobiet, 4−k mężczyzn), k = 1,2,3:
C(7,1)C(5,3) + C(7,2)C(5,2) + C(7,3)C(5,1) = 7·10 + 21·10 + 35·5 = 70 + 210 + 175 = 455 ✓
6. Morał: liczenie „dopełnienia” bywa krótsze niż sumowanie przypadków — ale zawsze warto policzyć drugą metodą. Zakładka „Zliczanie” pokazuje C(12,4) = 495 i weryfikuje tę liczbę, generując wszystkie podzbiory dla małych n.

Przykład 2 — ile liczb z 1…1000 nie dzieli się przez 2, 3 ani 5?

1. Niech A, B, C to zbiory liczb podzielnych odpowiednio przez 2, 3, 5 w zakresie 1…1000.
2. Pojedyncze: |A| = ⌊1000/2⌋ = 500, |B| = ⌊1000/3⌋ = 333, |C| = ⌊1000/5⌋ = 200.
3. Pary (podzielność przez iloczyn, bo dzielniki są parami względnie pierwsze):
|A∩B| = ⌊1000/6⌋ = 166, |A∩C| = ⌊1000/10⌋ = 100, |B∩C| = ⌊1000/15⌋ = 66.
4. Trójka: |A∩B∩C| = ⌊1000/30⌋ = 33.
5. Włączenia i wyłączenia:
|A∪B∪C| = (500+333+200) − (166+100+66) + 33 = 1033 − 332 + 33 = 734.
6. Szukana liczba to dopełnienie: 1000 − 734 = 266.
7. Kontrola „gęstościowa”: udział liczb niepodzielnych przez 2, 3, 5 to (1−1/2)(1−1/3)(1−1/5) = (1/2)(2/3)(4/5) = 4/15 ≈ 0,2667, czyli ok. 267 z 1000 — zgadza się z dokładnym wynikiem 266 (różnica bierze się z zaokrągleń podłogi). Zakładka „Włączenia i wyłączenia” liczy obie strony i porównuje je z bezpośrednim przelicieniem wszystkich N liczb.

Przykład 3 — rozwiązanie rekurencji Fₙ = Fₙ₋₁ + Fₙ₋₂

1. Szukamy rozwiązań postaci Fₙ = rⁿ. Podstawiając: rⁿ = rⁿ⁻¹ + rⁿ⁻², dzielimy przez rⁿ⁻² (r ≠ 0) i dostajemy równanie charakterystyczne r² = r + 1, czyli r² − r − 1 = 0.
2. Pierwiastki: r = (1 ± √5)/2. Oznaczamy φ = (1+√5)/2 ≈ 1,6180 oraz ψ = (1−√5)/2 ≈ −0,6180.
3. Rozwiązanie ogólne: Fₙ = A·φⁿ + B·ψⁿ.
4. Warunki początkowe F₀ = 0, F₁ = 1 dają układ:
A + B = 0 ⇒ B = −A;
Aφ + Bψ = 1 ⇒ A(φ − ψ) = 1. Ponieważ φ − ψ = √5, mamy A = 1/√5.
5. Wzór Bineta: Fₙ = (φⁿ − ψⁿ)/√5.
6. Zaskakujący wniosek: wyrażenie z trzema niewymiernościami daje dla każdego n liczbę całkowitą. Co więcej |ψ| < 1, więc ψⁿ → 0 i dla n ≥ 1 zachodzi Fₙ = zaokrąglenie(φⁿ/√5). Stąd też Fₙ₊₁/Fₙ → φ — widać to na zakładce „Rekurencje”, gdzie iloraz jest liczony na żywo.
7. Ta sama metoda działa dla wieży Hanoi: Hₙ = 2Hₙ₋₁ + 1 to rekurencja niejednorodna; rozwiązanie jednorodne to C·2ⁿ, szczególne (stałe) to −1, więc Hₙ = C·2ⁿ − 1, a z H₀ = 0 wychodzi C = 1, czyli Hₙ = 2ⁿ − 1.