md06matA.pdf

(624 KB) Pobierz
36200756 UNPDF
Stronag“ ó wna
Przyk“ad1: zliczanienieporz¡dk ó w
Stronatytu“owa
Spistre–ci
Definicja2.13. Nieporz¡dkiemwzbiorze{1,...,n}nazywamytak¡per-
mutacjƒfzbioru{1,...,n},»e
JJ II
f(i)6=i
dlaka»degoi=1,...,n.Zbi ó rwszystkichnieporz¡dk ó ww{1,...,n}oznaczamy
przezD n .
J I
Strona 69 z 111
Twierdzenie2.14. Dlan1
X
(−1) i
Powr ó t
|D n |=n!
i! .
i=0
Pe“nyekran
Zamknij
Koniec
n
36200756.028.png 36200756.029.png 36200756.030.png 36200756.031.png 36200756.001.png 36200756.002.png
Stronag“ ó wna
Dow ó d.Niech
A i ={f2S n :f(i)=i},i=1,...,n.
Stronatytu“owa
Mamy
|D n |=|S n |− A 1 [...[A n =n!−
X
(−1) i−1 X
1p 1 <p 2 <...<p i n
Spistre–ci
|A p 1 \A p 2 \...\A p i |.
i=1
JJ II
Zauwa»my,i»
|A p 1 \A p 2 \...\A p i |=(n−i)!
J I
Istniejedok“adnie n i ci¡g ó w(p 1 ,...,p i )takich,»e1p 1 <p 2 <...<p i n.
Dlatego
Strona 70 z 111
X
n
(−1) i−1 n
X
n
(−1) i n!
X
(−1) i
|D n | =n!−
(n−i)!=n!+
i! = n!
i! .
Powr ó t
i
i=1
i=1
i=0
Pe“nyekran
Wniosek2.15.
D n
n! = 1
lim
n!1
e .
Zamknij
Koniec
n
n
36200756.003.png 36200756.004.png 36200756.005.png 36200756.006.png 36200756.007.png 36200756.008.png
Przyk“ad2: zliczaniesurjekcji
Stronag“ ó wna
Stronatytu“owa
Twierdzenie2.16. NiechX={x 1 ,...,x n },Y={y 1 ,...,y m },|X|=n,
|Y|=m.Mamy
(−1) i m
(m−i) n .
Spistre–ci
X
|Surj(X,Y)|=
i
i=0
JJ II
J I
Dow ó d.Niech
A i = f2Y X :y i /2f(X) ,i=1,...,m.
Strona 71 z 111
Mamy
Y X \Surj(X,Y)=A 1 [...[A m ,
Powr ó t
sk¡d
|Surj(X,Y)|= Y X −|A 1 [...[A m |=
Pe“nyekran
X
m
(−1) i−1 X
1p 1 <p 2 <...<p i m
=m n −
|A p 1 \A p 2 \...\A p i |.
Zamknij
i=1
Koniec
m−1
36200756.009.png 36200756.010.png 36200756.011.png 36200756.012.png 36200756.013.png 36200756.014.png
Stronag“ ó wna
Zauwa»my,i»
A p 1 \A p 2 \...\A p i =(Y\{y p 1 ,...,y p i }) X ,
Stronatytu“owa
sk¡d |A p 1 \A p 2 \...\A p i |=(m−i) n
idlatego
Spistre–ci
(−1) i−1 m
(−1) i m
(m−i) n .
JJ II
X
X
|Surj(X,Y)| =m n −
(m−i) n =
i
i
i=1
i=0
J I
Wniosek2.17. n
m
Strona 72 z 111
(−1) i m
(m−i) n .
= 1
X
m!
i
i=0
Powr ó t
Dow ó d.Twierdzenia 1.5 i 2.16 .
Pe“nyekran
Zamknij
Koniec
m
m−1
m−1
36200756.015.png 36200756.016.png 36200756.017.png 36200756.018.png 36200756.019.png 36200756.020.png
Przyk“ad3: funkcjaEulera
Stronag“ ó wna
LeonhardEULER(1707-1783)
FunkcjƒEulera : N ! N okre–lasiƒnastƒpuj¡co
Stronatytu“owa
(n)=ilo–¢liczbwzglƒdniepierwszychznimniejszychodn.
Ustalmy n .Niech
Spistre–ci
n=p w 1
1 ·...·p w q
q ,
gdziep i s¡r ó »nymiliczbamipierwszymi,w j 1,j=1,...,q.
JJ II
A i df = n s2{1,...,n}:p i |s o ,i=1,...,q.
J I
Mo»nazauwa»y¢,»e
Strona 73 z 111
A i 1 \...\A i k = n
p i 1 ·...·p i k
Powr ó t
idlatego
(n) =n− A 1 [...[A q =n−
X
(−1) k−1 X
1i 1 <i 2 <...<i k q
Pe“nyekran
|A i 1 \...\A i k |=
k=1
.
X
(−1) k X
1i 1 <i 2 <...<i k q
n
1− 1
1− 1
Zamknij
=n+
p i 1 ·...·p i k = n
·...·
p 1
p q
k=1
Koniec
q
q
36200756.021.png 36200756.022.png 36200756.023.png 36200756.024.png 36200756.025.png 36200756.026.png 36200756.027.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin