Niech \(\displaystyle{ n\in \mathbb{N}-\left \{ 0,1 \right \}}\). Zliczyć ile jest ciągów \(\displaystyle{ (a_1,a_2,...a_{n+2})}\) o wyrazach z \(\displaystyle{ [n]}\) takich, że \(\displaystyle{ (\forall x\in [n])(\exists i)a_i=x}\).
Rozwiązanie według mnie.
Każdy wyraz z \(\displaystyle{ [n]}\) musi być użyty, a jako, że ciąg jest funkcją, to dla każdego \(\displaystyle{ a_i}\) jest maksymalnie jeden wyraz z tego zbioru. Zatem mamy \(\displaystyle{ (n+2)(n+1)\cdot...\cdot3}\) możliwości dobrania \(\displaystyle{ a_i}\) dla każdego x ze zbioru [n].
Zostają nam dwa niewykorzystane wyrazy \(\displaystyle{ a_i}\) dla których możemy wybrać dowolne n, więc tutaj mamy \(\displaystyle{ n^2}\) możliwości.
W sumie takich ciągów jest \(\displaystyle{ (n+2)(n+1)\cdot...\cdot 3 \cdot n^2}\)
Czy to jest dobrze? Jeśli nie, to gdzie jest błąd?
Zliczyć ile jest ciągów o wyrazach z [n]
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Zliczyć ile jest ciągów o wyrazach z [n]
Odpowiedź jest nieprawidłowa, co łatwo sprawdzić na przykład dla \(\displaystyle{ n=2}\) - wtedy wszystkich ciągów jest \(\displaystyle{ 16}\), więc takich o które nam chodzi nie może być \(\displaystyle{ 48}\). Błąd polega na wielokrotnym liczeniu tych samych ciągów, np. dla \(\displaystyle{ n=2}\) ciąg \(\displaystyle{ (1,1,1,2)}\) liczony jest wiele razy zależnie od tego, która z jedynek została wybrana jako pierwsza.
Prawidłowy wynik to:
\(\displaystyle{ \binom n1 \cdot \binom{n+2}3\cdot (n-1)! + \binom n2 \cdot\binom{n+2}{2} \cdot \binom n2 \cdot (n-2)!}\)
Pierwszy składnik to zliczanie ciągów, w których jakaś wartość przyjęta jest trzy razy, a reszta po razie; a drugi składnik to zliczanie ciągów, w których dwie wartości przyjęte są po dwa razy, a reszta po razie.
Wynik można uprościć do:
\(\displaystyle{ \frac{(n+2)!\cdot n\cdot (3n+1)}{24}}\)
i widać, że się zgadza np. dla \(\displaystyle{ n=2}\), bo istotnie wtedy jest \(\displaystyle{ 14=16-2}\) dobrych ciągów, tzn. od wszystkich wystarczy odjąć dwa stałe.
Q.
Prawidłowy wynik to:
\(\displaystyle{ \binom n1 \cdot \binom{n+2}3\cdot (n-1)! + \binom n2 \cdot\binom{n+2}{2} \cdot \binom n2 \cdot (n-2)!}\)
Pierwszy składnik to zliczanie ciągów, w których jakaś wartość przyjęta jest trzy razy, a reszta po razie; a drugi składnik to zliczanie ciągów, w których dwie wartości przyjęte są po dwa razy, a reszta po razie.
Wynik można uprościć do:
\(\displaystyle{ \frac{(n+2)!\cdot n\cdot (3n+1)}{24}}\)
i widać, że się zgadza np. dla \(\displaystyle{ n=2}\), bo istotnie wtedy jest \(\displaystyle{ 14=16-2}\) dobrych ciągów, tzn. od wszystkich wystarczy odjąć dwa stałe.
Q.