Witam,
mam problem z zadaniem:
Niech \(\displaystyle{ a_n}\) będzie liczbą podzbiorów zbioru \(\displaystyle{ \left[ n\right]}\) bez par typu \(\displaystyle{ k, k+2}\). Znaleźć zależność rekurencyjną na \(\displaystyle{ a_n}\).
Nie za bardzo wiem jak się zabrać i czy dobrze rozumuję, że jeśli np. \(\displaystyle{ n=3}\). To możliwe podzbiory poza pustym to są:
\(\displaystyle{ 1}\)
\(\displaystyle{ 2}\)
\(\displaystyle{ 3}\)
\(\displaystyle{ 12}\)
\(\displaystyle{ 23}\)
\(\displaystyle{ 123}\)
i wtedy \(\displaystyle{ a_3 = 6}\).
Proszę o wskazówki i pomoc przy rozwiązaniu
zależnośc rekurencyjna
-
- Użytkownik
- Posty: 327
- Rejestracja: 6 lis 2009, o 18:39
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 23 razy
- Pomógł: 28 razy
-
- Użytkownik
- Posty: 4211
- Rejestracja: 25 maja 2012, o 21:33
- Płeć: Mężczyzna
- Lokalizacja: Kraków PL
- Podziękował: 2 razy
- Pomógł: 758 razy
zależnośc rekurencyjna
\(\displaystyle{ n=3}\) jest za małe, bo jest pierwsze, w której występuje para \(\displaystyle{ \{k;k+2\}}\).
Rozpisz wszystkie podzbiory dla \(\displaystyle{ n=4}\), może coś Cię oświeci.
Rozpisz wszystkie podzbiory dla \(\displaystyle{ n=4}\), może coś Cię oświeci.
- Medea 2
- Użytkownik
- Posty: 2491
- Rejestracja: 30 lis 2014, o 11:03
- Płeć: Kobieta
- Podziękował: 23 razy
- Pomógł: 479 razy
zależnośc rekurencyjna
A jaką przyjemną funkcję tworzącą wytropiłam Możesz użyć jej do sprawdzenia, czy dobrze liczysz \(\displaystyle{ a_n}\).
\(\displaystyle{ \frac{1}{(1 + z^2) (1 - z - z^2)}.}\)
\(\displaystyle{ \frac{1}{(1 + z^2) (1 - z - z^2)}.}\)