Zliczanie ciągów

[michals95]

Zliczyć, ile jest ciągów długości długości \(\displaystyle{ 2n}\) o wyrazach ze zbioru \(\displaystyle{ 2n}\), takich, że żadne dwa sąsiednie wyrazy nie sumują się do \(\displaystyle{ 2n}\)
Próbowałem zrobić to zadanie korzystając z zasady w/w, jednak po sprawdzeniu dla kilku przypadków wynik nie był prawidłowy. Wydaje mi się, że trzeba tu z tej zasady skorzystać, mam jednak klopot z ustaleniem, jak zliczać \(\displaystyle{ A_{j}}\).

[M Maciejewski]

Czy mają to być permutacje? Bo jeśli nie, to możemy to zrobić tak:
pierwszy wyraz \(\displaystyle{ a_1}\) jest dowolny, wybieramy do na \(\displaystyle{ 2n}\) sposobów.
Drugi wyraz nie może być równy \(\displaystyle{ 2n-a_1}\), więc wybieramy go na \(\displaystyle{ 2n-1}\) sposobów.
Trzeci również na \(\displaystyle{ 2n-1}\) sposobów, itd.

[arek1357]

Ja obstaję za zasadą włączania i wyłączania:

\(\displaystyle{ (2n)!-\sum_{i=0}^{n-1} {n-1 \choose i}2^i(2n-i)!(-1)^i}\)

\(\displaystyle{ n-1}\) - tyle jest par takich, że suma daje \(\displaystyle{ 2n}\)

\(\displaystyle{ 2^i}\) to ilość permutacji tych par między sobą

\(\displaystyle{ (2n-i)!}\) - ilość permutacji i par sumujących się do \(\displaystyle{ 2n}\) oraz resztę liczb pojedynczych.

[Majeskas]

Czy mógłbyś wyjaśnić, skąd się to wzięło?

[Mruczek]

Po pierwsze, michals95, doprecyzuj treść, podaj dokładnie zbiór z jakiego mogą pochodzić wyrazy ciągu, to wtedy będziemy mogli Ci pomóc.

Czy mają to być permutacje? Bo jeśli nie, to możemy to zrobić tak:
pierwszy wyraz \(\displaystyle{ a_1}\) jest dowolny, wybieramy do na \(\displaystyle{ 2n}\) sposobów.
Drugi wyraz nie może być równy \(\displaystyle{ 2n-a_1}\), więc wybieramy go na \(\displaystyle{ 2n-1}\) sposobów.
Trzeci również na \(\displaystyle{ 2n-1}\) sposobów, itd.

M Maciejewski, przy założeniu, że wyrazy są ze zbioru \(\displaystyle{ \left\{ 1,2,...,2n\right\}}\) (a chyba tak założyłeś), Twoje rozwiązanie jest błędne, bo jeżeli wyrazem jest \(\displaystyle{ 2n}\), to następny wyraz może być dowolny.

Rozwiązanie arek1357 zakłada, że chcemy zliczać permutacje o własności z zadania.
Jest tam błąd w dolnym indeksie sumy - powinno być od 1, a nie od 0, a także powinno być \(\displaystyle{ (-1) ^{i + 1}}\) zamiast \(\displaystyle{ (-1) ^{i}}\).
Łatwiej jest policzyć permutacje w których własność podana w zadaniu nie zachodzi tzn. chcemy policzyć liczbę permutacji posiadających jakieś dwa sąsiednie wyrazy o sumie \(\displaystyle{ 2n}\). Za zbiór \(\displaystyle{ A_{j}}\) przyjęty jest zbiór permutacji posiadających parę sąsiednich wyrazów równych np. \(\displaystyle{ j}\) oraz \(\displaystyle{ 2n-j}\). Korzystamy z faktu, że moc części wspólnej dowolnych \(\displaystyle{ i}\) spośród zbiorów \(\displaystyle{ A_{j}}\) (tzn liczba permutacji mających \(\displaystyle{ i}\) określonych par sąsiednich wyrazów o sumie \(\displaystyle{ 2n}\)) jest taka sama (niezależnie od tego jakie te pary są) i wynosi \(\displaystyle{ 2^i(2n-i)!}\) (jest tak, bo w permutacji każda para wyrazów o sumie \(\displaystyle{ 2n}\) musi być rozłączna i występuje tylko raz) - \(\displaystyle{ 2^{i}}\) uwzględnia że, każda taka para elementów może być ustawiona na dwa sposoby, a \(\displaystyle{ (2n-i)!}\) permutuje pary wraz z pojedynczymi wyrazami. Reszta poniższego wzoru wynika ze wzoru na zasadę włączeń i wyłączeń.
Dlatego permutacji zawierających przynajmniej jedną parę sąsiednich wyrazów o sumie \(\displaystyle{ 2n}\) jest \(\displaystyle{ \left| A_{1} \cup A_{2} \cup... \cup A_{n-1}\right| = \sum_{i=1}^{n-1} {n-1 \choose i}2^i(2n-i)!(-1)^{i+1}}\).
Na koniec odejmujemy tą sumę od liczby wszystkich permutacji otrzymując szukany wynik.

[Majeskas]

Po pierwsze, michals95, doprecyzuj treść, podaj dokładnie zbiór z jakiego mogą pochodzić wyrazy ciągu, to wtedy będziemy mogli Ci pomóc.

Tam po prosru zabrakło nawiasu kwadratowego. Powinno być:

Zliczyć, ile jest ciągów długości długości \(\displaystyle{ 2n}\) o wyrazach ze zbioru \(\displaystyle{ [2n]}\), takich, że […]

Jeśli ktoś znajdzie rozwiązanie przy prawidłowej treści, będę wdzięczny. Przy zwykłym zastosowaniu zasady włączeń i wyłączeń pojawia się problem.

[Mruczek]

Co to zmienia, że tam jest ten nawias kwadratowy? Nie znam takiego oznaczenia z nawiasem kwadratowym - wyjaśnij o jaki zbiór Ci chodzi.

Moim zdaniem można łatwo napisać wzór rekurencyjny na liczbę tych ciągów, aczkolwiek rozwiązać tą rekurencję będzie ciężej. W poprzednim rozwiązaniu problem pojawiał się przy wyrazie równym \(\displaystyle{ 2n}\), no to można oddzielnie policzyć ciągi kończące się tym wyrazem. Niech np. \(\displaystyle{ a_{n}}\) to ciągi kończące się \(\displaystyle{ 2n}\), a \(\displaystyle{ b_{n}}\) to ciągi kończące się wyrazem innym niż \(\displaystyle{ 2n}\). Dalszą część napiszę, jak będę wiedział o jaki zbiór chodzi.

[dec1]

\(\displaystyle{ [n]=\{ k\in \NN_{+} \,|\, k\leq n\}}\)

[Mruczek]

No dobra, to tak jak myślałem, tak więc ta rekurencja będzie wyglądała wg mnie tak (przy założeniach z poprzedniego postu):

\(\displaystyle{ a_{1} = 1}\) - jeden ciąg składający się z wyrazu \(\displaystyle{ 2n}\)
\(\displaystyle{ a_{i} = a_{i-1} + b_{i-1}}\) - jeżeli teraz dajemy wyraz \(\displaystyle{ 2n}\) to na poprzedniej pozycji może być dowolny wyraz
\(\displaystyle{ b_{1} = 2n-1}\) - na pierwszą pozycję dajemy dowolny wyraz mniejszy od \(\displaystyle{ 2n}\)
\(\displaystyle{ b_{i} = (2n-1) a_{i-1} + (2n-2) b_{i-1}}\) - jeżeli na poprzedniej pozycji był wyraz \(\displaystyle{ 2n}\), to na kolejnej może być dowolny mniejszy od \(\displaystyle{ 2n}\), a jeżeli na poprzedniej pozycji był wyraz mniejszy od \(\displaystyle{ 2n}\) to na nowej może być każdy mniejszy od \(\displaystyle{ 2n}\) z wyjątkiem tego, który sumuje się do \(\displaystyle{ 2n}\).

Wynik to \(\displaystyle{ a_{2n}+ b_{2n}}\).

[Majeskas]

Nie ma co przepraszać, a zmienia tyle, że dość popularnym oznaczeniem w kręgach matematykodyskretnych jest \(\displaystyle{ [n]:=\left\{ 1,2,\ldots,n\right\}}\). Ale raczej nie ma rangi powszechnie przyjętego, więc rozumiem, że można go nie znać.

Jeśli chodzi o rekurencję, to był to mój pierwszy pomysł, tylko zapowiadała się paskudnie, więc szybko zrezygnowałem. Jak będzie mi się chciało, to może tak zaatakuję. Ona chyba powinna wyjść liniowa, tylko ze zmiennymi współczynnikami, a na takie są, zdaje się, sposoby.

-- 19 sierpnia 2016, 23:16 --

Jak się nad tym zastanowiłem, to to zadanie w ogóle nie nadaje się na rozwiązanie przez rekurencję. Jeśli bierzemy dobry ciąg długości \(\displaystyle{ 2n}\) i zastanawiamy się, jak można go rozbudować do dobrego ciągu długości \(\displaystyle{ 2n+2}\), to problem polega na tym, że przy ciągu długości \(\displaystyle{ 2n+2}\) dysponujemy innym zasobem wyrazów: \(\displaystyle{ \left\{ 1,2,\ldots,2n+2\right\}}\). Tak więc nie ma jak budować takich równań rekurencyjnych jak wyżej.

-- 19 sierpnia 2016, 23:18 --

Nie mogę edytować posta, więc wrzucam go jeszcze raz w poprawionej wersji:

Jak się nad tym zastanowiłem, to to zadanie w ogóle nie nadaje się na rozwiązanie przez rekurencję. Jeśli bierzemy dobry ciąg długości \(\displaystyle{ 2n}\) i zastanawiamy się, jak można go rozbudować do dobrego ciągu długości \(\displaystyle{ 2n+2}\), to problem polega na tym, że przy ciągu długości \(\displaystyle{ 2n+2}\) dysponujemy innym zasobem wyrazów: \(\displaystyle{ \left\{ 1,2,\ldots,2n+2\right\}}\). Tak więc nie ma jak budować takich równań rekurencyjnych jak wyżej.

[Majeskas]

Właśnie mnie olśniło. To zadanie da się łatwo rozwiązać z zasady włączeń i wyłączeń. Trzeba tylko dobrze definiować zbiory, których suma stanowi zbiór "złych" ciągów.
Niech \(\displaystyle{ A_i}\) będzie zbiorem tych ciągów długości \(\displaystyle{ 2n}\) o wyrazach z \(\displaystyle{ [2n]}\), w których element \(\displaystyle{ i}\) występuje obok \(\displaystyle{ 2n-i}\). Szukamy \(\displaystyle{ |A_1\cup A_2\cup\ldots\cup A_n|}\). Mamy \(\displaystyle{ |A_i|=(2n-1)\cdot2\cdot(2n)^{2n-2}}\) - traktujemy parę \(\displaystyle{ (i,2n-i)}\) jako jeden element, dla którego wybieramy jedno z \(\displaystyle{ 2n-1}\) miejsc, na \(\displaystyle{ 2}\) sposoby ustalamy kolejność elementów w parze; pozostałe \(\displaystyle{ 2n-2}\) miejsca zapełniamy dowolnie.

\(\displaystyle{ |A_i\cap A_j|={2n-2\choose 2}\cdot 2!\cdot2^2\cdot(2n)^{2n-4}=\frac{(2n-2)!}{(2n)!}\cdot2^2\cdot(2n)^{2n-4}}\)

Ostateczna odpowiedź:

\(\displaystyle{ \sum_{k=0}^n\frac{(-2)^k\cdot(2n-k)!\cdot(2n)^{2n-2k}}{(2n-2k)!}}\)

[Mruczek]

Tu jest błąd. Jeżeli mamy złą parę \(\displaystyle{ (n, n)}\) to nie permutujemy jej przez \(\displaystyle{ 2}\).
Trzeba oddzielnie zliczyć przecięcia zbiorów zawierających \(\displaystyle{ (n, n)}\) i nie zawierających jej.

To co zrobiłeś to tak naprawdę przeniesienie rozwiązania z zasadą włączeń i wyłączeń z przypadku gdy rozważaliśmy permutacje na ciągi.

[Majeskas]

Tu jest błąd. Jeżeli mamy złą parę \(\displaystyle{ (n, n)}\) to nie permutujemy jej przez \(\displaystyle{ 2}\).
Trzeba oddzielnie zliczyć przecięcia zbiorów zawierających \(\displaystyle{ (n, n)}\) i nie zawierających jej.

Słuszna uwaga, dziękuję. Pominąłem też jeden czynnik w wyrazie ogólnym sumy. Teraz powinno być dobrze:

\(\displaystyle{ (2n)^{2n}-\sum_{k=1}^n(-1)^{k-1}\left( {n-1 \choose k} {2n-k \choose k}\cdot k!\cdot2^k\cdot(2n)^{2n-2k}+{n-1 \choose k-1} {2n-k \choose k}\cdot k!\cdot2^{k-1}\cdot(2n)^{2n-2k} \right)}\)

Po uproszczeniach:

\(\displaystyle{ (2n)^{2n}-\sum_{k=1}^n \frac{(-2)^{k-1}\cdot(2n-k)!\cdot(2n)^{2n-2k}}{(2n-2k)!}\left( {n \choose k} + {n-1 \choose k} \right)}\)

To co zrobiłeś to tak naprawdę przeniesienie rozwiązania z zasadą włączeń i wyłączeń z przypadku gdy rozważaliśmy permutacje na ciągi.

Możliwe, nie twierdzę, że odkryłem Amerykę. Potrzebowałem rozwiązać to zadanie i najpierw źle do niego podszedłem, używając zasady włączeń i wyłączeń, tzn. definiowałem zbiory \(\displaystyle{ A_i}\) tak, że przecięcia wychodziłby bardzo "nieregularne", jeśli chodzi o liczność. Znalazłem je na forum. Zerknąłem tylko, że zamieszczone rozwiązania dotyczą innej treści i nie wczytywałem się dalej. No a ostatnio przyszło mi do głowy dobre rozwiązanie, więc zamieściłem. Może ktoś kiedyś znów będzie go szukał i skorzysta.