szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 10 sie 2013, o 14:07 
Użytkownik

Posty: 5
Lokalizacja: Warszawa
Ile jest ciągów o długości 2n takich, że każda liczba 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 C-zbiór ciągów o długości 2n takich że każda liczba i występuje dokładnie dwa razy.
|C| = {2n\choose 2}  \cdot  {2n-2\choose 2} \cdot ... \cdot {2\choose 2} =  \frac{(2n)!}{2^{n}}

A_{j} - zbiór ciągów o długości 2n takich że każda liczba i występuje dokładnie dwa razy i j-ta liczba występuje dwa razy pod rząd.

|A_{j}| = \frac{(2n-1)!}{2^{n-1}}
Wówczas odpowiedź wynosi: |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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Kobieta Offline
PostNapisane: 10 sie 2013, o 16:35 
Użytkownik
Avatar użytkownika

Posty: 321
Lokalizacja: Gówniak k. Bukowiny
Mysle, ze jst dobrze.
(Tylko ja bym od razu napisala wyrazenie dla |C| bo to liczba permutacji zbioru 2n elementowego, czyli (2n)!, ktora trzeba podzielic przez 2^n, bo kazdy z n elementow wystepuje w dwoch egzemplarzach i permutacje takich par sa rowne.)
Góra
Mężczyzna Offline
PostNapisane: 10 sie 2013, o 19:57 
Użytkownik

Posty: 1871
Lokalizacja: Staszów/Warszawa
Barbara777 napisał(a):
Mysle, ze jst dobrze.
(Tylko ja bym od razu napisala wyrazenie dla |C| bo to liczba permutacji zbioru 2n elementowego, czyli (2n)!, ktora trzeba podzielic przez 2^n, bo kazdy z n elementow wystepuje w dwoch egzemplarzach i permutacje takich par sa rowne.)

Ale sąsiednie wyrazy są różne.
Góra
Mężczyzna Offline
PostNapisane: 21 mar 2015, o 00:06 
Użytkownik

Posty: 5593
Lokalizacja: Kraków
To też z Nierozwiązanych...
Ukryta treść:    
Góra
Kobieta Offline
PostNapisane: 21 mar 2015, o 09:26 
Użytkownik
Avatar użytkownika

Posty: 2505
Rzeczywiście OEIS twierdzi, że nie da się zwinąć, ale można wyciągnąć funkcję tworzącą: jeśli

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 a_n/n! jest

\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 :D
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile jest dzielnikow liczby  Anonymous  6
 ile jest liczb 2cyfr/3cyfr, 5cyfr o pocz 12, bez cyfr 4 i 5?  Anonymous  1
 permutacje/ile jest sposobow ustawien/ -prosba o sprawdzenie  alamakota  3
 ile jest liczb trzycyfrowych, mniejszych od 555  Anonymous  1
 Ilość różnych wyrazów o długości n z zastrzeżeniem  apacz  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl