Matematyka dyskretna, zadanie nr 4451
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
brightnesss post贸w: 113 |  2016-04-12 21:58:08Zad 1 Ile jest ciagow dlugosci 2n takich, ze kazda liczba i$\in$[n] wystepuje dokladnie dwa razy oraz kazde dwa wyrazy sa rozne? Tutaj policzylam juz ta czesc, ktora mowi ze i wystepuje 2 razy i wyszlo mi: ${2n \choose 2}{2n-2 \choose 2}...{2 \choose 2}, czyli \frac{(2n)!}{2^{n}}$ I wiem, ze trzeba skorzystac z zasady wlaczen i wylaczen, czyli od tego co mamy odjac zbior B, gdzie B-sasiednie wyrazy sa takie same. Zbior B=2n*(n-2)!+${2n \choose 2}$(2n-4)!-${2n \choose 3}$(2n-6)!+...-${2n \choose n}$(2n-n)! Dobrze? I zadanie 2, na ktore nie mam pomyslu: Przez pustynie idzie karawana skladajaca sie z dziewieciu wielbladow. Iloma sposobami mozna poprzestawiac wielblady tak, aby przed kazdym wielbladem szedl inny niz przed przestawieniem? |
janusz78 post贸w: 820 | 2016-04-14 16:12:16 Zadanie 2 Ponumerujmy wielb艂膮dy w ich porz膮dku pocz膮tkowym kolejnymi cyframi $ 1,2,3....,9.$ Zadaniem jest znale藕膰 liczb臋 permutacji, kt贸re nie zawieraj膮 pojedy艅czych par: $ (1,2),(2,3),(3,4), (4,5),(5,6),(6,7),(7,8),(8,9).$ Rozpatrzmy na przyk艂ad par臋 $ (1,2)$ Na pocz膮tku obliczmy liczb臋 permutacji, kt贸re zawieraj膮 par臋 $ (1,2).$ Potraktujmy t臋 par臋 jako jeden element. Wtedy mamy osiem element贸w element贸w ni偶 dziewi臋膰 i liczba permutacji zawieraj膮cych $(1,2)$ jest r贸wna $P_{8}= 8!$ Takie same rozumowanie mo偶e dotyczy膰 ka偶dej z o艣miu par. Je艣li dwie pary s膮 艂膮czne (maj膮 wsp贸lny element) np. $ (1,2)(2, 3),$ wtedy wyst臋puj膮 trzy r贸偶ne elementy $1,2, 3 $ w dw贸ch parach. Je艣li za艣 dwie pary s膮 roz艂膮czne np. $(1,2), (7,8)$ wtedy traktujemy je jako dwa nowe elementy i w tym przypadku liczba siedmioelementowych permutacji wynosi $P_{7}= 7!$ Dwie r贸偶ne pary z o艣miu par mo偶emy wybra膰 na $C_{8}^{2}= { 8\choose 2}.$ St膮d i z prawa mno偶enia wynika, 偶e istnieje $C_{8}^{1}\cdot P_{8}$ permutacji zawieraj膮cych par臋 $(1,2).$ Og贸lniej istnieje $ C_{8}^{k}\cdot P_{9-k}$ permutacji zawieraj膮cych $ k $ par $ k=1,2,3,...,8$ Z zasady w艂膮cze艅 i wy艂膮cze艅 wynika, 偶e ilo艣膰 sposob贸w przestawie艅 wielb艂膮d贸w $ L, $ tak aby przed ka偶dym szed艂 inny ni偶 przed przedstawieniem jest r贸wna $ L= P_{9}- C_{8}^{1}P_{8}+ C_{8}^{2}P_{7}- C_{8}^{3}P_{6}+C_{8}^{4}P_{5}- C_{8}^{5}P_{4}+ C_{8}^{6}P_{3}- C_{8}^{7}P_{2}+ C_{8}^{8}P_{1}.$ $ L = 8!\left[9 - \frac{8}{1!}+ \frac{7}{2!}- \frac{6}{3!}+\frac{5}{4!}- \frac{4}{5!}+ \frac{3}{6!}- \frac{2}{7!}+ \frac{1}{8!}\right]= 148329$ Obliczenie $ L $ w programie R > L= factorial(8)*(9- 8/factorial(1)+ 7/factorial(2)- 6/factorial(3)+5/factorial(4)-4/factorial(5)+3/factorial(6)-2/factorial(7)+1/factorial(8)) > L [1] 148329 |
| strony: 1 | |
Prawo do pisania przys艂uguje tylko zalogowanym u偶ytkownikom. Zaloguj si臋 lub zarejestruj