szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Liczba ciągów
PostNapisane: 8 kwi 2018, o 16:42 
Użytkownik

Posty: 256
Lokalizacja: Polska
Znajdź liczbę ciągów długości 2n takich , ze każda liczba i \in \{ 1,2,..., n\} występuje dokładnie 2 razy, przy czym żadne dwa kolejne wyrazy nie są równe.

Jakieś pomysły?

Moja myśl jest taka że wszystkich ułożeń mamy (2n)!
i teraz będziemy odejmować przypadki kiedy cyfra/liczba a jest obok liczby a
Czyli spośród 2n wybieramy 2miejsca np na 2 dwójki które będą obok siebie następnie spośród 2n-2 wybieramy kolejne 2 cyfry które będą obok siebie itd itp
czyli

{2n \choose 2}  \cdot {2n-2 \choose 2}  \cdot ... \cdot  {2 \choose 2}
no i jeszcze przydałoby się powyższy iloczyn pomnożyć przez n! zważywszy na kolejność wystąpień poszczególnych cyfr

taka moja myśl, czy dobra?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Online
 Tytuł: Liczba ciągów
PostNapisane: 8 kwi 2018, o 19:29 
Użytkownik
Avatar użytkownika

Posty: 3229
Lokalizacja: blisko
zasada włączeń i wyłączeń...

a(n,k,s)= {n \choose s} {n-s \choose k-2s} \cdot  \sum_{i=0}^{s}  \frac{(k-i)!}{2^{s-i}} {s \choose i}(-1)^{i}

a(n,k,s) - ilość ciągów o długości k , w których występuje n liczb, oraz s par takich samych podwójnych liczb, ale takich ciągów, że dwie takie same liczby nie stoją koło siebie...


n- ilość liczb w ciągu

k - długość ciągu

s - ilość par czyli tych samych liczb

Oczywiście u Ciebie jest:

k=2n, s=n

Rozpatrzyłem przypadek bardziej ogólny...
Góra
Mężczyzna Offline
 Tytuł: Liczba ciągów
PostNapisane: 8 kwi 2018, o 20:06 
Użytkownik

Posty: 256
Lokalizacja: Polska
Mógłbyś rozwinąć swoje rozumowanie ?
Góra
Mężczyzna Online
 Tytuł: Liczba ciągów
PostNapisane: 8 kwi 2018, o 20:08 
Użytkownik
Avatar użytkownika

Posty: 3229
Lokalizacja: blisko
pytaj konkretnie co nie wiesz tak będzie łatwiej...
Góra
Mężczyzna Offline
 Tytuł: Liczba ciągów
PostNapisane: 8 kwi 2018, o 20:14 
Użytkownik

Posty: 256
Lokalizacja: Polska
Spośród wszystkich liczb ciągu wybierasz ilość par liczb a później ?
cóż to oznacza : {n-s \choose k-2s}(k-2s)!
Góra
Mężczyzna Online
 Tytuł: Liczba ciągów
PostNapisane: 8 kwi 2018, o 20:29 
Użytkownik
Avatar użytkownika

Posty: 3229
Lokalizacja: blisko
(k-2s)! - przepraszam bo musiałem ten czynnik zlikwidować nie zauważyłem on już jest niepotrzebny ponieważ wszystko jest ujęte już pod znakiem sumy

n-s - tyle zostało różnych liczb, które nie mają par

k-2s - tyle zostało miejsc na których rozmieszczono te liczby

{n-s \choose k-2s} - na tyle sposobów możemy wybrać liczby na tych miejscach...
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczba ciągów  klaudiak  0
 Liczba ciągów - zadanie 4  NY85  5
 liczba ciągów - zadanie 2  MikolajB  15
 Liczba ciągów - zadanie 3  lennyh  1
 Liczba drzew o zadanych stopniach wierzchołków  Annoyer13  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl