liczby fibonacciego
q: mam problem ze zrozumieniem podanej metody; za wszelka pomoc z gory dziekuje
α(k) − tak oznacze k−ty element ciagu, ε − symbol przynaleznosci
"Załóżmy, że X = {1, 2, ..., n} i niech Y ⊆ X. Przyporządkujmy zbiorowi Y ciąg α(1), α(2),
...., α(n) taki, że:
1) α(k) = 1 jeśli k ε Y, w przeciwnym wypadku 0
2) suma elementow ciagu wynosi p
3) jeżeli a(i) = a(j) = 1, to |i − j| >= 2 "
Czyli tłumaczę to sobie tak, że mam poszukać wszystkie podzbiory Y zbioru X, o liczności p, dla
których żadne 2 liczby nie są "następujące po sobie". Zbiory takie jak {1, 3, 4, 8, 9}, czy
{1, 2} nie spoelniają więc założeń. Przykładowy zbiór Y = {1, 3, 6}, dla p = 3 i n = 7,
zapisalbym jako: (1010010).
"Aby wyznaczyć liczbę wszystkich takich ciągów, rozważmy ciąg b(1), b(2), ...., b(n − p), taki
że b(k) = 0 dla kazdego k = 1, 2, ...., n − p. Następnie uzupełniamy ten ciąg o p jedynek w
taki sposób, aby żadne dwie jedynki nie były sąsiednie. Ponieważ uzupełniamy p jedynkami na n
| | | |
− p + 1 mozliwych miejscach, zatem mozemy to zrobic na | sposobów" |
| | |
Nie rozumiem ostatniego zdania. Jak wyglądałoby to dla ciągu, który podałem wcześniej
(1010010)?
PW: Oni robią to odwrotnie niż Ty − najpierw biorą same zera, np. 4 zera:
0, 0, 0, 0.
W przykładzie wziąłeś n=7, czyli trzeba utworzyć ciąg 7−elementowy. Oznacza to, że mamy do
dyspozycji p=7−4=3 jedynki. Można je wstawiać (po jednej) na każde z możliwych 5 miejsc −
przed pierwszym zerem, po pierwszym, ..., po czwartym zerze. Miejsc do wstawiania jedynek jest
więc o jedno więcej niż zer, czyli 5. Wstawiać 3 jedynki na 5 miejscach (po jednej na każdym)
można na
sposobów.
