witam
Mam problem z dwoma zadaniami i prosilbym o pomoc w rozwiazaniu ich
1. Na ile sposobów można wybrać dziesieć pilek z nieograniczonej liczby czerwonych , niebieskich i zielonych, jesli chcemy otrzymac co najwyzej 5 czerwonych.
Tutaj kompletnie nie wiem jak sie za to zabrac? Z czego skorzystac? Jak uwzglednic co najwyzej i co najmnie?
zad 2. ^{}
wyznacz postac zwarta ciagu wykorzystujac aparat funkcji tworzacych
\(\displaystyle{ a_{0}=3 a_{n-1}+2^{n-2} -1, a0=a1=0}\)
dochodze do czegos takiego i czy to jest dobrze?
\(\displaystyle{ A(z)=z*A(z)+2^{z ^{2}*A(z) } -1}\)
jesli tak to jak to dalej przeksztalcic? a jesli nie to prosilbym o poprawienie
dziekuje za pomoc
pozdrawiam
funkcje tworzace z rekurencja+ kombinatoryka
-
adek05
- Użytkownik
- Posty: 450
- Rejestracja: 3 kwie 2007, o 18:38
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska
- Podziękował: 12 razy
- Pomógł: 68 razy
funkcje tworzace z rekurencja+ kombinatoryka
1.
Można skorzystać z funkcji tworzących. Niech \(\displaystyle{ C, Z, N}\) będą funkcjami tworzącymi dla wyboru \(\displaystyle{ n}\) piłek w zadanym kolorze
\(\displaystyle{ C = 1 + c + c^2 + ... + c^{10} = \frac{1 - c^{11}}{1- c}}\)
\(\displaystyle{ Z = 1 + z + z^2 + ... + z^{10} = \frac{1 - z^{11}}{1- z}}\)
Tak samo \(\displaystyle{ N}\).
Dlaczego? Bo na ile sposobów można wybrać ze zbioru nierozróżnialnych elementów \(\displaystyle{ k}\) elementów? No na \(\displaystyle{ 1}\), bo nie jesteśmy w stanie rozróżnić wyborów - współczynnik przy \(\displaystyle{ [literka]^k}\) jest więc równy \(\displaystyle{ 1}\) i oznacza, że można wybrać \(\displaystyle{ k}\) elementów danego koloru na \(\displaystyle{ 1}\) sposób. Mnożymy i rozwijamy. Interesuje nas suma współczynników, gdzie wykładniki sumują się do \(\displaystyle{ 10}\) oraz gdzie wykładnik przy \(\displaystyle{ c}\) jest mniejszy bądź równy \(\displaystyle{ 5}\).
Bardziej elementarnie.
Szukamy wszystkich rozwiązań układu
\(\displaystyle{ \begin{cases} c + z + n = 10\\ c \leq 5 \end{cases}}\)
Czyli rozbija się nam to do 6 równań:
\(\displaystyle{ z + n = 10 - i \quad i \in \{0,\ldots,5\}, z,n \in N}\)
Mam nadzieję, że wiesz jak znaleźć liczbę rozwiązań każdego z takich równań (interpretacja kombinatoryczna).
Wystarczy zsumować liczbę rozwiązań
2.
Mocno pokręciłeś. Najpierw trzeba uporać się z warunkami brzegowymi.
Można skorzystać z funkcji tworzących. Niech \(\displaystyle{ C, Z, N}\) będą funkcjami tworzącymi dla wyboru \(\displaystyle{ n}\) piłek w zadanym kolorze
\(\displaystyle{ C = 1 + c + c^2 + ... + c^{10} = \frac{1 - c^{11}}{1- c}}\)
\(\displaystyle{ Z = 1 + z + z^2 + ... + z^{10} = \frac{1 - z^{11}}{1- z}}\)
Tak samo \(\displaystyle{ N}\).
Dlaczego? Bo na ile sposobów można wybrać ze zbioru nierozróżnialnych elementów \(\displaystyle{ k}\) elementów? No na \(\displaystyle{ 1}\), bo nie jesteśmy w stanie rozróżnić wyborów - współczynnik przy \(\displaystyle{ [literka]^k}\) jest więc równy \(\displaystyle{ 1}\) i oznacza, że można wybrać \(\displaystyle{ k}\) elementów danego koloru na \(\displaystyle{ 1}\) sposób. Mnożymy i rozwijamy. Interesuje nas suma współczynników, gdzie wykładniki sumują się do \(\displaystyle{ 10}\) oraz gdzie wykładnik przy \(\displaystyle{ c}\) jest mniejszy bądź równy \(\displaystyle{ 5}\).
Bardziej elementarnie.
Szukamy wszystkich rozwiązań układu
\(\displaystyle{ \begin{cases} c + z + n = 10\\ c \leq 5 \end{cases}}\)
Czyli rozbija się nam to do 6 równań:
\(\displaystyle{ z + n = 10 - i \quad i \in \{0,\ldots,5\}, z,n \in N}\)
Mam nadzieję, że wiesz jak znaleźć liczbę rozwiązań każdego z takich równań (interpretacja kombinatoryczna).
Wystarczy zsumować liczbę rozwiązań
2.
Mocno pokręciłeś. Najpierw trzeba uporać się z warunkami brzegowymi.
-
Xitami
funkcje tworzace z rekurencja+ kombinatoryka
\(\displaystyle{ a_n=5a_{n-1}-6a_{n-2}\\ a_0=a_1=0,\quad a_2=1\\\\
\frac{x^2}{6 x^2
- 5 x
+ 1}=x^2
+ 5 x^3
+ 19 x^4
+ 65 x^5
+ 211 x^6
+ 665 x^7
+ 2059 x^8
+ 6305 x^9+\dots}\)
\frac{x^2}{6 x^2
- 5 x
+ 1}=x^2
+ 5 x^3
+ 19 x^4
+ 65 x^5
+ 211 x^6
+ 665 x^7
+ 2059 x^8
+ 6305 x^9+\dots}\)
-
adek05
- Użytkownik
- Posty: 450
- Rejestracja: 3 kwie 2007, o 18:38
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska
- Podziękował: 12 razy
- Pomógł: 68 razy
funkcje tworzace z rekurencja+ kombinatoryka
Prawde mówiąc przychodzi mi do głowy tylko ręczne wypisanie możliwości. Ta wersja z układem jest bardzo przyjemna w liczeniuKasienkaG pisze:Czy to 1. zadanie można zrobić jeszcze w jakiś inny sposób, czy ten jest jedyny??
Można sobie to tylko inaczej opowiedzieć, np. bierzemy \(\displaystyle{ 5}\) piłek czerwonych i potem wszystkie możliwe kombinacje niebieskich i zielonych, nie patrzymy na kolejność itd. Ale to jest dość żmudne.