Matematyka dyskretna, zadanie nr 2783
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
geometria post贸w: 865 |  2014-11-09 00:58:20Oblicz na ile sposobow mozna polaczyc w pary 2n osob. Zrobilbym tak: ${2n \choose 2}$. Jezeli jest zle to poproslbym o wytlumaczenie dlaczego. |
tumor post贸w: 8070 | 2014-11-09 07:16:26 Naj艂atwiej stwierdzi膰, 偶e co艣 jest 藕le, gdy si臋 sprawdzi, czy dzia艂a. Ludzi A,B,C,D mo偶na po艂膮czy膰 AB i CD AC i BD AD i BC i koniec, bo wszystkie inne pary to te same pary. Natomiast ${4 \choose 2}=6$. Czyli nie. ----- Teraz rozumujemy, co posz艂o 藕le. ${2n \choose 2}$ to ilo艣膰 wybor贸w jednej pary z grupy 2n os贸b. A co z reszt膮? Je艣li masz 8 os贸b, wybierzesz jedn膮 par臋 (na ${8 \choose 2}$ sposob贸w), zostanie $6$ os贸b. I co z nimi? :) Ano z tych 6 nale偶y wybra膰 drug膮 par臋, zostan膮 4 osoby, z tych 4 nale偶y wybra膰 kolejn膮 par臋, zostan膮 dwie (no i wyb贸r z nich pary jest mo偶liwy na jeden spos贸b). By艂oby to zatem ${8 \choose 2}{6 \choose 2}{4 \choose 2}{2 \choose 2}$, tylko taki model opisuje wyb贸r par NUMEROWANYCH. Czyli gdyby艣my chcieli podzieli膰 ludzi na pary, da膰 jednej parze numer I, drugiej numer II etc, to by艂oby to w艂a艣nie takie obliczenie. Gdy kolejno艣膰 par nie ma znaczenia, to naturaln膮 drog膮 jest uto偶sami膰 ze sob膮 wszystkie kolejno艣ci, kt贸re opisuj膮 te same pary. A jest ich tyle, ile mo偶liwych przemiesza艅 par, dla $n$ par to liczba $n!$ (dla wyj艣ciowych 4 os贸b mamy $\frac{{4 \choose 2}{2 \choose 2}}{2!}=3$, dodajmy. :P) To艣my sobie wyrozumowali d艂ugi wz贸r. No ale tam si臋 wszystko zabawnie skraca. Jak to po skr贸ceniu b臋dzie? |
geometria post贸w: 865 | 2014-11-09 12:30:39 Czyli ${2n \choose 2}$*${2n-2 \choose 2}$*...*${2 \choose 2}$ (2n-2)! w mianowniku skroci sie z (2n-2)! w liczniku itd. Wiec $\frac{(2n)!}{2^{n}}$. Po podzieleniu przez n! ostatecznie jest $\frac{(2n)!}{2^{n}n!}$ |
tumor post贸w: 8070 | 2014-11-09 12:46:58 Wygl膮da sensownie. Dla 4 ludzi daje $\frac{4!}{2^2*2!}=3$ dla 6 ludzi daje $\frac{6!}{2^3*3^!}=15$, co te偶 jest warto艣ci膮 s艂uszn膮 (bo osoba A mo偶e by膰 w 5 r贸偶nych parach, zostaj膮 w贸wczas za ka偶dym razem 4 osoby, czyli po 3 mo偶liwe podzia艂y, ostatecznie $5*3$). My艣l膮c analogicznie, dla 8 os贸b b臋dzie 7*(ilo艣膰 dla 6 os贸b), czyli $7*15=105$, co zgodne z naszym wzorem. Mo偶emy te偶 uzasadni膰 go indukcyjnie. Je艣li bowiem wz贸r dzia艂a dla pewnego $n$, to dla $n+1$ b臋dziemy mie膰 $\frac{(2n+2)!}{2^{n+1}(n+1)!}=\frac{(2n)!}{2^nn!}*\frac{(2n+1)(2n+2)}{2*(n+1)}=\frac{(2n)!}{2^nn!}*(2n+1)$ ---- Mo偶emy do tego radosnego wzoru doj艣膰 jeszcze inaczej. Przypu艣膰my, 偶e mamy $2n$ ludzi oraz n liter $A,B,C,...$ przy tym ka偶da litera wyst膮pi w dw贸ch wariantach,$ A_1,A_2, B_1,B_2$ i tak dalej. W贸wczas oczywi艣cie je艣li dw贸m ludziom przypiszemy te same litery $(A_1 i A_2)$, to stanowi膮 oni par臋. Takich przypisa艅 jest $\frac{(2n)!}{(2!)^n}$, bo to permutacje z powt贸rzeniami. T臋 liczb臋 dzielimy przez $n!$ z powodu podobnego jak wy偶ej: kolejno艣膰 par nie ma dla nas znaczenia, czyli wszystko jedno, czy Franek z Jurkiem s膮 par膮 $A_1,A_2$ czy par膮 $B_1,B_2$. Kolejno艣ci par jest w艂a艣nie $n!$. |
| strony: 1 | |
Prawo do pisania przys艂uguje tylko zalogowanym u偶ytkownikom. Zaloguj si臋 lub zarejestruj