Matematyka.pl

Zadanie: Znajdź wzór na liczbę ciągów długości 2n, w których każda liczba z przedziału 1..n występuje dokładnie dwa razy i takich, że sąsiednie liczby są różne.

Próbuje to uderzać z zasady włączeń-wyłączeń.

\(\displaystyle{ \left| U _{n} \right| = \prod_{k=0}^{n} {2n-2k \choose 2}}\) Moc uniwersum, wybieramy 2 miejsca w ciągu i wstawiamy tam dany element itd.

i-ta własność: i stoi w ciągu obok drugiego i: \(\displaystyle{ U_{n-1}*(2n-1)}\) - pozostałe 2(n-1) elementy ustawiamy dowolnie, a potem na (2n-1) możemy wstawić parę i
i-ta i j-ta własność: \(\displaystyle{ U_{n-2}*(2n-3)^2}\) 2(n-2) elementy ustawiamy dowolnie, na (2n-3) mozemy wstawić i, a potem na tyle samo sposobów j-ty.

Widać, że wzór wychodzi taki: \(\displaystyle{ \sum_{k=0}^{n} U _{n-k} \cdot {n \choose k} \cdot (-1)^k \cdot (2n-2k+1)^k}\)

Nie wiem, czy to dobrze i czy to wystarcza, bo wysumować będzie raczej niełatwo

Ja zrobiłem trochę inaczej. Niech \(\displaystyle{ D_{n}}\) oznacza ciąg długości 2n spełniający podane własności .
Oczywiście\(\displaystyle{ D_{1}=0}\),a \(\displaystyle{ D_{2}=2}\)
Załóżmy,że znamy \(\displaystyle{ D_{n}}\)wyliczymy \(\displaystyle{ D_{n+1}}\).Weźmy dowolny ciąg spełniający warunki zadania. nowy uzyskuje się tak,że pierwszą (n+1)-kę wstawiamy dowolnie,a drugą też,tyle,że trzeba wyłączyć ustawienia,że ta druga (n+1)-ka stoi tuż za,lub tuż przed pierwszą,czyli dwa ustawienia.Zatem
\(\displaystyle{ D_{n+1}=D_{n} \cdot 2n+1 \cdot 2n}\)iterując tę równość jeszcze n-1 razy mamy:
\(\displaystyle{ D_{n+1}=D{2} \cdot 2n+1 \cdot 2n \cdot 2n-1 \cdot \dots \cdot 5 \cdot 4 \cdot D_{2}}\)= frac{(2n+1)!}{3}.
Czyli ciągów jest \(\displaystyle{ \frac{(2n-1)!}{3}}\) jeśli n>1 i 0 w przeciwnym wypadku.