szukanie zaawansowane
 [ Posty: 13 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 2 cze 2016, o 19:50 
Użytkownik

Posty: 32
Lokalizacja: W-wa
Zliczyć, ile jest ciągów długości długości 2n o wyrazach ze zbioru 2n, takich, że żadne dwa sąsiednie wyrazy nie sumują się do 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ć A_{j}.
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2016, o 20:26 
Użytkownik

Posty: 322
Lokalizacja: Toruń
Czy mają to być permutacje? Bo jeśli nie, to możemy to zrobić tak:
pierwszy wyraz a_1 jest dowolny, wybieramy do na 2n sposobów.
Drugi wyraz nie może być równy 2n-a_1, więc wybieramy go na 2n-1 sposobów.
Trzeci również na 2n-1 sposobów, itd.
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2016, o 22:02 
Użytkownik
Avatar użytkownika

Posty: 3397
Lokalizacja: blisko
Ja obstaję za zasadą włączania i wyłączania:

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

n-1 - tyle jest par takich, że suma daje 2n

2^i to ilość permutacji tych par między sobą

(2n-i)! - ilość permutacji i par sumujących się do 2n oraz resztę liczb pojedynczych.
Góra
Mężczyzna Offline
PostNapisane: 16 sie 2016, o 12:44 
Użytkownik

Posty: 1438
Lokalizacja: Warszawa
Czy mógłbyś wyjaśnić, skąd się to wzięło?
Góra
Mężczyzna Offline
PostNapisane: 17 sie 2016, o 21:19 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
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.

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

M Maciejewski, przy założeniu, że wyrazy są ze zbioru \left\{ 1,2,...,2n\right\} (a chyba tak założyłeś), Twoje rozwiązanie jest błędne, bo jeżeli wyrazem jest 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ć (-1) ^{i + 1} zamiast (-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 2n. Za zbiór A_{j} przyjęty jest zbiór permutacji posiadających parę sąsiednich wyrazów równych np. j oraz 2n-j. Korzystamy z faktu, że moc części wspólnej dowolnych i spośród zbiorów A_{j} (tzn liczba permutacji mających i określonych par sąsiednich wyrazów o sumie 2n) jest taka sama (niezależnie od tego jakie te pary są) i wynosi 2^i(2n-i)! (jest tak, bo w permutacji każda para wyrazów o sumie 2n musi być rozłączna i występuje tylko raz) - 2^{i} uwzględnia że, każda taka para elementów może być ustawiona na dwa sposoby, a (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 2n jest \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.
Góra
Mężczyzna Offline
PostNapisane: 18 sie 2016, o 19:09 
Użytkownik

Posty: 1438
Lokalizacja: Warszawa
Mruczek napisał(a):
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ć:

michals95 napisał(a):
Zliczyć, ile jest ciągów długości długości 2n o wyrazach ze zbioru [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.
Góra
Mężczyzna Offline
PostNapisane: 18 sie 2016, o 19:48 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
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 2n, no to można oddzielnie policzyć ciągi kończące się tym wyrazem. Niech np. a_{n} to ciągi kończące się 2n, a b_{n} to ciągi kończące się wyrazem innym niż 2n. Dalszą część napiszę, jak będę wiedział o jaki zbiór chodzi.
Góra
Mężczyzna Offline
PostNapisane: 18 sie 2016, o 19:55 
Użytkownik

Posty: 718
[n]=\{ k\in \NN_{+} \,|\, k\leq n\}
Góra
Mężczyzna Offline
PostNapisane: 18 sie 2016, o 20:06 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
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):

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

Wynik to a_{2n}+ b_{2n}.
Góra
Mężczyzna Offline
PostNapisane: 18 sie 2016, o 20:12 
Użytkownik

Posty: 1438
Lokalizacja: Warszawa
Nie ma co przepraszać, a zmienia tyle, że dość popularnym oznaczeniem w kręgach matematykodyskretnych jest [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 2n i zastanawiamy się, jak można go rozbudować do dobrego ciągu długości 2n+2, to problem polega na tym, że przy ciągu długości 2n+2 dysponujemy innym zasobem wyrazów: \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 2n i zastanawiamy się, jak można go rozbudować do dobrego ciągu długości 2n+2, to problem polega na tym, że przy ciągu długości 2n+2 dysponujemy innym zasobem wyrazów: \left\{ 1,2,\ldots,2n+2\right\}. Tak więc nie ma jak budować takich równań rekurencyjnych jak wyżej.
Góra
Mężczyzna Offline
PostNapisane: 5 wrz 2016, o 15:31 
Użytkownik

Posty: 1438
Lokalizacja: Warszawa
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 A_i będzie zbiorem tych ciągów długości 2n o wyrazach z [2n], w których element i występuje obok 2n-i. Szukamy |A_1\cup A_2\cup\ldots\cup A_n|. Mamy |A_i|=(2n-1)\cdot2\cdot(2n)^{2n-2} - traktujemy parę (i,2n-i) jako jeden element, dla którego wybieramy jedno z 2n-1 miejsc, na 2 sposoby ustalamy kolejność elementów w parze; pozostałe 2n-2 miejsca zapełniamy dowolnie.

|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ź:

\sum_{k=0}^n\frac{(-2)^k\cdot(2n-k)!\cdot(2n)^{2n-2k}}{(2n-2k)!}
Góra
Mężczyzna Offline
PostNapisane: 5 wrz 2016, o 17:21 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Tu jest błąd. Jeżeli mamy złą parę (n, n) to nie permutujemy jej przez 2.
Trzeba oddzielnie zliczyć przecięcia zbiorów zawierających (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.
Góra
Mężczyzna Offline
PostNapisane: 8 wrz 2016, o 13:40 
Użytkownik

Posty: 1438
Lokalizacja: Warszawa
Mruczek napisał(a):
Tu jest błąd. Jeżeli mamy złą parę (n, n) to nie permutujemy jej przez 2.
Trzeba oddzielnie zliczyć przecięcia zbiorów zawierających (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:

(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:

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

Cytuj:
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 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.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 13 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 zliczanie zbiorow i funkcji,dwu i multimiany - zadania  Lios  6
 Ile jest ciągów...  ŚwIeRsZcZ  1
 Zliczanie funkcji - zadanie 2  Auster  11
 Ilość ciągów binarnych  Valiors  3
 Zliczanie rozmieszczenia kul w komórkach  szymod  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl