dyskretna
matdys: Witam, mam parę zadań do obliczenia z kombinatoryki. Problem jest taki, że nie jestem w stanie
rozszyfrować wszystkich zagadnień.
Otóż, polecenie brzmi następująco:
Podaj wartość:
| | | |
a) | − UWAGA! Zamiast nawiasów okrągłych są klamrowe. Nie wiedziałem jak to zapisać. |
| | |
b) P(5,2) − tutaj domyślam się, że jest to podział liczby?
c) N(5,3) − Symbol Newtona jak mniemam.
10 cze 12:36
10 cze 12:38
Mila:
No to musisz znać treść zadań, bo inaczej nie można pomóc.
a) mają byc takie nawiasy?:
[...] jeżeli tak, to liczby Stirlinga I rodzaju.
Jeżeli:
{..} to liczby Stirlinga II rodzaju
b) P(5,2) − podział liczby 5 na dwa składniki
| | n | |
P(n,2)=[ |
| ] cecha liczby |
| | 2 | |
Możesz to zrobić na piechotę:
5=1+4
5=2+3
Dla większej liczby składników to np. rekurencja
c) symbol Newtona chyba znasz z LO
10 cze 19:11
matdys: Właśnie problem taki, że treść zadania taką jaką padałem. Co do P(n,k), to faktycznie to
podział liczby. Znalazłem w notatkach. Dzięki. To liczby Stirligna.
11 cze 20:30
matdys: Jeśli dobrze rozumiem liczby stirlinga to...
{4 nad 3} = 7?
11 cze 20:45
Mila:
Liczby Stirlinga II rodzaju:
S
2(n,k)=S
2(n−1,k−1)+k*S
2(n−1,k)
S
2(4,3)=S
2(3,2}+3*S
2(3,3)=
11 cze 21:26
matdys: ja sobie rozpisywałem zbiory i pewnie dlatego coś źle wyszło.. mogłabyś jeszcze tylko
powiedzieć skąd potem nagle bierze się ułamek?
11 cze 21:48
jc: Dla tak małych liczb można wszystko wypisać:
a bcd
b acd
c abd
d abc
ab cd
ac bd
ad bc
Rzem 7.
11 cze 21:55
matdys: @jc
czyli w końcu ile? 6, czy 7?
11 cze 21:58
Mila:
S(4,3)=6
S(4,2)=7
Liczba podziałów zbioru n różnych elementów na dwa niepuste podzbiory ( nie jest ważna
kolejność):
JC wypisał podziały na dwa podzbiory, to masz ich 7.
Liczba podziałów zbioru n różnych elementów na 3 niepuste podzbiory trzeba liczyć wg podanego
wzoru
21:26 albo przez wyłączanie.
Na 4 niepuste podzbiory raczej trzeba stosować wzór, zależy ile elementów masz w zbiorze.
Możesz też wypisać.
{a,b,c,d}
{a},{b},{c,d}
{a,b}, {c},{d}
{a,c},{b},{d}
{a,d},{b},{c}
{b,c}, {a},{d}
{b,d},{c},{a}
Jednak powinieneś umieć obliczyć.
Na pewno masz to w notatkach z wykładów.
11 cze 22:14
matdys: no właśnie nie bardzo. Jedynie co mam to:
{n nad m} to liczba wszystkich podziałów zbioru X na m bloków. Zbior Surj(X,Y) wszystkich
surjekcji f: X −> Y ma {n nad m} * m! i do tego dowód.. To wszystko..
11 cze 22:28
Mila:
To możesz też obliczyć liczbę suriekcji i podzielić przez k! (k− liczba podzbiorów)
Masz wzór na liczbę suriekcji?
11 cze 22:31
11 cze 22:36
11 cze 22:51
Mila:
To jest właśnie ten wzór, który podałam 21:26.
S(n,k)=S(n−1,k−1)+k*S(n−1,k)
Własności:
1)
S(n,0)=0
S(n,n)=1
S(n,1)=1
Warto zapamiętać:
| | 2n−2 | |
S(n,2)= |
| − liczba podziałów n różnych obiektów na dwa niepuste podzbiory. |
| | 2 | |
Liczba suriekcji:
f:{x
1,x
2,...x
n}→{y
1,y
2...y
k}
k<n
k!*S(n,k)
k=n
Liczba suriekcji : n!
Wyprowadź wg wzoru : S(4,2),S(5,2) to zrozumiesz.
11 cze 22:52
matdys: S(5,2) = 11?
11 cze 23:00
jc: = 15
11 cze 23:02
11 cze 23:07
matdys: ktos jest wstanie zweryfikować błąd?
11 cze 23:28
Mila:
Brak nawiasów
S(5,2)=S(4,1)+2*S(4,2)=
=1+2*[S(3,1)+2*S(3,2)]=
=1+2*[1+2*
(S(2,1)+2*S(2,2)
) ]=
=1+2*[1+2*(1+2*1)]=
=1+2*[1+6]=15
Widzisz, że dobrze jest zapamiętać wzór:
11 cze 23:35
matdys: No dobra, ale jak mamy np. S2(5,4) to wzór już nie ma miejsca bytu.
11 cze 23:40
Mila:
Tak napisałam wcześniej .
S(5,4) trzeba liczyć.
Podam tabelę , gdzie jest policzone, to sobie sprawdzisz.
11 cze 23:42
11 cze 23:46
matdys: Dobra, wyszło 10.
11 cze 23:46
Mila:
Dobrze.
11 cze 23:46
matdys: Okey, dzięki.
11 cze 23:47
Mila:
Powodzenia.
11 cze 23:47
http://prntscr.com/bf7ui7
