Liczba ciągów
-
- Użytkownik
- Posty: 541
- Rejestracja: 11 maja 2016, o 13:36
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Podziękował: 497 razy
- Pomógł: 5 razy
Liczba ciągów
Niech \(\displaystyle{ n\geq 5}\) będzie liczbą naturalną. Rozważmy \(\displaystyle{ n}\)-wyrazowe ciągi o wyrazach \(\displaystyle{ A, B, C, D, E}\). Ile jest wszystkich takich ciągów, w których:
a.) każde dwa kolejne wyrazy są różne?
b.) występują co najwyżej dwa różne wyrazy?
c.) każde pięć kolejnych wyrazów jest różnych?
Narazie zaciąłem się przy podpunkcie b.)
a.) każde dwa kolejne wyrazy są różne?
b.) występują co najwyżej dwa różne wyrazy?
c.) każde pięć kolejnych wyrazów jest różnych?
Narazie zaciąłem się przy podpunkcie b.)
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Liczba ciągów
b) Nie jest to szczególnie błyskotliwe, ale można to rozdzielić na przypadek bez różnych wyrazów i z dokładnie dwoma różnymi wyrazami. W tym pierwszym przypadku jest ich oczywiście \(\displaystyle{ 5}\), a w tym drugim \(\displaystyle{ {5\choose 2}\left(2^{n}-2\right)}\)
Na \(\displaystyle{ {5\choose 2}}\) sposobów wybieramy dwie litery, które pojawią się w ciągu, a następnie na \(\displaystyle{ 2^{n}-2}\) sposobów wybieramy pozycje, na których pojawi się jedna litera (na przykład ta wcześniej wystepująca w alfabecie, cokolwiek), a na pozostałych miejscach wstawiamy tę druga (odejmujemy przypadek samych liter pierwszego rodzaju i żadnych liter pierwszego rodzaju).
Łącznie więc dostajemy \(\displaystyle{ 5+{5\choose 2}\left(2^{n}-2\right)}\) ciągów spełniających warunki.
c) Nie jestem pewien, czy poprawnie rozumiem treść zadania, ale jeśli tak, to okazuje się, że ustawienie liter na pięciu początkowych pozycjach determinuje już wszystkie wyrazy. Najłatwiej to prześledzić dla \(\displaystyle{ n=5,6,7,8,9}\) i uogólnić (albo szybciej uogólnić).
Na \(\displaystyle{ {5\choose 2}}\) sposobów wybieramy dwie litery, które pojawią się w ciągu, a następnie na \(\displaystyle{ 2^{n}-2}\) sposobów wybieramy pozycje, na których pojawi się jedna litera (na przykład ta wcześniej wystepująca w alfabecie, cokolwiek), a na pozostałych miejscach wstawiamy tę druga (odejmujemy przypadek samych liter pierwszego rodzaju i żadnych liter pierwszego rodzaju).
Łącznie więc dostajemy \(\displaystyle{ 5+{5\choose 2}\left(2^{n}-2\right)}\) ciągów spełniających warunki.
c) Nie jestem pewien, czy poprawnie rozumiem treść zadania, ale jeśli tak, to okazuje się, że ustawienie liter na pięciu początkowych pozycjach determinuje już wszystkie wyrazy. Najłatwiej to prześledzić dla \(\displaystyle{ n=5,6,7,8,9}\) i uogólnić (albo szybciej uogólnić).
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Liczba ciągów
Co do a) możemy napisać:
Uogólnijmy:
\(\displaystyle{ a(n,k)}\) - są to ciągi składające się z\(\displaystyle{ k}\) różnych elementów o długości \(\displaystyle{ n}\), tak żeby żadne dwa kolejne się nie powtarzały...
łatwo zauważyć , że:
\(\displaystyle{ a(1,5)=5}\)
\(\displaystyle{ a(2,5)=5 \cdot 4}\)
ogólnie:
\(\displaystyle{ a(n,5)=a(n-1,5) \cdot 4}\)
Uogólnijmy:
\(\displaystyle{ a(n,k)}\) - są to ciągi składające się z\(\displaystyle{ k}\) różnych elementów o długości \(\displaystyle{ n}\), tak żeby żadne dwa kolejne się nie powtarzały...
łatwo zauważyć , że:
\(\displaystyle{ a(1,5)=5}\)
\(\displaystyle{ a(2,5)=5 \cdot 4}\)
ogólnie:
\(\displaystyle{ a(n,5)=a(n-1,5) \cdot 4}\)
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Liczba ciągów
Toś Ameryki w tym momencie nie odkrył...Mi wyszło w pierwszym podpunkcie \(\displaystyle{ 5 \cdot 4^{n-1}}\)
A myślisz, że co ja napisaem może co inne?
Czy Pan Matoł Matołecki to kto inny niż Pan Matołecki Matoł?
Mieli już u was rekurencję???
-
- Użytkownik
- Posty: 541
- Rejestracja: 11 maja 2016, o 13:36
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Podziękował: 497 razy
- Pomógł: 5 razy
Re: Liczba ciągów
Czyli dobrze rozumiem, że prawidłowa odpowiedź do tego podpunktu to \(\displaystyle{ 5!=120}\)?Premislav pisze: ↑9 kwie 2020, o 17:46 c) Nie jestem pewien, czy poprawnie rozumiem treść zadania, ale jeśli tak, to okazuje się, że ustawienie liter na pięciu początkowych pozycjach determinuje już wszystkie wyrazy. Najłatwiej to prześledzić dla \(\displaystyle{ n=5,6,7,8,9}\) i uogólnić (albo szybciej uogólnić).
-
- Użytkownik
- Posty: 541
- Rejestracja: 11 maja 2016, o 13:36
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Podziękował: 497 razy
- Pomógł: 5 razy
Re: Liczba ciągów
Dziękuję bardzo za podpowiedzi. Na koniec pytanie zagwozdka: Jak dyskutować z argumentami, że przecież z dowolności wyboru \(\displaystyle{ n}\), w każdym z tych podpunktów jest nieskończenie wiele ciągów więc:
a.) nieskończenie wiele
b.) nieskończenie wiele
c.) nieskończenie wiele
?
a.) nieskończenie wiele
b.) nieskończenie wiele
c.) nieskończenie wiele
?
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Liczba ciągów
We fragmencie (zakładam, że zacytowałeś oryginalną treść zadania)
\(\displaystyle{ n}\) zostaje ustalone. Ktokolwiek z tym dyskutuje, nie zna konwencji lub jest trollem.Niech \(\displaystyle{ n\ge 5}\) będzie liczbą naturalną