Matematyka.pl

W urnie jest \(\displaystyle{ n}\) kartek ponumerowanych liczbami od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\). Wyciągamy z urny bez zwracania \(\displaystyle{ k}\) kartek. Niech \(\displaystyle{ a_i}\) numer \(\displaystyle{ i}\)-tej wyciągnietej kartki. Jakie jest prawdopodobieństwo tego, że w ciągu \(\displaystyle{ \left( 0,a_1, \ldots, a_k, 0\right)}\) jest dokładnie jedno maksimum lokalne? (Wyraz ciągu jest maksimum lokalnym, jeśli jest liczbą większą od obu sąsiednich wyrazów)

mam taki sam problem

Sumuj po miejscu wystąpienia maksimum - oznaczmy go i.
Najpierw wybierasz i liczb z n i sortujesz rosnąco.
Następnie k-i i sortujesz malejąco.

W ten sposób liczymy każdy układ dwa razy (maksimum w lewej lub w prawej części), więc wynik dzielimy na dwa.

Dodajemy 1, bo podzieliliśmy na 2 przypadki i=0 oraz i=k, a ich dwa razy nie liczymy

Suma powinna być do obliczenia.

do końca tego nie widzę, jednak coś mi zaczyna w głowie się układać

można prosić o więcej szczegółów? wiem, że proszę o dużo

czy to nie powinno być coś takiego:

\(\displaystyle{ \sum_{i=0}^{k} {n \choose i} {n-i \choose k-i}}\)

Prawie tak. Musisz uwzględnić jeszcze, że 1,3,2 powstanie z dwóch różnych wyborów zbiorów: {1,3}{2} oraz {1}{2,3}. Dlatego pisałem o dzieleniu na dwa. Odwołuję jednak dodawanie jedynki, bo jednak wszystko da się przedstawić na dwa sposoby

Hubbaser pisze:Prawie tak. Musisz uwzględnić jeszcze, że 1,3,2 powstanie z dwóch różnych wyborów zbiorów: {1,3}{2} oraz {1}{2,3}. Dlatego pisałem o dzieleniu na dwa. Odwołuję jednak dodawanie jedynki, bo jednak wszystko da się przedstawić na dwa sposoby

Ok, czyli moc zbioru A (istnieje dokładnie jedno maksimum lokalne) to \(\displaystyle{ \frac{\sum_{i=0}^{k} {n \choose i} {n-i \choose k-i}
}{2}}\).

Jakieś wskazówki jak to zsumować?
Szukałam już jakichś tożsamości trygonometrycznych ale nic nie znalazłam podobnego

Zdaje mi się, że z trygonometrią nie ma to większego związku.

Podaną sumę można wyliczyć z rozpisania symboli newtona, a dalej dwumianu newtona.

Ale takie sumy najłatwiej obliczać z interpretacji kombinatorycznej. Mówi ona również, że od początku dało się zrobić to zadanie prościej, ale nie wpadłem na to Mianowicie zamiast wybierać zbiory tak jak to wcześniej napisałem, można wybrać k liczb z n i porozrzucać je do dwóch zbiorów

*tożsamości kombinatorycznych

Hubbaser pisze: Mianowicie zamiast wybierać zbiory tak jak to wcześniej napisałem, można wybrać k liczb z n i porozrzucać je do dwóch zbiorów

co znaczy porozrzucać do dwóch zbiorów? Nie bardzo to widzę

Każdemu elementowi mówisz czy ma być w pierwszym czy w drugim zbiorze.

Czyli dla k różnego od 0:

\(\displaystyle{ \left| A\right| = \frac{{n \choose k} 2^{k}}{2}}\)

Dla k=0 wynik zadania to 0, bo ciąg 0,0 ma dwa maksima lokalne

po zsumowaniu wyszło mi \(\displaystyle{ \sum_{i=0}^{k} {k \choose i} \cdot {n \choose k} =2^k \cdot {n \choose k}}\)

Dobrze?

Czyli nasze prawdopodobieństwo to: \(\displaystyle{ \frac{2^k \cdot {n \choose k}}{ \frac{2n!}{(n-k)!} }= \frac{2^{k-1}}{k!}}\)-- 11 kwi 2016, o 15:38 --czyli na to samo wychodzi dziękuję baaardzo