Info: coś podkreślone lub słowo moc - to powinno mieć 2 kreski nad sobą

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

S1 U … U Sn = S1 + … + Sn - S1∩S2 - … - Sn-1∩Sn + S1∩S2∩S3 + … Sn-2∩Sn-1∩Sn - S1∩S2∩S3∩S4 - …

Moc sumy mnogościowej zbioru S₁,…,S_n jest równa sumie mocy wszystkich przecięć nieparzystej liczby zbiorów minus suma mocy wszystkich przecięć parzystej liczby zbiorów.

2. Zasada rozmieszczania przedmiotów w pudełkach.

Jest (n + k - 1 / k - 1) sposobów rozmieszczenie n identycznych przedmiotów w k rozróżnialnych pudełkach.

3. Lemat o zliczaniu.

Jeżeli A,B- zbiory skończone fi: A -> B oraz Vb e B fi-1 = {a: fi(a) = b} ma tą samą ilość elementów to Bmoc = Amoc / fi(b)moc

4. Zasada szufladkowa Dirichleta.

Jeżeli skończony zbiór S jest podzielny na k podzbiorów, to co najmniej jeden z nich zawiera co najmniej ksi/k elementów.

5. Uogólniona zasada szufladkowa Dirichleta.

Niech A₁,…,A­_k c A , Amoc = n. Zakładamy, że każdy element a e A należy do co najmniej r zbiorów A_i. wtedy średnia arytmetyczna mocy zbiorów A_i jest równa co najmniej n*r / k.

6. Zliczanie podziałów uporządkowanych.

Dany jest zbiór A n elementów podzielony na podzbiory A₁,…,A_k, gdzie A_i ma n_i elementów, n=n₁+…+n_k. Podział elementów zbioru A między A₁,…,A_k nazywamy podziałem uporządkowanym. Ilość podziałów uporządkowanych j.w. wynosi n! / n1! .. nk!

7. Definicja elementów nierozróżnialnych i podziału uporządkowanego zbioru.

8. Definicja grafu skierowanego.

Graf skierowany G = struktura złożona z:

- zbioru wierzchołków V(G);

-zbioru krawędzi E(G);

-funkcji y: E(G) -> V(G) x V(G)

Dla każdej krawędzi istnieje przypisana do niej para wierzchołków w (początek i koniec).

9. Macierz sąsiedztwa.

W teorii grafów macierz sąsiedztwa grafu G jest kwadratową macierzą w której a_ij oznacza liczbę krawędzi pomiędzy wierzchołkami i i j. W przypadku grafów prostych macierz sąsiedztwa jest macierzą zerojedynkową z zerami na głównej przekątnej. Dla grafów nieskierowanych macierz sąsiedztwa jest z definicji symetryczna.

10. Definicja drogi w grafie skierowanym.

Drogą z wierzchołka U do wierzchołka V nazywamy taki ciąg krawędzi (e1 ... en), że początek e₁=U, koniec e_n=V oraz Vi początek e_i=koniec e_i-1.

---