md03fizA.pdf

(339 KB) Pobierz
27316419 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 61
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
27316419.033.png 27316419.034.png 27316419.035.png 27316419.036.png 27316419.001.png 27316419.002.png 27316419.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 61
x 1 +...+x k =n.
Dlatego
Powr ó t
n−1
k−1
k!·P(n,k)
.
Pe“nyekran
Zamknij
Koniec
27316419.004.png 27316419.005.png 27316419.006.png 27316419.007.png 27316419.008.png 27316419.009.png 27316419.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 61
k
2
x 1 +...+x k =n+
.
Powr ó t
Dlatego
n+ k 2 −1
k−1
k!·P(n,k)
.
Pe“nyekran
Zamknij
Koniec
27316419.011.png 27316419.012.png 27316419.013.png 27316419.014.png 27316419.015.png 27316419.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 61
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
27316419.017.png 27316419.018.png 27316419.019.png 27316419.020.png 27316419.021.png 27316419.022.png 27316419.023.png 27316419.024.png 27316419.025.png 27316419.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 61
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
@
@
@
@
@
@
@
@
27316419.027.png 27316419.028.png 27316419.029.png 27316419.030.png 27316419.031.png 27316419.032.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin