md03fiz.pdf

(269 KB) Pobierz
28423217 UNPDF
Przyk“ad
Nailesposob ó wmo»nazap“aci¢zazakupwarto–ci73$,
dysponuj¡cpojedynczyminomina“ami:1$,2$,3$,5$,10$,15$,20$,50$?
Stronag“ ó wna
Stronatytu“owa
Niech F(n 1 ,...,n m ;N)
Spistre–ci
oznaczaliczbƒsposob ó wzap“atykwotyNpojedynczyminomina“amiowarto–-
ciachn 1 ,...,n m .Mamyzwi¡zek
JJ II
F(n 1 ,...,n m ;N)=F(n 1 ,...,n m−1 ;N−n m )+F(n 1 ,...,n m−1 ;N).
J I
z }| {
F(1,2,3,5,10,15,20;73)=
=F(1,2,3,5,10,15;3)+F(1,2,3,5,10,15;23)=...
0
F(1,2,3,5,10,15,20,50;73)=F(1,2,3,5,10,15,20;23)+
Strona 37 z 53
F(1,2,3,5,10,15;3)=F(1,2,3;3)=2
Powr ó t
z }| {
F(1,2,3,5,10;23)=
=F(1,2,3,5;8)=F(1,2,3;3)+ F(1, 2, 3;8 )
0
F(1,2,3,5,10,15;23)=F(1,2,3,5,10;8)+
Pe“nyekran
| {z }
0
=2
...=2+2= 4
Zamknij
73=50+20+3=50+20+2+1=50+15+5+3=50+15+5+2+1.
Koniec
28423217.033.png 28423217.034.png 28423217.035.png 28423217.036.png 28423217.001.png 28423217.002.png 28423217.003.png
Stronag“ ó wna
Stronatytu“owa
Asymptotycznaw“asno–¢liczbP(n,k)
Spistre–ci
Lemat1.32.
n−1
k−1
} P(n,k)
n+ k 2 −1
k−1
.
1
1
JJ II
~
k! ·
k! ·
J I
Dow ó d}.Ka»dypodzia“(a 1 ,...,a k )liczbyngeneruje najwy»ej k!rozwi¡za«
r ó wnaniadiofantycznego
Strona 38 z 53
x 1 +...+x k =n.
Dlatego
Powr ó t
n−1
k−1
k!·P(n,k)
.
Pe“nyekran
Zamknij
Koniec
28423217.004.png 28423217.005.png 28423217.006.png 28423217.007.png 28423217.008.png 28423217.009.png 28423217.010.png
Stronag“ ó wna
Dow ó d~.Istniejejednoznacznaodpowiednio–¢miƒdzypodzia“ami(a 1 ,...,a k )
liczbyna podzia“ami(b 1 ,...,b k )liczby
k
2
Stronatytu“owa
n+
Spistre–ci
or ó »nychsk“adnikach .Rzeczywi–cie,podstawiamy
b i =a i +(k−i),i=1,...,k;
JJ II
k
2
b 1 +...+b k =a 1 +...+a k +(k−1)+...+1=n+ k(k−1)
2 =n+
.
J I
Ka»dypodzia“(b 1 ,...,b k )generujedok“adniek!rozwi¡za«r ó wnania
Strona 39 z 53
k
2
x 1 +...+x k =n+
.
Powr ó t
Dlatego
n+ k 2 −1
k−1
k!·P(n,k)
.
Pe“nyekran
Zamknij
Koniec
28423217.011.png 28423217.012.png 28423217.013.png 28423217.014.png 28423217.015.png 28423217.016.png
Twierdzenie1.33.
Stronag“ ó wna
P(n,k)
n k−1 = 1
lim
n!1
k!(k−1)! .
Stronatytu“owa
Dow ó d.
n−1
k−1
n−1
n
k−1
Spistre–ci
1
= 1
· (n−1) k − 1
n k−1 k! ·
k!(k−1)! ·
(n−1) k−1 =
n−1
n
k−1
JJ II
= 1
1− 1
1− k−2
! 1
k!(k−1)! ·
·
n−1
·...·
n−1
k!(k−1)!
| {z }
&1
| {z }
&1
| {z }
&1
J I
Podobniepokazujemy,»e
Strona 40 z 53
n+ k 2 −1
k−1
n k−1 k! ·
1
! 1
k!(k−1)! .
Powr ó t
Zlematu 1.32 iztwierdzeniaotrzechci¡gach
Pe“nyekran
P(n,k)
n k−1 ! 1
k!(k−1)! .
Zamknij
Koniec
28423217.017.png 28423217.018.png 28423217.019.png 28423217.020.png 28423217.021.png 28423217.022.png 28423217.023.png 28423217.024.png 28423217.025.png 28423217.026.png
Stronag“ ó wna
Stronatytu“owa
Spistre–ci
Twierdzenie1.34.
P(n,k)=P k (n).
JJ II
Ideadowodunatzw. diagramachFerrersa .
J I
n=14, k=5
a 1 =6 ~~~~~~
~~~
Strona 41 z 53
a 2 =3
a 3 =2
a 1 +a 2 +a 3 +a 4 +a 5 =14
~~
Powr ó t
a 4 =2
~~
@
a 5 =1
~
@
@
~ b 1 =5
b 2 =4
b 3 =2
b 4 =1
b 5 =1
b 6 =1
@
~
~
~
~
Pe“nyekran
@
@
~
~
~
~
@
@
~
~
@
@R@
~
Zamknij
b 1 +b 2 +b 3 +b 4 +b 5 +b 6 =14
~
~
Koniec
@I
@
@
@
@
@
@
@
@
28423217.027.png 28423217.028.png 28423217.029.png 28423217.030.png 28423217.031.png 28423217.032.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin