Na dzisiejszych zajęciach zajmiemy się zliczaniem funkcji. Funkcja to inaczej przekształcenie zbioru X w zbiór Y. Przyjmijmy takie oznaczenia. Niech X i Y będą zbiorami skończonymi, oraz niech |X| = n, |Y| = m (liczność zbiorów). Fun(X, Y) oznacza zbiór wszystkich funkcji X w Y, a |Fun(X, Y)| liczbę wszystkich funkcji X w Y. Oznaczenia te będą przydatne dla nas przy twierdzeniach.

Twierdzenie 2.1

|Fun(X, Y)| =

W szczególnym przypadku dla |Y| = 2 mamy Fun(X, Y) =
. Jeśli mamy zbiór ciągów 0, 1 długości n, czyli
, to
. Przyjmijmy kolejne oznaczenie. Niech Inj(X, Y) będzie zbiorem injekcji (funkcji różnowartościowych) zbioru X w Y.

Twierdzenie 2.2

Dla
mamy
.
jest tak zwaną potęgą ubywająca. Ponadto
.

Załóżmy, że mamy sytuację, że
, a
. Wówczas
, co znaczy, że taka funkcja nie jest injekcją. Injekcja jest bowiem relacją przyporządkowująca jednemu elementowi zbioru A jeden i tylko jeden element zbioru B. Przyjmijmy kolejne oznaczenie. Niech Sur(X, Y) będzie zbiorem surjekcji (funkcji na) zbioru X na zbiór Y. Surjekcja to odwzorowanie zbioru A na zbiór B - takie, że każdy element zbioru B przyporządkowany jest co najmniej jednemu elementowi zbioru A.

Twierdzenie 2.3

Dla
mamy:
.

Powyższy wzór jest związany z postacią liczb Stirlinga drugiego rodzaju. I następne z oznaczeń. Niech |X| = |Y| = n. Wtedy przez Bij(X, Y) oznaczamy zbiór bijekcji (funkcji różnowartościowych) zbioru X na zbiór Y.

Twierdzenie 2.4

Niech |X| = |Y| = n. Wtedy: |Bij(X, Y)| = n! Jeśli X = Y, to wtedy oznaczamy Bij(X, X) = Bij(X) i jest to zbiór permutacji zbioru X.

Przy okazji powyższego twierdzenia istnieje wzór Stirlinga na przybliżone obliczanie silni. Robimy to korzystając z poniższego wzoru:

. Przykładowo 100! W przybliżeniu wynosi
.

Przejdźmy teraz do rozmieszczeń uporządkowanych i przyjmijmy kolejne oznaczenie. Załóżmy, że mamy n obiektów i m pudełek. Uwzględniamy kolejność rozmieszczania obiektów w pudełkach. Oznaczenie:
nazywamy entą potęgą przyrastającą liczby n.

Twierdzenie 2.5

Liczba wszystkich rozmieszczeń uporządkowanych n obiektów w m pudełkach jest równa
i mamy związek, że
.

Przejdźmy teraz do zagadnienia związanego z podzbiorami zbiorów. Niech
. Oznaczmy P(X) wszystkich podzbiorów w zbiorach X. Wtedy liczba wszystkich podzbiorów zbioru X równa jest
. Rozpatrzmy teraz podzbiory k elementowe zbiorów. Niech |X| = n, oraz
. Oznaczmy przez
liczbę podzbiorów (kombinacji) k elementowych zbioru X

Twierdzenie 2.6

Symbol dwumianowy Newtona oznaczamy, jako:

Ponadto istnieje wzór:

, gdzie
to współczynniki dwumianowe.

Współczynniki dwumianowe spełniają szerego tożsamości. Oto kilka z nich:

- Na tej równości opiera się konstrukcja trójkąta Pascala

Przejdżmy teraz do współczynników wielomianowych i przyjmijmy takie oznaczenie. Mamy n obiektów i m pudełek, oraz dane są liczby naturalne
. Liczbę wszystkich różnych rozmieszczeń n obiektów w m pudełkach przy założeniu, że w itym pudełku dla i od 1 do m znajduje się dokładnie
obiektów oznaczamy:
.

Twierdzenie 2.7

. Dla m = 2,
mamy:

Omówmy teraz zasadę włączeń i wyłączeń. Dany jest zbiór skończony X oraz rodzina
jego podzbiorów. Problem polega na wyznaczaniu ilości sumy zbiorów
, gdy znamy liczności wszystkich części wspólnych rodziny A. Robimy to tak:

dla indeksów

Twierdzenie 2.8

I to tyle, jeśli chodzi o ważniejsze twierdzenia. Kolejna rzecz, o jakiej powiemy to zasada szufladkowa Dirichleta. Jeśli rozmieścimy n obiektów w m szufladkach oraz n > m, to co najmniej jedna szuflada musi zawierać więcej niż 1 element. Kolejna zasada, to zasada uogólniona. Niech X i Y to zbiory skończone. Niech
, oraz |X| > r |Y| dla pewnej liczby rzeczywistej r > 0. Wtedy co najmniej jeden ze zbiorów
zawiera więcej niż r elementów. Używamy oznaczenia i mówimy, że
jest przeciwobrazem elementu
.

---