Liczba ciągów spełniających warunki.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
water123
Użytkownik
Użytkownik
Posty: 21
Rejestracja: 12 lis 2008, o 10:06
Płeć: Kobieta
Lokalizacja: bydgoszcz

Liczba ciągów spełniających warunki.

Post autor: water123 »

Ile ciagow \(\displaystyle{ (x_{1},...,x_{2n+1})}\) spełnia wszystkie trzy poniższe własności?:
a) \(\displaystyle{ x_{1}=x_{2n+1}=0}\)
b) \(\displaystyle{ \left| x_{i} - x_{i-1} \right| =1}\) dla \(\displaystyle{ i=2,...,2n+1}\)
c) \(\displaystyle{ x_{i} qslant 0}\) dla \(\displaystyle{ i=1,2,...,2n+1}\)
Ostatnio zmieniony 6 gru 2008, o 15:02 przez water123, łącznie zmieniany 1 raz.
patry93
Użytkownik
Użytkownik
Posty: 1251
Rejestracja: 30 sty 2007, o 20:22
Płeć: Mężczyzna
Lokalizacja: Koziegłówki/Wrocław
Podziękował: 352 razy
Pomógł: 33 razy

Liczba ciągów spełniających warunki.

Post autor: patry93 »

Podbijam, ponieważ też mam problem z tym zadaniem.
Na piechotę można policzyć, że dla n=1,2,3,4 jest odpowiednio 1,2,5,9 takich ciągów, lecz żadnej istotniej zależności nie zauważyłem.
Znalazłem samą odpowiedź, która brzmi:
Ukryta treść:    
Może kogoś to nakieruje na dobry trop...
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Liczba ciągów spełniających warunki.

Post autor: »

Pewnie się przyda:


Q.
patry93
Użytkownik
Użytkownik
Posty: 1251
Rejestracja: 30 sty 2007, o 20:22
Płeć: Mężczyzna
Lokalizacja: Koziegłówki/Wrocław
Podziękował: 352 razy
Pomógł: 33 razy

Liczba ciągów spełniających warunki.

Post autor: patry93 »

Hm, teraz sobie uświadomiłem, że albo źle policzyłem na piechtę dla n=4, albo odpowiedź jest błędna...
Te 9 ciągów, które znalazłem, to:
\(\displaystyle{ \hbox{(010101010) , (012101010) , (010121010) , (010101210) , (012121010) , (010121210) , (012121210) , (012323210)}}\) \(\displaystyle{ \hbox{ , (012343210) }}\)
Więc brakuje mi pięciu, o ile odpowiedź jest prawidłowa, ale nie widzę innych
Pomijam już to, że nie widzę w tym zadaniu związku z Catalanem
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Liczba ciągów spełniających warunki.

Post autor: »

patry93 pisze:\(\displaystyle{ (010101010) , (012101010) , (010121010) , (010101210) \\
(012121010) , (010121210) , (012121210) , (012323210)} , (012343210) }}\)
Brakuje chociażby \(\displaystyle{ (012321010)}\)
Pomijam już to, że nie widzę w tym zadaniu związku z Catalanem :)
Mogę więc jedynie domniemywać, że nie przeczytałeś linkowanego artykułu z Wikipedii. Proponuję więc, byś jednak to zrobił, ze szczególnym uwzględnieniem fragmentu o liczbie dróg.

Q.
ODPOWIEDZ