matematyka dyskretna ZawistuS: Hej, mógł bym prosić o pomoc? Mam problemy z takimi zadaniami Zadanie 1. Siedem cukierków { a, b, 1, 2, 3, 4, 5 } wkładamy do 3 identycznych pudełek. W każdym pudełku musi być przynajmniej jeden cukierek. Muszą być spełnione oba poniższe warunki: [w1] a i b nie mogą się znaleźć razem w jednym pudełku; [w2] ani a, ani b nie mogą być same w pudełku. Ile jest takich podziałów? Zadanie 2. Ile jest podziałów liczby 20 na 8 składników?

wredulus_pospolitus: 1) a jest w jakimś pudełku b jest w innym pudełku pozostałe 5 cukierków rozdzielamy na 3 pudełka, z czego po jednym musimy dołożyć do każdego z pudełek, więc jakie mamy opcje: a) mamy {a + 3 cukierki}, {b + 1 cukierek} , {1 cukierek} b) mamy {a + 2 cukierki}, {b + 2 cukierki} , {1 cukierek} c) mamy {a + 2 cukierki}, {b + 1 cukierek} , {2 cukierki} d) mamy {a + 1 cukierek}, {b + 1 cukierek} , {3 cukierki} e) mamy {a + 1 cukierek}, {b + 2 cukierki} , {2 cukierki} f) mamy {a + 1 cukierek}, {b + 3 cukierki} , {1 cukierek} policz ile możliwości jest dla każdego z tych przypadków

Mila: 2) Podział liczby na k składników; P(n,k) na pewno masz wzór rekurencyjny w notatkach. P(20,8) oblicz

ZawistuS: Możecie mi to wyjaśnić krok po kroku jak to zrobić, bądź zrobić te przykłady z wyjaśnieniem? Próbuję sam ogarnąć takie zadania, ale totalnie nie mogę tego zrozumieć, bo nigdzie nie mogę znaleźć dobrego wyjaśnienia. Wiem, że to dla was easy zadanka. Ja niestety tego nie ogarniam i próbuję to pojąć. Jak zobaczę jak to zrobiliście to spróbuję to ogarnąć. Z góry dzięki

Mila: Jaki masz materiał na wykładach?

ZawistuS: KOMBINATORYKA 1. Notacja i podstawowe pojecia 2. Relacja binarna i jej własnosci; funkcja i jej własnosci 3. Zasady równolicznosci, mnoenia i właczania−wyłaczania 4. Zasada „szufladkowa” Dirichleta 5. Zbiory uporzadkowane; zliczanie łancuchów i antyłancuchów 6. Zliczanie funkcji, injekcji i rozmieszczen uporzadkowanych 7. Permutacja i jej własnosci 8. Zliczanie i generowanie podzbiorów zbioru n−elementowego 9. Zliczanie w zbiorach z powtórzeniami (równania diofantyczne) 10. Metoda funkcji tworzacej 11. Zliczanie podziałów zbioru (liczby Stirlinga II rodzaju) 12. Zliczanie surjekcji 13. Zliczanie podziałów liczby 14. Wprowadzenie do ogólnej teorii zliczania Próbuję to zrozumieć sam, niestety nie udaje mi się. Nie mam wyjaśnionych dokładnie przykładów

ABC: nie masz ćwiczeń z tego przedmiotu?

ZawistuS: Mam ćwiczenia. Kobietą z którą je mam nie potrafi tego dokładnie wyjaśnić, leci szybko z tematem, a ja siedzę i nie rozumiem tych zadań. Dlatego proszę żeby ktoś mi pokazał przykład jak zrobić takie zadania.

Mila: zadanie (2) (13 punkt) 1) Podział liczby na k składników P(n,k)=P(n−1,k−1)+P(n−k,k) Własności: P(n,1)=1,P(n,n)=1 P(n,k)=0 jeśli n<k ========= Warto skorzystać z gotowego wzoru:

	n
P(n,2)=[		] cecha liczby
	2

	1
może masz podane jeszcze na P(n,3)=[		n2]
	12

2) Przykłady łatwe: a) Podział liczby 7 na 2 składniki ( nie jest ważna kolejność) 7=2+5, 7=3+4, 7=6+1 są 3 podziały

	7
P(7,2) =[		]=3
	2

to samo wyjdzie gdy liczymy z wzoru (1): P(n,k)=P(n−1,k−1)+P(n−k,k) P(7,2)=P(6,1)+P(7−2,2)= =1+P(5,2)=1+P(4,1)+P(5−2,2)=1+1+P(3,2)=2+P(2,1)+P(1,2)=2+1+0=3 Żmudne liczenie b) Podział liczby 7 na 3 składniki.

	6
P(7,3)=P(6,2)+P(4,3)=[		]+P(3,2)+P(1,3)=3+1+0=4
	2

c) Podział liczby 20 na 2 składniki

	20
P(20,2)=[		]=10
	2

d) podział liczby 20 na 3 składniki liczymy z wzoru (1)

	19
P(20,3)=P(19,2)+P(17,3)=[		]+P(16,2)+P(14,3)=
	2

=9+8+P(13,2)+P(11,3)=17+6+P(10,2)+P(8,3)=23+5+P(8,3) =28+P(7,2)+P(5,3)=28+3+P(5,3)= =31+P(4,2)+P(2,3)=33+0=33 ===================== 3) Podział liczby 20 na 8 składników. Będziemy korzystać z własności i z ułatwień:

	n		1
P(n,2)=[		], P(n,3)=[		n2]
	2		12

Analizuj i rozpisz samodzielnie, a potem spróbuj obliczyć: P(20,8) Daj znać , gdy będziesz gotowy do współpracy.

Mila: Co z Tobą? Nie chcesz się nauczyć?

	n2
P(n,3)=[		] zaokrąglenie, (sufit, podłoga)
	12

P(20,8)=P(19,7)+P(12,8)= =P(18,6)+P(12,7)+P(11,7)+P(4,8)= P(18,6)+P(12,7)+P(11,7)+0= =P(17,5)+P(12,6)+P(11,6)+P(5,7)+P(10,6)+P(4,7)= =P(17,5)+P(12,6)+P(11,6)+P(10,6)= =P(16,4)+P(12,5)+P(11,5)+P(6,6)+P(10,5)+P(5,6)+P(9,5)+P(4,6)= =1+P(16,4)+P(12,5)+P(11,5)+P(10,5)+P(9,5)= =1+P(15,3)+P(12,4)+P(11,4)+P(7,5)+P(10,4)+P(6,5)+P(9,4)+P(5,5)+P(8,4)+P(4,5)=

	225
=2+[		]+P(11,3)+P(8,4)+P(10,3)+P(7,4)+P(6,4)+P(2,5)+P(9,3)+P(6,4)+P(8,3)+P(5,4)+
	12

+P(7,3)+P(4,4)= =2+19+10+8+7+6+4+1+P(8,4)+P(7,4)+P(6,4)+P(6,4)+P(5,4)= =56+P(7,3)+P(4,4)+P(6,3)+P(3,4)+P(5,3)+P(2,4)+P(4,3)+P(1,4)= =56+4+1+3+3+2+1=70 ===================

ZawistuS: Dziękuję, już czaje o co chodzi. Podstawienie do wzoru, a potem rozbijanie tego do skutku. Zadanie drugie już rozumiem

Mila: