Kombinatoryka - liczby fibonacciego

[BarbarBarabasz]

Cześć,

Z matematyki dyskretnej mam takie zadanie.
"Każdego dnia Janek kupuje albo lody za 1 zł. albo baton za 2 zł. Lody są w czterech smakach, a batony tylko jednego rodzaju. Na ile sposobów Janek może wydać n złotych?"

Treść zadania ma chyba za mało informacji. Ktoś może wie w jaki sposób to rozwiązać? Dodam że w zadaniu jest wskazówka, która mówi o rozumowaniu poprzez liczby Fbinacciego.

[ppr]

Przez chwilę pominę smaki lodów. Janek może wydać złotówkę na jeden sposób (oczywiste), dwa złote na jeden sposób (zakładam, że nie może w ciągu dnia kupić dwóch lodów - tylko baton wchodzi w grę). Pytanie brzmi na ile sposobów może wydać trzy złote? Spróbuj sformułować rekurencyjną zależność - wskazówka: może kupić batona i zostanie mu jeszcze jedna złotówka, może kupić lody i zostaną mu jeszcze dwa złote.

[BarbarBarabasz]

Okej, trochę mi to dało. W zadaniu jest napisane ze kupuje za kasę lody albo batona. Nie wiem czy zawsze kupuje jednego batona, ale dla zadania przyjąłem ze kupuje batona dopóki starcza mu pieniędzy. Wymyśliłem sobie prosty algorytm.
\(\displaystyle{ n}\) - ilosc pieniędzy
\(\displaystyle{ L_n = n}\) to liczba kupionych lodów, zawsze równa się ilości pieniędzy jakie mamy
\(\displaystyle{ B_n =}\) liczba kupionych batonów dla \(\displaystyle{ n}\) parzystego to \(\displaystyle{ \frac{n}{2}}\), dla \(\displaystyle{ n}\) nieparzystego \(\displaystyle{ \frac{n-1}{2}}\)
Czyli:
Dla \(\displaystyle{ n = 3\,\text{zł}}\) mamy:

\(\displaystyle{ L_n(3) + B_n(1) = 4}\) możliwości

Dla \(\displaystyle{ n = 10\,\text{zł}}\) mamy:

\(\displaystyle{ L_n(10) + B_n(5) = 15}\) możliwości

Dla \(\displaystyle{ n = 7\,\text{zł}}\) mamy:

\(\displaystyle{ L_n(7) + B_n(3) = 10}\) możliwosci

Wzór działa, ale nie wiem jak to napisać czysto matematycznie, oraz nie jestem pewien czy moje wnioskowanie jest prawidłowe.

[ppr]

Niestety, wydaje mi się, że zadanie trzeba rozumieć inaczej. Ogółem popraw oznaczenia, bo w definicji \(\displaystyle{ B_n}\) czy \(\displaystyle{ L_n}\) nie wspominasz o argumencie w nawiasach, ciężko rozszyfrować o co chodzi.

To zadanie i wskazówka nasuwa wniosek, że chodzi tutaj o ułożenie równania rekurencyjnego - to wygląda na klasyczny rodzaj takich zadań. Jak ja bym o tym myślał: Janek ma do dyspozycji pewną kwotę, mamy ceny produktów i zastanawiamy się na ile sposobów można tę kwotę wydać. Załóżmy, że znamy ilość sposobów dla 1, 2, ..., n-2, n-1 złotych i zastanawiamy się, na ile sposobów można wydać n złotych. Ilość możliwości na wydanie n złotych będę oznaczać przez \(\displaystyle{ a_n}\).
No więc mamy n złotych i znamy ilość sposobów dla wszystkich mniejszych kwot. No więc jeżeli mamy n złotych to możemy kupić batona i pozostaje nam n-2 złote, które możemy wydać na \(\displaystyle{ a_{n-2}}\) sposobów, możemy kupić loda na cztery sposoby (bo cztery smaki) i zostanie nam n-1 złotych, sposobów na wydanie jest \(\displaystyle{ a_{n-1}}\).
Decyzja: kupienie batona albo kupienie loda to zupełnie oddzielne przypadki (alternatywne), więc z kombinatorycznego punktu widzenia obowiązuje tutaj reguła dodawania. Stąd \(\displaystyle{ a_n = 4 a_{n-1} + a_{n-2}}\).

Podejrzewam, że o to właśnie chodzi. Daj znać, czy to kupujesz, ewentualnie popraw swoje oznaczenia i notację i spróbuję podjąć dyskusję.

[kerajs]

Z zupełnie innej beczki:

Ukryta treść:    

i-ilość kupionych batonów
s- ilość sposobów wydania n złotych na lody i batony
\(\displaystyle{ s= \sum_{i=0}^{\lfloor \frac{n}{2} \rfloor} {n-i \choose i} \cdot 4^{n-2i}}\)

[BarbarBarabasz]

Argument w nawiasach przy \(\displaystyle{ L_n}\) i \(\displaystyle{ B_n}\) oznacza ilość kupionych towarów dla określonej kwoty.
Wcześniej napisałem w jaki sposób te argumenty są liczone.
Zgodzę się jednak z Tobą, to co napisałeś ma ręce i nogi.
Mógłbyś jeszcze podstawić pod wzór jakąś konkretną kwotę złotych?

[ppr]

Złotówkę możemy wydać na cztery sposoby (cztery smaki), dwa złote na dziewięć sposobów (dwa lody * cztery smaki albo jeden baton).

Cztery złote możemy wydać na:
\(\displaystyle{ a_4 = 4 a_{3} + a_{2} \\
a_3 = 4 a_2 + a_1 = 4\cdot9+4 = 40 \\
a_4 = 4 \cdot 40 + 9 = 169 }\)

[kerajs]

Poprawa rachunków:

Ukryta treść:    

Złotówkę możemy wydać na cztery sposoby (cztery smaki), dwa złote na dziewięć sposobów (dwa lody * cztery smaki albo jeden baton).

Raczej:
\(\displaystyle{ a_2=4 \cdot 4+1=17}\)

Cztery złote możemy wydać na:
\(\displaystyle{ a_4 = 4 a_{3} + a_{2} \\
a_3 = 4 a_2 + a_1 = 4\cdot9+4 = 40 \\
a_4 = 4 \cdot 40 + 9 = 169 }\)

A tu:
\(\displaystyle{ a_3=4 \cdot 4 \cdot 4+4 \cdot 1+1 \cdot 4=72=4 \cdot 17+4=4a_2+a_1\\

a_4=4 \cdot 4 \cdot 4 \cdot 4+4 \cdot 4 \cdot 1+4 \cdot 1 \cdot 4+1 \cdot 4 \cdot 4+1 \cdot 1=305=4 \cdot 72+17=4a_3+a_2}\)

Dodano po 32 minutach 38 sekundach:
Ponadto:

Ukryta treść:    

\(\displaystyle{ s(1)= \sum_{i=0}^{0} {1-i \choose i} \cdot 4^{1-2i}= {1 \choose 0} \cdot 4^1=4 \\
s(2)= \sum_{i=0}^{1} {2-i \choose i} \cdot 4^{2-2i} ={2 \choose 0} \cdot 4^2+{1 \choose 1} \cdot 4^0=17 \\
s(3)= \sum_{i=0}^{1} {3-i \choose i} \cdot 4^{3-2i}={3 \choose 0} \cdot 4^3+{2 \choose 1} \cdot 4^1=72 \\
s(4)= \sum_{i=0}^{2} {4-i \choose i} \cdot 4^{4-2i}={4 \choose 0} \cdot 4^4+{3 \choose 1} \cdot 4^2+{2 \choose 2} \cdot 4^0=305 }\)

[Gosda]

Czemu tak dookoła? To typowe zadanie na rekurencję liniową. Mamy

\(\displaystyle{ a_n = 4a_{n-1} + a_{n-2}}\)

z warunkiem początkowym \(\displaystyle{ a_0 = 0, a_1 = 1}\). Maszyneria funkcji tworzących daje

\(\displaystyle{ A(x) = \frac{-x}{x^2+4x-1}}\),

co pozwala na dość szybkie wyznaczenie postaci zwartej dla \(\displaystyle{ a_n}\) (dostaniemy coś na kształt wzoru Bineta).

[janusz47]

\(\displaystyle{ a_{n} = 4a_{n-1} + a_{n-2}.}\)

Jest to równanie różnicowe - jednorodne.

Równanie charakterystyczne

\(\displaystyle{ x^2 - 4x -1 =0, }\)

jego pierwiastki

\(\displaystyle{ x_{1} = 2-\sqrt{5}, \ \ x_{2} = 2+ \sqrt{5}. }\)

Rozwiązanie ogólne

\(\displaystyle{ a_{n} = K_{1}( 2-\sqrt{5})^{n} + K_{2}(2 + \sqrt{5})^{n}.}\)

Uwzględniając warunki początkowe

\(\displaystyle{ a_{0} = 0, \ \ a_{1} = 1, }\)

otrzymujemy wartości stałych

\(\displaystyle{ K_{1} = -\frac{1}{2\sqrt{5}} = -\frac{\sqrt{5}}{10} }\)


\(\displaystyle{ K_{2} = \frac{1}{2\sqrt{5}} = \frac{\sqrt{5}}{10} }\)

Postać ogólna ciągu

\(\displaystyle{ a_{n} = -\frac{\sqrt{5}}{10} (2-\sqrt{5})^{n} + \frac{\sqrt{5}}{10} (2+\sqrt{5})^{n}. }\)

[BarbarBarabasz]

Czyli który wzór jest prawidłowy, bo przyznam że pogubiłem się w tych wszystkich odpowiedziach.

[kerajs]

Aby się o tym przekonać wykonaj test. Policz na paluszkach na ile sposobów można wydać 2 zety, a następnie sprawdź który wzór generuje taką samą odpowiedź dla \(\displaystyle{ n=2}\). Może każdy jest prawidłowy?


PS
Wzór ogólny janusza47 można bez problemu skorygować, wyliczając nowe stałe dla poprawnych warunków początkowych.

PPS
Czy może ktoś wie jak w tym zadaniu zastosować liczby Fibonacciego ?

[BarbarBarabasz]

Dla 2 zł mamy 17 kombinacja
Możemy kupić 1 baton i dwa lody ( Przyjąłem że każda kombinacja kupna lodów (4 smaki), to oddzielna możliwość na wydanie pieniędzy, stąd 4*4)

3 zł = 65 możliwości
4 zł = 258 kombinacja
5 zł = 1026 kombinacji
6zł = 4099 kombinacji
7 zł = 16 387 kombinacji
8 zł = 65 540 kombinacji

Co ciekawe, ciąg ten jest bardzo podobny do ciągu Fibonaciego, podzielenie wyniku następnego i poprzedniego(\(\displaystyle{ a_n / a_{n-1}}\)), w przybliżeniu zawsze da nam liczbe 3.99. Następnie, dowolny wynik kombinacji pomnożony przez tą liczbę, będzie odpowiadał wynikowi kombinacji o jeden większy

[kerajs]

Dla 2 zł mamy 17 kombinacja

Tak, 17 możliwości.

3 zł = 65 możliwości
4 zł = 258 kombinacja
5 zł = 1026 kombinacji
6zł = 4099 kombinacji
7 zł = 16 387 kombinacji
8 zł = 65 540 kombinacji

NIe, nie, nie,....., nie.

Co ciekawe, ciąg ten jest bardzo podobny do ciągu Fibonaciego

Sorki, ja tego podobieństwa nie widzę.

Nadal nie wiem jaki związek z zadaniem ma wskazówka o liczbach Fibonacciego.

Dodano po 28 minutach 20 sekundach:
Może taki
\(\displaystyle{ a_n= \frac{1}{2}F_{3n+3} }\)

[BarbarBarabasz]

Dla 2 zł mamy 17 kombinacja

Tak, 17 możliwości.

3 zł = 65 możliwości
4 zł = 258 kombinacja
5 zł = 1026 kombinacji
6zł = 4099 kombinacji
7 zł = 16 387 kombinacji
8 zł = 65 540 kombinacji

NIe, nie, nie,....., nie.

A dlaczego nie?
Dla 3 zł, możemy kupić 3 lody o czterech różnych smakach, która mogą się powtarzać, co daje \(\displaystyle{ 4\cdot 4\cdot 4}\), chyba że źle to interpretuje,