Ile ciągów spełnia zadane warunki ?

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Imperator
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 6 lis 2011, o 00:51
Płeć: Mężczyzna
Lokalizacja: Swarzędz

Ile ciągów spełnia zadane warunki ?

Post autor: Imperator »

Witam,
Natrafiłem na pewien problem rozwiązując pewne zadanie.
Chodzi o obliczenie ilości wszystkich n-elementowych ciągów spełniających podane warunki:

Dany jest ciąg n-elementowy \(\displaystyle{ a_{n}}\) liczb naturalnych ( wartości mogą się powtarzać ) o sumie \(\displaystyle{ S_{a}}\),
oraz pewne liczby naturalne m oraz z.

Warunki:
1) \(\displaystyle{ S_{a} - m \le S_{b} \le S_{a}}\)
2) \(\displaystyle{ \bigwedge\limits_{i \in <1, n>} b_{i} \le a_{i}}\)
3) \(\displaystyle{ \max |b_{i} - b_{i+1}| = z}\)

\(\displaystyle{ b_{n}}\) jest ciągiem szukanym. \(\displaystyle{ S_{b}}\) to suma elementów \(\displaystyle{ b_{n}}\).

Zadanie:
Oblicz na ile sposobów można utworzyć ciągu \(\displaystyle{ b_{n}}\).

Utknąłem na tym zadaniu. Potrafię obliczyć ile ciągów spełnia każdy warunek z osobna,
jednak nie wiem jak znaleźć część wspólną tych poszczególnych zbiorów.
Czy jest ktoś w stanie to policzyć, lub wytłumaczyć mi jak powinienem się do tego zabrać ?

Z góry dziękuję,
Pozdrawiam.
Ostatnio zmieniony 9 lis 2011, o 00:34 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości: \max.
abc666

Ile ciągów spełnia zadane warunki ?

Post autor: abc666 »

To jest oryginalne zadanie czy część jakiegoś innego lub część jakiegoś problemu programistycznego?
Imperator
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 6 lis 2011, o 00:51
Płeć: Mężczyzna
Lokalizacja: Swarzędz

Ile ciągów spełnia zadane warunki ?

Post autor: Imperator »

To co prawda jest część mojego rozwiązania dla pewnego problemu programistycznego,
aczkolwiek można to traktować jako oddzielne zadanie. Znaczy się, są wszystkie potrzebne dane
tutaj podane. Chodzi o wzór na ilość tych ciągów w zależności od ciągu a oraz zmiennych z i m.
ODPOWIEDZ