Zależności rekurencyjne

[ann1]

Bardzo proszę o pomoc w ułożeniu zależności rekurencyjnych do tych zadań:

1. Pewne dziecko bawiło się n patyczkami o różnej długości. Najpierw każdy z nich przełamało dokładnie na pół. Następnie wbiło je pionowo w ziemię w jednej linii. Stoisz na jednym z końców linii i zauważasz, że dziecko przestrzegało dwóch zasad: między dwoma patyczkami tej samej długości nigdy nie ma patyczków niższych oraz dokładnie k-razy zdarzyło się, że za patyczkiem stał patyczek wyższy. Na ile sposobów dziecko mogło ułożyć patyczki. Ułóż zależność rekurencyjną.
2. Na płaszczyźnie znajduje się n okręgów. Jaka jest max liczba obszarów na które dzielą one płaszczyznę? Ułóż zależność rekurencyjną.
3. Pragniesz stworzyć grę komputerową o n poziomach o różnej skali trudności (1...n). Postanawiasz zastosować zasadę: dokładnie między k poziomami skala trudności będzie rosła. Na ile sposobów można przypisać skalę trudności do poziomów? Znajdź zależność rekurencyjną.

[Premislav]

2. Ten problem już się pojawił, jak się wczytasz, to rozwiązanie znajdziesz w tym oto wątku: 414410.htm
(posty usera Slup, reszta to w zasadzie machanie rękami).