Matematyka dyskretna, zadanie nr 4451

Autor	Zadanie / Rozwiązanie
brightnesss postów: 113	2016-04-12 21:58:08 Zad 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