Matematyka dyskretna, zadanie nr 4444

Autor	Zadanie / Rozwiązanie
brightnesss postów: 113	2016-04-11 13:26:42 Zad1 Na półce stoi 12 książek. Na ile sposobów można wybrać spośród nich 5 ksiązek, aby nie było wśród nich żadnych dwóch stojących obok siebie? Zad2 Przy okrągłym stole zasiada 12 osob, Na ile sposobów można wybrać sposród nich 5 osób tak, aby nie została wybrana żadna para osób siedzących obok siebie? Wiem, że to są zadania na kombinację z powtórzeniami. Jednak nie potrafie ich zrozumieć. Szukałam na różnych forach rozwiązań i tam była metoda np ustawienia w ciąg binarny 100101, jednak nie rozumiem na czym ona polega i jak nam pomaga. Z góry dziękuję za pomoc.

tumor postów: 8070	2016-04-11 13:44:51 Może proponuj jakieś rozwiązania, jakieś idee? 1. Możesz spojrzeć rekurencyjnie. Zadanie ma rozwiązanie, gdy chcemy wybrać k książek, a wszystkich książek jest co najmniej 2k-1. Jeśli wszystkich jest więcej, to mamy jeszcze więcej rozwiązań. Jeśli S(12,5) oznacza, że z 12 wybieramy 5 książek zgodnie z regułami, to $S(12,5)=S(10,4)+S(9,4)+S(8,4)+S(7,4)$ Mamy tu cztery przypadki, jeśli wybieramy pierwszą książkę, to zostaje 10 z których musimy wybrać 4. Jeśli omijamy pierwszą a wybieramy drugą, to zostaje 9 z których wybieramy 4 etc. Za każdym razem $S(n,k)=S(n-2,k-1)+S(n-3,k-1)+...+S(2(k-1)-1,k-1)$ A oczywiście jeśli mamy $S(n,1)=n$, o ile oczywiście $n\ge 1$ --- Możesz zauważyć, że zadanie to jest bardzo podobne do niedawnego zadania z ciągami binarnymi, w których nie ma dwóch jedynek obok siebie. Mamy ciąg 12 znaków, w tym 5 jedynek, które nie sąsiadują ze sobą. Ile takich ciągów umiemy stworzyć? Każdy taki ciąg mówi nam o jakimś wyborze. Tzn jeśli np na trzecim miejscu ciągu znajduje się 1, to książkę trzecią wybieramy, a jeśli na czwartym jest 0, to czwartej nie wybieramy. Każdą sytuację wyboru/podziału możemy przedstawić w postaci pewnego ciągu o odpowiednich elementach. A ciągi się niekiedy zlicza bardziej intuicyjnie. 2. Zadanie z ciągami binarnymi będzie trzeba zmodyfikować w ten sposób, że jeśli pierwsza w ciągu jest 1, to nie może być 1 na ostatnim miejscu. I tyle. Wiadomość była modyfikowana 2016-04-11 15:25:37 przez tumor

brightnesss postów: 113	2016-04-11 13:52:12 Co do pierwszego to myślałam, że skoro wybieramy 5 książek, ale nie mogą stać obok siebie to możemy ustawić taki ciąg: o\|o\|o\|o\|o o-ksiązka \|-miesce z ktorego nie mozemy wybrać Książek mamy 5, a miejsc 4. Wiemy też że wszystkich elementów mamy 12, więc zostało mnam 3 ksiązki które możemy wsadzić gdziekolwiek pomiędzy wybranymi. Czyli na ${7 \choose 3}$. Jednak odpowiedź jest niepoprawna i nie wiem gdzie jest błąd.

tumor postów: 8070	2016-04-11 14:10:06 Jeśli 9 książek wygląda tak: wnwnwnwnw, gdzie w to wybrana, n niewybrana, to wstawienie kolejnej niewybranej książki między dwie pierwsze da w efekcie wnnwnwnwnw natomiast wstawienie między drugą i trzecią da wnnwnwnwnw Widzisz jakąś różnicę? Bo zliczasz oba warianty jakby się różniły, podczas gdy się nie różnią. Proszę o podliczenie ciągów z zerami i jedynkami tak jak w zadaniu: http://www.math.edu.pl/forum/temat,studia,4443,0

brightnesss postów: 113	2016-04-11 15:12:52 No tak, widze blad. Jednak nadal nie rozumiem tego wczesniejszego zadania z zerem i jedynkami. Ps mozna jakos poprawic ta moja metode?

tumor postów: 8070	2016-04-11 15:30:07 Można. Masz sytuację _w_n_w_n_w_n_w_n_w_ gdzie w oznacza wybraną, n niewybraną, a _ to miejsce, gdzie jeszcze możemy coś dać. No i mamy rozdysponować jeszcze nnn gdzieś tam. Sytuacje upraszczamy do _w_nw_nw_nw_nw_ Ponieważ nie ma znaczenia, czy nowe n wstawimy po prawej czy po lewej od poprzednich n. Mamy zatem 6 miejsc, gdzie możemy wstawić nasze nnn. Poza tym nnn możemy wstawić a) razem wszystkie trzy: to się da zrobić na 6 sposobów b) w systemie 2+1, czyli w jedno wolne miejsce nn, a w inne tylko n, to się da zrobić na 65 sposobów c) jako 1+1+1, czyli wybierając ${6 \choose 3}=20$ sposobów włożenia pojedynczych n w trzy spośród 6 miejsc. Razem 56. --- Jednakże opcja z ciągiem zerojedynkowym i rozwiązaniem jak poprzednio jest nieco lepsza. Załóżmy, że ostatnia nie jest jedynka. Mamy zatem 5 par (10) oraz dwa dodatkowe 0, razem 7 elementów, co rozpatrzone jako permutacje z powtórzeniami da $\frac{7!}{5!2!}=21$ układów. Jeśli ostatnia jest jedynka, to mamy wśród 11 pozostałych cyfr ciągu cztery pary (10) i trzy 0. To też 7 elementów, ale teraz $\frac{7!}{4!3!}=35$ Razem 56 układów. ---- Rozpatrując rekurencyjnie $S(12,5)=S(10,4)+S(9,4)+S(8,4)+S(7,4)= S(8,3)+2S(7,3)+3S(6,3)+4S(5,3)= S(6,2)+3S(5,2)+6S(4,2)+10S(3,2)= S(4,1)+4S(3,1)+10S(2,1)+20S(1,1)= 4+12+20+20=56$

brightnesss postów: 113	2016-04-11 22:35:32 Dziękuję bardzo. Jednak mam ostatnie dwa pytania. Dlaczego w tym b mamy 6*5? A drugie, czy moglabym prosic o wytlumaczenie tego sposobu: http://www.matematyka.pl/215455.htm

tumor postów: 8070	2016-04-11 23:06:16 Jeśli masz 6 miejsc, w których dajesz dwa elementy (raz element nn, a raz n), przy tym nie może być tak, że oba elementy trafią w jedno miejsce, to jeden element (na przykład podwójny) trafia w dowolne z 6 miejsc, a drugi element (tu: pojedynczy) trafia w jedno z pozostałych 5 miejsc. Inaczej patrząc: wybieramy na ${6 \choose 2}$ sposobów dwa miejsca do rozlokowania tych elementów, no ale elementy są odróżnialne, czyli lokujemy je na 2! sposobów. ${6 \choose 2}2!=56$ ----- Rozwiązanie z matematyka.pl jest tylko uogólnionym zapisem pierwszego rozwiązania z mojego poprzedniego postu. Wzór użyty to tzw kombinacje z powtórzeniami. Jeśli wybieramy kombinację (czyli podzbiór) jakiegoś zbioru $\{1,2,3,...,s\}$ to oczywiście ten podzbiór tylko na jeden sposób możemy uporządkować rosnąco. Zatem tyle jest kombinacji t-elementowych ile t-elementowych ciągów rosnących. Zatem ${s \choose t}$ można rozumieć jako ilość t-elementowych ciągów rosnących o elementach ze zbioru s-elementowego. Wyobraźmy sobie jednak, że mamy elementy $a_1\le a_2 \le a_3 \le ... \le a_t$, czyli t-elementowy ciąg NIEMALEJĄCY o elementach ze zbioru s-elementowego. Zróbmy teraz taki manewr, dodajmy do pierwszego wyrazu 0, do następnego 1, do kolejnego 2 i tak dalej: $a_1<a_2+1<a_3+2<...<a_t+(t-1)$ Zatem ciągów niemalejących t-elementowych ze zbioru s-elementowego jest dokładnie tyle, ile ciągów rosnących t-elementowych ze zbioru (s+t-1)-elementowego, czyli ${s+t-1 \choose t}$. Zarazem jednak taki ciąg niemalejący można rozumieć jak kombinację, w której elementy mogą się powtarzać (tak jak mogą być równe pewne wyrazy ciągu niemalejącego). Wróćmy do naszego zadania. Mamy _w_nw_nw_nw_nw_ czyli k+1 miejsc, w które możemy wrzucić elementy. Wybieramy zatem trzy z tych miejsc, ale Z POWTÓRZENIAMI, czyli używamy wzoru na kombinacje z powtórzeniami. W naszym przypadku mamy zbiór (k+1)-elementowy (wybieramy spośród k+1 miejsc wstawiania zer), a podzbiór (n-2k+1)-elementowy (ponieważ od n elementów odjęliśmy k jedynek i k-1 zer i tyle nam zostało zer do wstawiania). Jeśli podstawimy $t=n-2k+1$ $s=k+1$, dostaniemy ${s+t-1 \choose t}={n-k+1 \choose n-2k+1}$ Jeszcze raz, w skrócie: - kombinacja bez powtórzeń odpowiada ciągowi rosnącemu (elementy się nie powtarzają). - jeśli rozważymy ciąg niemalejący (elementy mogą się powtarzać) to otrzymamy tzw. kombinację z powtórzeniami, ale ciąg niemalejący sprytnym dodawaniem zmieniamy na rosnący, wobec tego wzór na kombinacje z powtórzeniami też korzysta z symbolu Newtona - podstawiając dane z naszego zadania, gdzie mamy k+1 dziur do wypełniania (n-2k+1) elementami (być może wiele elementów w jednej dziurze) dostajemy od razu to, co autor rozwiązania

brightnesss postów: 113	2016-04-12 11:39:31 Bardzo dziękuję, już zaczyna mi się coś rozjaśniać. Zaciekawił mnie jeszcze ten ciąg niemalejący. Bo jesli na przyklad chcemy znalezc ile jest liczb naturalnych, w ktorych cyfry wystepuja w porzadku niemalejacym, to możemy to zapisać jako równanie : X1+x2+x3+...+x9=n Gdzie xi i$\in${1,2,...,9} to ilosc cyfr "i" w naszej liczbie. Wiec nasz wzór to będzie ${n+9-1 \choose 9}$? Dobrze to rozumiem?

tumor postów: 8070	2016-04-12 11:51:54 ${9+n-1 \choose n} $ gdzie n jest długością liczby, a pierwsza cyfra nie jest zerem (dlatego dla liczb jednocyfrowych dostaniemy wynik 9, a nie 10). Wybieramy bowiem n liczb z powtórzeniami ze zbioru 9-elementowego.

strony: 1 2

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj