Ile jest ciągów długości 2n...

[pavel3643]

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.

[Barbara777]

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

[robertm19]

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.

[mol_ksiazkowy]

To też z Nierozwiązanych...

Ukryta treść:    

rozwijając ten pomysł: tj. ze wzoru włączeń i wyłączeń:
\(\displaystyle{ | X \backslash \bigcup_{j=1}^n A_j | = \sum_{k=0}^n (-1)^k \sum_{|J|= k} |\bigcap_{j \in J} A_j| = \sum_{k=0}^n (-1)^k {n \choose k} {2n- k \choose k} k! \frac{(2n-2k)!}{2^{n-k}} = \sum_{k=0}^n (-1)^k {n \choose k} \frac{(2n-k)!}{2^{n-k}}}\)
zbiór \(\displaystyle{ A_j}\) to taki który ma wszystkie ustawienia z liczbami \(\displaystyle{ j}\) obok siebie.

Wynika to z twierdzenia:
Ilość \(\displaystyle{ k}\) elementowych podzbiorów zbioru \(\displaystyle{ \{ 1, ... n \}}\), w których nie ma żadnych kolejnych liczb to
\(\displaystyle{ {n-k+1 \choose k}}\)
Suma ta raczej nie da się już zwinąć (uprościć); dla \(\displaystyle{ n=2}\) jest równa \(\displaystyle{ n=2}\) (ciągi \(\displaystyle{ (1, 2, 1, 2)}\) i \(\displaystyle{ (2, 1, 2, 1)}\)). dla \(\displaystyle{ n=3}\) jest równa \(\displaystyle{ 30}\) itd.

[Medea 2]

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