Znajdź liczbę ciągów długości \(\displaystyle{ 2n}\) takich , ze każda liczba \(\displaystyle{ 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 \(\displaystyle{ (2n)!}\)
i teraz będziemy odejmować przypadki kiedy cyfra/liczba a jest obok liczby a
Czyli spośród \(\displaystyle{ 2n}\) wybieramy \(\displaystyle{ 2}\)miejsca np na \(\displaystyle{ 2}\) dwójki które będą obok siebie następnie spośród \(\displaystyle{ 2n-2}\) wybieramy kolejne \(\displaystyle{ 2}\) cyfry które będą obok siebie itd itp
czyli
\(\displaystyle{ {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 \(\displaystyle{ n!}\) zważywszy na kolejność wystąpień poszczególnych cyfr
taka moja myśl, czy dobra?
Liczba ciągów
-
aolo23
- Użytkownik
- Posty: 307
- Rejestracja: 5 sty 2016, o 13:01
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 118 razy
- Pomógł: 2 razy
Liczba ciągów
Ostatnio zmieniony 8 kwie 2018, o 20:56 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
arek1357
- Użytkownik
- Posty: 5736
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 razy
Liczba ciągów
zasada włączeń i wyłączeń...
\(\displaystyle{ 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}}\)
\(\displaystyle{ a(n,k,s)}\) - ilość ciągów o długości \(\displaystyle{ k}\) , w których występuje \(\displaystyle{ n}\) liczb, oraz \(\displaystyle{ s}\) par takich samych podwójnych liczb, ale takich ciągów, że dwie takie same liczby nie stoją koło siebie...
\(\displaystyle{ n}\)- ilość liczb w ciągu
\(\displaystyle{ k}\) - długość ciągu
\(\displaystyle{ s}\) - ilość par czyli tych samych liczb
Oczywiście u Ciebie jest:
\(\displaystyle{ k=2n, s=n}\)
Rozpatrzyłem przypadek bardziej ogólny...
\(\displaystyle{ 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}}\)
\(\displaystyle{ a(n,k,s)}\) - ilość ciągów o długości \(\displaystyle{ k}\) , w których występuje \(\displaystyle{ n}\) liczb, oraz \(\displaystyle{ s}\) par takich samych podwójnych liczb, ale takich ciągów, że dwie takie same liczby nie stoją koło siebie...
\(\displaystyle{ n}\)- ilość liczb w ciągu
\(\displaystyle{ k}\) - długość ciągu
\(\displaystyle{ s}\) - ilość par czyli tych samych liczb
Oczywiście u Ciebie jest:
\(\displaystyle{ k=2n, s=n}\)
Rozpatrzyłem przypadek bardziej ogólny...
Ostatnio zmieniony 8 kwie 2018, o 23:01 przez arek1357, łącznie zmieniany 2 razy.
-
arek1357
- Użytkownik
- Posty: 5736
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 razy
Liczba ciągów
\(\displaystyle{ (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
\(\displaystyle{ n-s}\) - tyle zostało różnych liczb, które nie mają par
\(\displaystyle{ k-2s}\) - tyle zostało miejsc na których rozmieszczono te liczby
\(\displaystyle{ {n-s \choose k-2s}}\) - na tyle sposobów możemy wybrać liczby na tych miejscach...
\(\displaystyle{ n-s}\) - tyle zostało różnych liczb, które nie mają par
\(\displaystyle{ k-2s}\) - tyle zostało miejsc na których rozmieszczono te liczby
\(\displaystyle{ {n-s \choose k-2s}}\) - na tyle sposobów możemy wybrać liczby na tych miejscach...