Matematyka.pl

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.

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.)

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.)

Ale sąsiednie wyrazy są różne.

To też z Nierozwiązanych...

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