Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Rozdzielanie kwiatów

Strona 1 z 1

[ Posty: 8 ]

Autor

Wiadomość

prawyakapit Offline

Tytuł: Rozdzielanie kwiatów

Napisane: 4 maja 2015, o 12:07

Posty: 650
Lokalizacja: łódź

Marcin ma 6 tulipanów, 5 róż i 4 goździki. Z okazji dnia kobiet chce obdarować tymi kwiatami swoje koleżanki: Asię , Basię i Kaię. NA ile sposobów może to zrobić, przy założeniu, że:
Każda dziewczyna dostanie co najmniej jeden kwiatek

Czy mógłby mi ktoś podpowiedzieć rozwiązanie?
Próbowałam rozmieszczać najpierw po jednym kwiatku dla każdej dziewczyny, ale to nie wychodzi oczywiscie bo zostaje mi 12 kwiatów, ale nie znam ich rodzajów przecież.

Góra

Gouranga Offline

Tytuł: Rozdzielanie kwiatów

Napisane: 4 maja 2015, o 12:26

Posty: 1471
Lokalizacja: Trójmiasto

Wygląda jak zadanie z wykładniczych funkcji generujących.
Rozpatrując funkcję:
$\left(1 + \frac{z}{1!} + \frac{z^2}{2!} + \frac{z^3}{3!} + \frac{z^4}{4!}\right) \cdot \left(1 + \frac{z}{1!} + \frac{z^2}{2!} + \frac{z^3}{3!} + \frac{z^4}{4!} + \frac{z^5}{5!}\right) \cdot \left(1 + \frac{z}{1!} + \frac{z^2}{2!} + \frac{z^3}{3!} + \frac{z^4}{4!} + \frac{z^5}{5!} + \frac{z^6}{6!}\right)$
możemy znaleźć ilość możliwych ciągów danej długości z tych kwiatów. Jednak nadal to nie będzie rozwiązywało problemu bo dalej trzeba by te ciągi dzielić na 3 dziewczyny.

Góra

prawyakapit Offline

Tytuł: Rozdzielanie kwiatów

Napisane: 4 maja 2015, o 12:28

Posty: 650
Lokalizacja: łódź

szczerze mówiąc to nie miałam absolutnie takiego tematu jak funkcje generujące

Góra

a4karo Offline

Tytuł: Rozdzielanie kwiatów

Napisane: 4 maja 2015, o 12:55

Posty: 15239
Lokalizacja: Bydgoszcz

Sformułowanie zadania wymaga chyba sprecyzowania: czy wszystkie kwiaty maja być rozdane dziewczynom, czy wystarczy np. że da każdej po jednym, a resztę wyrzuci do pobliskiego kosza?

Góra

prawyakapit Offline

Tytuł: Rozdzielanie kwiatów

Napisane: 4 maja 2015, o 13:08

Posty: 650
Lokalizacja: łódź

Mam taki pomysł:
Rozpatruję przypadki:
Asia nie dostanie Kwiatka
wtedy rozdzielamy 6 tulipanów , 4 goździki i 5 róż między Basię i Kasię, rozdzielamy między te 2 osoby tulipany : ${6+2-1\choose 2}$
róże: ${5+2-1\choose 2}$
goździki: ${4+2-1\choose 2}$ sposobów

mnożymy to przez 3 bo mamy jeszcze przypadek, że Basia albo Kasia nie dostanie kwiatka:
czyli ${7\choose 2} \cdot {6\choose 2} \cdot {5\choose 2} \cdot 3$
dalej rozważamy przypadek w którym wszystkie kwiatki trafiają do jednej osoby
jest to możliwe na 3 sposoby.

czy coś pomijam w tym rozumowaniu ?

sumuję wszystko i odejmuje od liczby wszystkich możliwości rozdania kwiatków
ps: wszystkie muszą być rozdane

Góra

Gouranga Offline

Tytuł: Rozdzielanie kwiatów

Napisane: 4 maja 2015, o 14:13

Posty: 1471
Lokalizacja: Trójmiasto

prawyakapit, pomysł odpada bo symbol Newtona działa jak kwiaty będą rozróżnialne a w tym zadaniu dwa tulipany nie są rozróżnialne między sobą.

Góra

prawyakapit Offline

Tytuł: Rozdzielanie kwiatów

Napisane: 4 maja 2015, o 14:40

Posty: 650
Lokalizacja: łódź

nie rozróżniam kwiatków ale miejsca. Interpretuje to zadane jako rozmiesczenie poszczególych rodzajów kwiatow na 2 rozróżnialnych miejscach. 2-wyrazowa Kombinacja z powtórzeniami ciągu 7 elementowego.

Góra

arek1357 Offline

Tytuł: Rozdzielanie kwiatów

Napisane: 4 maja 2015, o 20:03

Posty: 3273
Lokalizacja: blisko

Mam taki pomysł (nie twierdzę, że dobry):

Zakładam, że każda dziewczynka dostaje minimum jeden kwiatek, wszystkie kwiatki muszą być rozdane.
Kwiaty tego samego gatunku są nierozróżnialne gatunki są rozróżnialne dziewczynki też są rozróżnialne.
To tyle.

Nazwijmy dziewczynki: A, B, C. kwiatki: tulipany(t), róże (r), goździki (g).

Utwórzmy tabelkę:

$\begin{tabular}{cccc} * & t & r & g \\ \hline A & x_{1} & y_{1} & z_{1} \\ \hline B & x_{2} & y_{2} & z_{2} \\ \hline C & x_{3} & y_{3} & z_{3} \\ \hline \end{tabular}$

Znaczy to, że np dziewczynka A ma: $x_{1}$ tulipanów,

$y_{1}$ róż ,i $z_{1}$ goździków itd...

Teraz z warunków zadania mamy:

I:
$x_{1}+x_{2}+x_{3}=6$
$y_{1}+y_{2}+y_{3}=5$ kwiaty
$z_{1}+z_{2}+z_{3}=4$

A teraz każda ile dostanie:

II:
A: $x_{1}+y_{1}+z_{1}=a$
B: $x_{2}+y_{2}+z_{2}=b$
C: $x_{3}+y_{3}+z_{3}=c$

$a+b+c=15$ tyle jest kwiatów,
oraz:
$1 \le a,b,c \le 15$ - warunki

Wyliczając: $z_{1}, z_{2}, z_{3}$ z I i podstawiając do II

Wyjdzie, że trzecie równanie w II jest równoważne dwóm wcześniej i otrzymamy:

III:
$x_{1}+y_{1}+z_{1}=a$
$x_{2}+y_{2}+z_{2}=b$

Gdzie warunki na a, b są znane.

Czyli nasze układy sprowadzają się do wyliczenia ilości równań w III, gdzie:

$0 \le x_{i}, y_{i}, 1 \le a,b \le 14,a+b \le 14$

Jak widać tych możliwości jest:

$\sum_{\substack{1 \le a,b \le 14, \\ a+b \le 14}}^{} {a+3-1 \choose a}{b+3-1 \choose b}=$

$\frac{1}{4} \sum_{\substack{1 \le a,b \le 14, \\ a+b \le 14}}^{}(a+1)((a+2)(b+1)(b+2)$

Zapomniałem dodać, że muszą być jeszcze warunki:

$0 \le x_{i} \le 6$

$0 \le y_{i} \le 5$

$0 \le z_{i} \le 4$

będą jeszcze te ograniczenia ale razem wydaje mi się ok!

Drobna modyfikacja bo to są kombinacje z powtórzeniami a do tego z ograniczeniami,

to rozwiązaniem dla konkretnego a lub b przy ograniczeniach jak wyżej dla ixów ygreków i zetów

musimy oznaczyć przez $f(a), f(b)$ - ilość kobmbinacji z ograniczeniami:

czyli:

$\sum_{\substack{1 \le a,b \le 14 \\ a+b \le 14}}^{}f(a)f(b)$

Np dla:

$a=5,b=6$ będzie równanie charakterystyczne:

$(1+x+x^2+x^3+x^4+x^5+x^6) (1+x+x^2+x^3+x^4+x^5) (1+x+x^2+x^3+x^4)$

stąd:

$f(a)=coef (x^6)$

$f(b)=coef (x^5)$

Chyba prościej się nie da. natomiast wzór, który napisałem wyżej jest dobry ale dla kombinacji bez ograniczeń.

$f(a)=coef(x^6)=24$

$f(b)=coef(x^5)=20$

I tak trzeba będzie zliczać poszczególne przypadki!

$(1+x+x^2+x^3+x^4+x^5+x^6)(1+x+x^2+x^3+x^4+x^5)(1+x+x^2+x^3+x^4)=$

$=x^{15}+3 x^{14}+6 x^{13}+10 x^{12}+15 x^{11}+20 x^{10}+24 x^9+26 x^8+26 x^7+24 x^6+20 x^5+15 x^4+10 x^3+6 x^2+3 x+1$

$(a,b)=(1,2)(2,1)(1,3)(3,1)(1,4)(4,1)(1,5)(5,1)(1,6)(6,1)(1,7)(7,10(1,8)(8,1)(1,9)(9,1)(1,10)(10,1)$
$(1,11)(11,1)(1,12)(12,1)(1,13)(13,1)(2,3)(3,2)(2,4)(4,2)(2,5)(5,2)(2,6)(6,2)(2,7)(7,2)(2,8)(8,2)$
$(2,9)(9,2)(2,10)(10,2)(2,11)(11,2)(2,12)(12,2)(3,4)(4,3)(3,5)(5,3)(3,6)(6,3)(3,7)(7,3)(3,8)(8,3)$
$(3,9)(9,3)(3,10)(10,3)(3,11)(11,3)(4,5)(5,4)(4,6)(6,4)(4,7)(7,4)(4,8)(8,4)(4,9)(9,4)(4,10)(10,4)$
$(5,6)(6,5)(5,7)(7,5)(5,8)(8,5)(5,9)(9,5)(6,7)(7,6)(6,8)(8,6)(1,1)(2,2)(3,3)(4,4)(5,5)(6,6)(7,7)$

Trzecia dziewczynka dostaje zawsze te kwiatki, które nie dostały dziewczynki pierwsza i druga.
Dlatego do kombinacji się nie liczy.

$\sum_{}^{} f(a)f(b)=2 \cdot 3(6+10+15+20+24+26+26+24+20+15+10+6)+2 \cdot 6(10+15+20+24+26+26+24+20+15+10)+2 \cdot 10(15+20+24+26+26+24+20+15)+2 \cdot 15(20+24+26+26+24+20)+2 \cdot 20(24+26+26+24)+2 \cdot 24(26+26)+6 \cdot 6+10 \cdot 10+15 \cdot 15+20 \cdot 20+24 \cdot 24+26 \cdot 26=1212+2280+14096+2013=19601$

Gdyby każda z dziewczynek miała dostać przynajmniej po jednym kwiatku z każdego gatunku
to warunki by się zmieniły tak:

$1 \le x_{i},y_{i},z_{i},3 \le a,b,a+b \le 12$

Góra

Poprzedni | Następny

	Strona 1 z 1	[ Posty: 8 ]

Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Zobacz podobne tematy
Tytuł tematu	Autor	Odpowiedzi
rozdzielanie biletów	FEMO	1
rozdzielanie pączków miedzy osoby	wiedzma	6
Rozdzielanie owoców między 3 ludzi	vtvs	9
Rozdzielanie sześciu zabawek między dwie osoby.	Abysmy	1
rozdzielanie przedmiotów	lofi	3

[Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]