Ile jest ciągów o długości \(\displaystyle{ 2n}\) takich, że każda liczba \(\displaystyle{ i\in
\left\{1,2, ... ,n \right\}}\) występuje dokładnie dwa razy oraz każde sąsiednie dwa wyrazy są różne?
Gdzie są błędy w moim rozumowaniu?
Niech \(\displaystyle{ C}\)-zbiór ciągów o długości \(\displaystyle{ 2n}\) takich że każda liczba \(\displaystyle{ i}\) występuje dokładnie dwa razy.
\(\displaystyle{ |C| = {2n\choose 2} \cdot {2n-2\choose 2} \cdot ... \cdot {2\choose 2} = \frac{(2n)!}{2^{n}}}\)
\(\displaystyle{ A_{j}}\) - zbiór ciągów o długości \(\displaystyle{ 2n}\) takich że każda liczba \(\displaystyle{ i}\) występuje dokładnie dwa razy i j-ta liczba występuje dwa razy pod rząd.
\(\displaystyle{ |A_{j}| = \frac{(2n-1)!}{2^{n-1}}}\)
Wówczas odpowiedź wynosi: \(\displaystyle{ |C| - |\bigcup_{k=1}^{n}A_k|}\)
Oczywiście trzeba jeszcze policzyć tę sumę mnogościową z zasady W/W. Chodzi mi o te dwa wzorki które napisałem.
Ile jest ciągów długości 2n...
-
- Użytkownik
- Posty: 5
- Rejestracja: 10 sie 2013, o 12:27
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
Ile jest ciągów długości 2n...
Ostatnio zmieniony 21 mar 2015, o 09:26 przez yorgin, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
Powód: Symbol mnożenia to \cdot.
- Barbara777
- Użytkownik
- Posty: 316
- Rejestracja: 13 maja 2013, o 18:28
- Płeć: Kobieta
- Lokalizacja: Gówniak k. Bukowiny
- Podziękował: 16 razy
- Pomógł: 115 razy
Ile jest ciągów długości 2n...
Mysle, ze jst dobrze.
(Tylko ja bym od razu napisala wyrazenie dla \(\displaystyle{ |C|}\) bo to liczba permutacji zbioru \(\displaystyle{ 2n}\) elementowego, czyli \(\displaystyle{ (2n)!}\), ktora trzeba podzielic przez \(\displaystyle{ 2^n}\), bo kazdy z \(\displaystyle{ n}\) elementow wystepuje w dwoch egzemplarzach i permutacje takich par sa rowne.)
(Tylko ja bym od razu napisala wyrazenie dla \(\displaystyle{ |C|}\) bo to liczba permutacji zbioru \(\displaystyle{ 2n}\) elementowego, czyli \(\displaystyle{ (2n)!}\), ktora trzeba podzielic przez \(\displaystyle{ 2^n}\), bo kazdy z \(\displaystyle{ n}\) elementow wystepuje w dwoch egzemplarzach i permutacje takich par sa rowne.)
-
- Użytkownik
- Posty: 1847
- Rejestracja: 8 lip 2008, o 21:16
- Płeć: Mężczyzna
- Lokalizacja: Staszów/Warszawa
- Podziękował: 7 razy
- Pomógł: 378 razy
Ile jest ciągów długości 2n...
Ale sąsiednie wyrazy są różne.Barbara777 pisze:Mysle, ze jst dobrze.
(Tylko ja bym od razu napisala wyrazenie dla \(\displaystyle{ |C|}\) bo to liczba permutacji zbioru \(\displaystyle{ 2n}\) elementowego, czyli \(\displaystyle{ (2n)!}\), ktora trzeba podzielic przez \(\displaystyle{ 2^n}\), bo kazdy z \(\displaystyle{ n}\) elementow wystepuje w dwoch egzemplarzach i permutacje takich par sa rowne.)
- mol_ksiazkowy
- Użytkownik
- Posty: 11367
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
- Medea 2
- Użytkownik
- Posty: 2491
- Rejestracja: 30 lis 2014, o 11:03
- Płeć: Kobieta
- Podziękował: 23 razy
- Pomógł: 479 razy
Ile jest ciągów długości 2n...
Rzeczywiście OEIS twierdzi, że nie da się zwinąć, ale można wyciągnąć funkcję tworzącą: jeśli
\(\displaystyle{ a_n = \sum_{k=0}^n (-1)^k {n \choose k} \frac{(2n-k)!}{2^{n-k}},}\)
to (prawie?) wykładniczą funkcją tworzącą dla \(\displaystyle{ a_n/n!}\) jest
\(\displaystyle{ \sum_{n=0}^\infty \frac{a_n}{(n!)^2} (-x)^n = \frac{\exp \left(\sqrt{1+2x}-1\right)}{\sqrt{1+2x}}}\)
Podziwiam ludzi, którzy są w stanie wyprowadzać takie wzory
\(\displaystyle{ a_n = \sum_{k=0}^n (-1)^k {n \choose k} \frac{(2n-k)!}{2^{n-k}},}\)
to (prawie?) wykładniczą funkcją tworzącą dla \(\displaystyle{ a_n/n!}\) jest
\(\displaystyle{ \sum_{n=0}^\infty \frac{a_n}{(n!)^2} (-x)^n = \frac{\exp \left(\sqrt{1+2x}-1\right)}{\sqrt{1+2x}}}\)
Podziwiam ludzi, którzy są w stanie wyprowadzać takie wzory