Matematyka dyskretna, zadanie nr 2783

Autor	Zadanie / Rozwiązanie
geometria postów: 865	2014-11-09 00:58:20 Oblicz 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^22!}=3$ dla 6 ludzi daje $\frac{6!}{2^33^!}=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 $53$). Myśląc analogicznie, dla 8 osób będzie 7(ilość dla 6 osób), czyli $715=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