Miniatura 1
Zliczanie rekurencyjne
Andrzej Sendlewski
1. Wstęp
Z analizy testów konkursu  Kangur Matematyczny z ostatnich kil-
kunastu lat wynika, że jego uczestnicy stykają się z problemami polega-
jącymi na konieczności policzenia liczby obiektów w pewnym układzie,
którego rozmiar wyraża się parametrami liczbowymi (zobacz [4]). Wy-
znaczenie takiej liczby jest proste, gdy znamy wzór opisujący tę liczbę
jako funkcję od tych parametrów. Wtedy wystarczy podstawić do wzo-
ru aktualne wartości parametrów i wykonać odpowiednie operacje. Ale
co mamy zrobić, gdy takiego wzoru nie umiemy napisać albo, co gorsza,
nie wiemy, że w ogóle można go napisać, a układ jest na tyle wielki, że
 ręczne obliczenia sprawiają nam duże kłopoty?
Otóż, dla niektórych układów tego typu, można z powodzeniem za-
stosować postępowanie zwane rekurencją (w teorii numeracji zwane re-
kursją). Polega ono na rozważaniu układów o mniejszych rozmiarach
niż dany i ustaleniu zależności pomiędzy liczbami interesujących nas
obiektów w układzie wyjściowym przez liczby tychże obiektów w ukła-
dach o mniejszych rozmiarach. Pozwala nam to redukować problem do
układów o coraz mniejszych rozmiarach, aż otrzymamy pewne ukła-
dy początkowe, w których liczby interesujących nas obiektów są łatwe
do wyznaczenia, a tym samym  są nam znane. Jeśli opis zależności
jest kompletny, to w odwrotnym postępowaniu pozwoli nam to obli-
czyć liczbę obiektów w układzie wyjściowym. Metoda ta ma niestety
swoją wadę. Jest nią duża liczba operacji prowadzących do uzyskania
wyniku, gdyż musimy wyznaczyć odpowiednie liczby dla wszystkich
1
2 1. ZLICZANIE REKURENCYJNE
układów o mniejszych rozmiarach. Liczba ta niestety bardzo szybko
wzrasta wraz ze wzrostem rozmiaru układu. Dlatego metoda ta nabrała
znaczenia praktycznego dopiero w dobie upowszechnienia komputerów
(pracochłonność została zrzucona na komputer) i jest obecnie jedną z
ważnych metod algorytmicznych (zobacz [3]).
W niniejszej miniaturze chcemy wprowadzić Czytelnika w opisaną
metodę rekurencji na konkretnych przykładach wzorowanych głównie
na zadaniach ze wspomnianego na poczÄ…tku konkursu  Kangur Mate-
matyczny .
2. Liczby figuralne
Na początek przedstawimy kilka prostych zadań dotyczących ukła-
dów figur geometrycznych, które wprowadzą nas w istotę rekurencji.
Zadanie 1 (liczby kwadratowe). Rysujemy kolejne kwadraty o bo-
kach długości całkowitej i dzielimy je na kwadraty jednostkowe (ry-
sunek 1). Z ilu kwadratów jednostkowych składa się kwadrat o boku
długości n?
1 2 3 4
Rysunek 1. Kolejne kwadraty
Rozwiązanie. Oczywiście każdy z Czytelników odpowie natych-
miast, że z n2 i . . . to jest doskonała odpowiedz
! Ale nie ma tu my-
ślenia rekurencyjnego. Spróbujmy odkryć jaka jest zależność pomiędzy
sÄ…siednimi kwadratami.
Z obserwacji kwadratów na rysunku 2 wnioskujemy, że n ty kwadrat
powstaje z kwadratu (n-1)-szego przez dodanie 2(n - 1) + 1 = 2n - 1
kwadratów jednostkowych (zaznaczonych na rysunku 2 czerwonym ko-
lorem).
2. LICZBY FIGURALNE 3
1 2 3 4
Rysunek 2. Kolejne kwadraty
A więc, jeśli przez k(n) oznaczymy liczbę kwadratów jednostkowych,
tworzących n ty kwadrat, to prawdziwy jest wzór:


1, jeżeli n = 1;
k(n) =
k(n - 1) + 2n - 1, jeżeli n > 0.

Wzór ten pozwala nam obliczać wartości k(n) dla danego n, ale
pod jednym warunkiem: że policzymy wartości k(m) dla wszystkich
liczb m < n. A więc:
k(n) = (. . . (((1 + 3) + 5) + 7) + . . .) + 2n - 1,
co po uwzględnieniu naszej początkowej uwagi prowadzi do równości

1 + 3 + 5 + 7 + . . . + 2n - 1 = n2 .


Zadanie 2 (liczby trójkątne). Z monet o tych samych nominałach
układamy kolejne  trójkąty równoboczne , takie jak na rysunku 3. Jaka
jest wartość monet tworzących n ty trójkąt?
1 2 3 4
Rysunek 3. Kolejne  trójkąty równoboczne
4 1. ZLICZANIE REKURENCYJNE
Rozwiązanie. Oczywiście, aby obliczyć wartość monet tworzących
n ty trójkąt, wystarczy znać liczbę monet tworzących ten trójkąt. Niech
t(n) oznacza poszukiwaną liczbę monet tworzących n ty trójkąt.
1 2 3 4
Rysunek 4. Kolejne  trójkąty równoboczne
Patrząc na rysunek 4 stwierdzamy, że n ty trójkąt powstaje z trój-
kÄ…ta (n - 1)-szego przez dodanie n monet (monety te zaznaczono czer-
wonym kolorem). Stąd mamy następujące zależności:


1, jeżeli n = 1;
t(n) =
t(n - 1) + n, jeżeli n > 1.

Wzór ten pozwala nam obliczać wartości t(n), dla danego n, ale
wymaga to obliczenia wszystkich wartości t(m) dla m < n.
Aby napisać jawny wzór na obliczanie wartości t(n), tj. rozwiązać
równanie rekurencyjne z zadania, wystarczy zsumować kolejne liczby
naturalne od 1 do n.
1 2 3 4
Rysunek 5. Inna reprezentacja liczb kwadratowych
W tym celu można skorzystać z wzoru na n wyrazów ciągu aryt-
metycznego. My natomiast postąpimy inaczej. Spróbujemy zbadać za-
leżności pomiędzy liczbami kwadratowymi i trójkątnymi. Otóż, jeśli na
2. LICZBY FIGURALNE 5
rysunku 1 każdy mały kwadrat zastąpimy monetą, a potem te mone-
ty poprzesuwamy, to otrzymamy reprezentacjÄ™ liczb kwadratowych za
pomocą  rombów z rysunku 5. Romby te możemy podzielić na dwa
kolejne trójkąty równoboczne, jak na rysunku 6, albo na dwa identyczne
trójkąty równoboczne i  przekątną , jak na rysunku 7.
1 2 3 4
Rysunek 6
1 2 3 4
Rysunek 7
Z obserwacji figur na rysunku 6, otrzymujemy dla n > 1 równość:

k(n) = t(n) + t(n - 1) .

Natomiast z obserwacji figur na rysunku 7, dla n 1, mamy:

k(n + 1) = 2t(n) + n + 1 .

WyznaczajÄ…c t(n) z ostatniego wzoru otrzymujemy:
k(n + 1) - (n + 1) (n + 1)2 - (n + 1)
t(n) = = ,
2 2
czyli:

n(n + 1)
t(n) = .
2

6 1. ZLICZANIE REKURENCYJNE
Zadanie 3 (liczby tetraedralne). Z jednakowych sześciennych kloc-
ków budujemy kolejne piramidy trójkątne, jak na rysunku 8. Z ilu sze-
ściennych klocków zbudowana jest n ta piramida trójkątna?
1
2
3
4
Rysunek 8. Kolejne piramidy trójkątne
Rozwiązanie. Zależność rekurencyjną łatwo odczytujemy z rysun-
n(n + 1)
ku 9. Żółta ściana n tej piramidy zbudowana jest z t(n) =
2
klocków. A więc, jeśli oznaczymy przez pt(n) liczbę klocków, z których
1
2
3
4
Rysunek 9
zbudowana jest n ta piramida, to mamy:

Å„Å‚
1, jeżeli n = 1;
òÅ‚
pt(n) = n(n + 1)
ół
pt(n - 1) + , jeżeli n > 1.
2

Obliczając wartości pt(n), dla n = 1, 2, . . . , 12, otrzymujemy:
n 1 2 3 4 5 6 7 8 9 10 11 12
pt(n) 1 4 10 20 35 56 84 120 165 220 286 364

2. LICZBY FIGURALNE 7
Zadanie 4. Z jednakowych sześciennych klocków budujemy kolej-
ne piramidy ( kwadratowe ), jak na rysunku 10. Z ilu sześciennych
klocków zbudowana jest n ta piramida?
1
2
3
4
Rysunek 10. Kolejne piramidy
Rozwiązanie. Zależność rekurencyjna jest łatwa do ustalenia (patrz
rysunek 11). Jeśli oznaczymy przez p(n) liczbę klocków, z których zbu-
1
2
3
4
Rysunek 11
dowana jest n ta piramida, to mamy:


1, jeżeli n = 1;
p(n) =
p(n - 1) + n2, jeżeli n > 1.

Licząc wartości p(n), dla n = 1, 2, . . . 12, otrzymujemy:
n 1 2 3 4 5 6 7 8 9 10 11 12
p(n) 1 5 14 30 55 91 140 204 285 385 506 650

Postępując podobnie jak postąpiliśmy w przypadku rozwiązywania
równania rekurencyjnego dla liczb trójkątnych, z jedną drobną różnicą,
8 1. ZLICZANIE REKURENCYJNE
że miejsce liczb kwadratowych zastąpimy liczbami sześciennymi (kolej-
ne sześciany zbudowane z jednakowych klocków sześciennych), można
dość łatwo wyprowadzić wzór:

n(n + 1)(2n + 1)
p(n) = ,
6

czyli:

n(n + 1)(2n + 1)
12 + 22 + 32 + . . . + n2 = .
6

3. Liczby Fibonacci ego
Klasyczny ciąg Fibonacci ego zdefiniowany jest następująco:

Å„Å‚
ôÅ‚
0, jeżeli n = 0;
òÅ‚
fib(n) = 1, jeżeli n = 1;
ôÅ‚
ół
fib(n - 2) + fib(n - 1), jeżeli n > 1.

Rozwiązaniem tej rekurencji jest wzór Bineta:


1 (-1)n
"
fib(n) = Õn - ,
Õn
5

"
1 + 5
gdzie liczba Õ = jest zÅ‚otym stosunkiem (zobacz [1]).
2
Wiele zadań na zliczanie często prowadzi do ciągu Fibonacci ego
albo różnych jego uogólnień. W tym paragrafie zajmiemy się właśnie
takimi przykładami.
Zadanie 5. Na taras wieży widokowej prowadzą schody o n stop-
niach. Piotr wbiega na taras wykonujÄ…c losowo kroki co 1 albo co 2
stopnie. Na ile sposobów Piotr może przebiec schody?
Rozwiązanie. Piotr przebiegnie schody, gdy osiągnie stopień n.
Niech s(n) oznacza liczbę wszystkich możliwych sposobów osiągnięcia
n tego stopnia. Możliwe postępowanie Piotra ilustruje rysunek 12.
Aby Piotr mógł się znalez
ć na stopniu o numerze 1, to musi to zrobić
na jeden sposób, wykonując krok  długości 1 (zielona strzałka), więc
s(1) = 1. Na drugi stopień może on dotrzeć na 2 sposoby: wykonując
3. LICZBY FIBONACCI EGO 9
dwa kroki długości 1 albo wykonując jeden krok długości 2 (czerwona
strzałka); czyli s(2) = 2.
+2
+1
n
n - 1
n - 2
+2
+1 3
+1
2
1
0
Rysunek 12. Schody
Rozważmy teraz dowolny stopień o numerze n > 2. Jak osiągnąć
stopień n? Otóż stopień ten może być osiągnięty na dwa sposoby: albo
ze stopnia o numerze n-1 za pomocą kroku długości 1, albo ze stopnia o
numerze n-2 za pomocą kroku długości 2. Liczba sposobów osiągnięcia
n tego stopnia w pierwszym przypadku jest równa liczbie sposobów
osiągnięcia stopnia (n - 1), tj. s(n - 1). Zaś w drugim liczbie sposobów
osiągnięcia stopnia (n - 2), tj. s(n - 2). Stąd s(n) = s(n - 2) + s(n - 1).
Zatem pełen opis rekurencyjny jest następujący:

Å„Å‚
ôÅ‚
1, jeżeli n = 1;
òÅ‚
s(n) = 2, jeżeli n = 2;
ôÅ‚
ół
s(n - 2) + s(n - 1), jeżeli n > 2.


Zadanie 6. Mamy pokryć prostokątny pas podłogi o wymiarach
n × 2 prostokÄ…tnymi pÅ‚ytami o wymiarach 2 × 1. (PÅ‚yt nie możemy
łamać.) Na ile sposobów możemy to zrobić?
Rozwiązanie. Zauważmy, że zadanie jest wykonalne dla wszelkich
naturalnych n. Umówmy się, że płyty układane poziomo będziemy za-
znaczać kolorem zielonym, a płyty układane pionowo kolorem żółtym.
10 1. ZLICZANIE REKURENCYJNE
Najpierw ustalmy liczbę sposobów ułożenia płyt dla prostokątów o dłu-
gościach n równych: 1, 2 i 3. Wszystkie możliwe pokrycia takich pro-
stokątów przedstawiono na rysunku 13. Widzimy, że dla n = 1 mamy
1 2 2 3 3
Rysunek 13. Przypadki n = 1, 2, 3
jeden sposób, a dla n = 2 i n = 3 po dwa sposoby. Rozważmy teraz
prostokąt o długości n > 3. Mogą wystąpić dwie sytuacje: układanka
kończy się jednym prostokątem żółtym albo kończy się dwoma prosto-
kÄ…tami zielonymi (patrz rysunek 14). W pierwszym przypadku liczba
n - 1 1 n - 2 2
Rysunek 14
sposobów pokrycia prostokąta długości n jest równa liczbie sposobów
pokrycia prostokąta długości (n-1), zaś w drugim liczbie sposobów po-
krycia prostokąta długości (n - 2). Tym samym, oznaczając przez s(n)
(celowo przyjmujemy to samo oznaczenie co w poprzednim zadaniu!)
poszukiwaną liczbę sposobów pokrycia prostokąta długości n, mamy
następującą zależność rekurencyjną:

Å„Å‚
ôÅ‚
1, jeżeli n = 1;
òÅ‚
s(n) = 2, jeżeli n = 2;
ôÅ‚
ół
s(n - 2) + s(n - 1), jeżeli n > 2.


Zadanie 7. Ile jest sposobów zdobycia n punktów w meczu koszy-
kówki przez jedną z drużyn?
Rozwiązanie. Niech l(n) będzie liczbą sposobów uzyskania n punk-
tów. Punkty w meczu koszykówki zdobywane są rzutami do kosza za:
3. LICZBY FIBONACCI EGO 11
1 (tzw. rzuty osobiste), 2, albo 3 (z większej odległości) punkty. Wy-
nik n = 1 można osiągnąć tylko na jeden sposób; wynik n = 2 na
dwa sposoby: 1 + 1, 2; a wynik n = 3 na cztery sposoby sposoby:
1 + 1 + 1, 1 + 2, 2 + 1, 3. Załóżmy teraz, że n > 3. Wynik ten można
osiągnąć na trzy sposoby (patrz rysunek 15).
+3
+2
+1
n
n - 3 n - 2 n - 1
Rysunek 15. Sposoby osiągnięcia wyniku n
Z przeprowadzonego rozumowania otrzymujemy następującą zależ-
ność rekurencyjną:

Å„Å‚
ôÅ‚ 1, jeżeli n = 1;
ôÅ‚
ôÅ‚
òÅ‚
2, jeżeli n = 2;
l(n) =
ôÅ‚
4, jeżeli n = 3;
ôÅ‚
ôÅ‚
ół
l(n - 3) + l(n - 2) + l(n - 1), jeżeli n > 3.

Wartości l(n), dla n = 1, 2, . . . 12, przedstawia poniższa tabela:
n 1 2 3 4 5 6 7 8 9 10 11 12
l(n) 1 2 4 7 13 24 44 81 149 274 504 927

Zadanie 8 (por. Junior 2010, pytanie 30). Pasek kodu kreskowego
tworzą na przemian kreski czarne i białe. Kod ten zawsze zaczyna się
i kończy czarną kreską. Każda z kresek (czy to czarna, czy biała) ma
grubość 1 albo 2 (patrz rysunek 16). Ile jest pasków długości n o różnych
kodach (kody zawsze czytamy od lewej do prawej strony)?
n
Rysunek 16. Przykład kodu
12 1. ZLICZANIE REKURENCYJNE
Rozwiązanie. Niech L(n) oznacza liczbę różnych kodów długo-
ści n. Wtedy oczywiście:

L(1) = 1, L(2) = 1, L(3) = 1 i L(4) = 3 .

Niech n będzie większe niż 4. Jak wyznaczyć liczbę L(n) za pomocą
liczb L(m) dla m < n? Tym razem nie wystarczy uwzględnić jaką
kreską kończy się kod; trzeba także uwzględnić jaką kreską się zaczyna.
Mamy cztery możliwe przypadki przedstawione na rysunku 17.
n - 2 n - 3 n - 3 n - 4
n n n n
Rysunek 17. Możliwe cztery przypadki
Rozważmy kolejno każdy z tych przypadków.
a) Jeżeli kod zaczyna i kończy się kreskami grubości 1, to aby
uzyskać kod długości n, trzeba wypełnić przestrzeń długości
n - 2 kodem zaczynającym i kończącym się białymi kreskami.
Liczba takich kodów jest oczywiście równa L(n - 2) (bo liczba
kodów będzie taka sama, gdy zamienimy kolory).
Analogicznie w pozostałych trzech przypadkach.
b) Jeżeli kod zaczyna się kreską grubości 1, a kończy kreską gru-
bości 2, to liczba takich kodów jest równa L(n - 3).
c) Jeżeli kod zaczyna się kreską grubości 2, a kończy kreską gru-
bości 1, to liczba takich kodów jest także równa L(n - 3).
d) Jeżeli kod zaczyna się i kończy kreskami grubości 2, to liczba
takich kodów jest równa L(n - 4).
StÄ…d otrzymujemy:

L(n) = L(n - 2) + 2 · L(n - 3) + L(n - 4) .

Wykorzystując otrzymany wzór rekurencyjny, obliczamy kolejne wy-
razy ciÄ…gu L(n). Dla n = 1, 2, . . . , 13 mamy:
n 1 2 3 4 5 6 7 8 9 10 11 12 13
L(n) 1 1 1 3 4 6 11 17 27 45 72 116 189

4. ZBIORY 13
4. Zbiory
Zbiory są najprostszymi strukturami i można je badać za pomocą
relacji przynależności elementu do zbioru. Pokażemy tutaj, że do zlicza-
nia liczby zbiorów o wskazanych własnościach rekurencja także może
być przydatna.
Zadanie 9. Zbiór X ma n elementów. Ile jest różnych podzbiorów
zbioru X o k elementach?
Dowód. Zauważmy, że jeśli k > n, to nie istnieje żaden podzbiór
zbioru X o k elementach. Załóżmy więc, że 0 k n. Niech C(n, k)
oznacza liczbę wszystkich k elementowych podzbiorów zbioru X. Po-
nieważ jedynym zbiorem o 0 elementach jest zbiór pusty, a jedynym
podzbiorem zbioru X o n elementach jest zbiór X, to dla dowolnych n:

C(n, 0) = 1 i C(n, n) = 1 .

Niech 1 < k < n. Ustalmy element x " X. Jeżeli Y jest k
elementowym podzbiorem zbioru X, to albo x " Y , albo x " Y (patrz
/
rysunek 18). Podzbiorów k elementowych zbioru X, do których x nie
x
x
Y
Y
x " Y x " Y
/
Rysunek 18
należy jest tyle, ile jest k elementowych podzbiorów zbioru X \ {x},
czyli dokładnie C(n - 1, k). Natomiast podzbiorów k elementowych
zbioru X, do których x należy jest tyle, ile jest (k - 1) elementowych
podzbiorów zbioru X \ {x} , czyli C(n - 1, k - 1). Bo każdy z nich
można otrzymać przez dołączenie elementu x do dowolnie wybranego
(k - 1) elementowego podzbioru zbioru X \ {x}. StÄ…d otrzymujemy
równość:

C(n, k) = C(n - 1, k - 1) + C(n - 1, k) .

14 1. ZLICZANIE REKURENCYJNE
Z ustalonych zależności łatwo obliczamy kolejne wartości C(n, k):
n k 0 1 2 3 4 5 6 7 8 9 10
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
7 1 7 21 35 35 21 7 1
8 1 8 28 56 70 56 28 8 1
9 1 9 36 84 126 126 84 36 9 1
10 1 10 45 120 210 252 210 120 45 10 1

Trójkąt liczb z tabeli zwany jest trójkątem Pascala. Liczby n tego
wiersza tabeli są kolejnymi współczynnikami w rozwinięciu wyrażenia
(a + b)n, dokładniej prawdziwa jest równość:

n

(a + b)n = C(n, k)akbn-k .
k=0


n
Liczbę C(n, k) często oznacza się symbolem , który nazywany
k
jest symbolem Newtona. Nadmieńmy jeszcze, że można udowodnić rów-
ność (zobacz [2]):

n!
C(n, k) = .
k! · (n - k)!

Zadanie 10. Danych jest n różnokolorowych kredek. Kredki te roz-
kładamy do k jednakowych (nierozróżnialnych) pudełek tak, że w każ-
dym z tych pudełek znajdzie się przynajmniej jedna kredka. Na ile
sposobów możemy to zrobić?
Rozwiązanie. Niech X oznacza zbiór kredek. Każde rozłożenie
kredek do k pudełek powoduje rozbicie zbioru X na k niepustych pod-
zbiorów X1, X2, . . . , Xk, co w języku teorii zbiorów możemy zapisać
następująco:
4. ZBIORY 15
a) Xi ‚" X, dla każdego i = 1, 2, . . . , k,
b) Xi = ", dla każdego i = 1, 2, . . . , k,

c) X = X1 *" X2 *" . . . *" Xk.
Każdą rodzinę zbiorów {X1, X2, . . . , Xk} spełniającą powyższe warunki
nazywamy rozkładem zbioru X na k klas (każde Xi to klasa).
Zatem nasze zadanie polega na wyznaczeniu liczby wszystkich rozkła-
dów zbioru n elementowego na k klas. Oznaczmy poszukiwaną liczbę
przez S(n, k).
Oczywiście, jeśli k > n, to żądany rozkład jest niemożliwy. Załóżmy
więc, że 1 k n. Gdy k = 1, to jedyną klasą musi być cały zbiór X,
więc:

S(n, 1) = 1 .

Podobnie, gdy k = n, to jedynym rozkładem jest rodzina zbiorów jed-
noelementowych {{z}; z " X}, więc:

S(n, n) = 1 .

Niech 1 < k < n. Ustalmy element x " X. Jeżeli wez
miemy dowolny
rozkład zbioru X na k klas, to albo {x} jest klasą tego rozkładu, albo
{x} nie jest klasą tego rozkładu (patrz rysunek 19). Rozkładów zbioru
x klasa {x}
k klas
k - 1 klas
x
X \ {x}
X
Rysunek 19
X na k klas, w których {x} jest klasą jest tyle, ile jest rozkładów zbioru
X \ {x} na k - 1 klas, czyli S(n - 1, k - 1). Natomiast każdy rozkład
zbioru X na k klas, w których {x} nie jest klasą można zrealizować
16 1. ZLICZANIE REKURENCYJNE
następująco: wziąć dowolny rozkład zbioru X \ {x} na k klas i dołączyć
element x do jednej dowolnie wybranej spośród tych klas. Przeto liczba
takich rozkÅ‚adów jest równa k · S(n - 1, k). StÄ…d otrzymujemy równość:

S(n, k) = S(n - 1, k - 1) + k · S(n - 1, k) .

Z ustalonych zależności łatwo obliczamy kolejne wartości S(n, k):
n k 1 2 3 4 5 6 7 8 9 10
1 1
2 1 1
3 1 3 1
4 1 7 6 1
5 1 15 25 10 1
6 1 31 90 65 15 1
7 1 63 301 350 140 21 1
8 1 127 966 1701 1050 266 28 1
9 1 255 3025 7770 6951 2646 462 36 1
10 1 511 9330 34105 42525 22827 5880 750 45 1

W literaturze matematycznej liczby S(n, k) zwane sÄ… liczbami Stir-
linga drugiego rodzaju (zobacz [2]).
Zadanie 11. Siedmiu kierowców ma pięcioma samochodami poje-
chać do pewnej miejscowości. Ile jest różnych możliwości rozmieszczenia
kierowców w samochodach?
Rozwiązanie. Rozmieszczenie 7 kierowców w 5 samochodach de-
finiuje funkcję ze zbioru kierowców  na zbiór samochodów (żaden sa-
mochód nie odjedzie bez kierowcy). Zatem ile jest takich funkcji? Aby
taką funkcję zdefiniować należy wziąć rozkład zbioru 7 kierowców na 5
klas, co można uczynić na S(7, 5) sposobów. Mając rozkład, wszystkim
elementom klasy przyporządkowujemy ten sam samochód, przy czym
elementom różnych klas różne samochody, co możemy zrobić na 5! spo-
sobów. Zatem liczba poszukiwanych funkcji (z uwzględnieniem wartości
z tabeli) jest równa 5! · S(7, 5) = 120 · 140.
5. ŚCIEżKI W GRAFACH 17
5. Ścieżki w grafach
W tym paragrafie zajmiemy się przykładami zliczania ścieżek w
grafach zorientowanych.
Zadanie 12 (por. Junior 2007, pytanie 23). Równoramienny trój-
kąt prostokątny o przyprostokątnych długości całkowitej n dzielimy na
trójkąty prostokątne o przyprostokątnych równych 1 (patrz przykład
dla n = 5 na rysunku 20).
B
A
Rysunek 20. Przykład dla n = 5
Na ile sposobów możemy przejść z końca A przeciwprostokątnej do
jej końca B, poruszając się po bokach małych trójkątów prostokątnych
zgodnie z kierunkiem strzałek według schematu ?
Rozwiązanie. Jeśli naniesiemy wszystkie strzałki zgodnie ze sche-
(n + 1)(n + 2)
matem, to otrzymamy graf zorientowany o t(n + 1) =
2
wierzchołkach. Umieśćmy ten graf w układzie współrzędnych, tak jak
na rysunku 21. Mamy wyznaczyć liczbę wszystkich ścieżek w tym grafie
prowadzących od punktu A = (0, 0) do punktu B = (n, n). Rozwiążmy
18 1. ZLICZANIE REKURENCYJNE
zadanie pozornie nieco ogólniejsze. Spróbujmy wyznaczyć liczbę ście-
żek kończących się w dowolnym punkcie o współrzędnych (n, k), dla
dowolnych n i k takich że, 0 k n.
y
B = (5, 5)
5
4
3
2
1
x
A = (0, 0)
1 2 3 4 5
Rysunek 21
Niech d(n, k) oznacza liczbę wszystkich ścieżek w grafie prowadzą-
cych od punktu A = (0, 0) do punktu P = (n, k). Mamy następujące
trzy istotnie różne możliwości osiągnięcia punktu P zależne od jego
współrzędnej k. Musimy osobno rozważyć przypadki: k = 0, k = n
oraz 1 k < n. Przypadki te ilustruje rysunek 22.
(n, n) (n - 1, k) (n, k)
(n - 1, 0) (n, 0) (n - 1, n - 1) (n, n - 1) (n - 1, k - 1) (n, k - 1)
Rysunek 22
Stąd mamy następujące zależności rekurencyjne pomiędzy poszuki-
wanymi liczbami:
5. ŚCIEżKI W GRAFACH 19

a) jeżeli k = 0, to d(0, 0) = 0 oraz d(n, 0) = 1 dla n > 0;


b) jeżeli k = 1, to d(1, 1) = 2 oraz:


d(n, 1) = d(n, 0) + d(n - 1, 0) + d(n - 1, 1) ,

dla n > 1;
c) jeżeli 1 < k < n, to:

d(n, k) = d(n, k - 1) + d(n - 1, k - 1) + d(n - 1, k) ;

d) jeżeli k = n, to:

d(n, k) = d(n, k - 1) + d(n - 1, k - 1) ,

czyli:

d(n, n) = d(n, n - 1) + d(n - 1, n - 1) .

Obliczanie wartości d(n, k) dla większych liczb n i k jest dość kło-
potliwe, gdyż wymaga wykonania dość dużej liczby operacji (złożoność
obliczeniowa problemu jest duża). Jednakże niezbędne obliczenia może-
my wykonać przy pomocy komputera. W tym celu, wystarczy ustalone
zależności rekurencyjne zapisać w języku programowania. Napiszmy ta-
ką procedurę w języku PASCAL.
Function d(n,k:LongInt):LongInt;
begin
if k=0 then
begin
if n=0 then d:=0;
if n>0 then d:=1;
end {k=0}
else if k=1 then
begin
if n=1 then d:=2;
if n>1 then d:=d(n,k-1)+d(n-1,k-1)+d(n-1,k)
end {k=1}
else if kelse d:=d(n,k-1)+d(n-1,k-1) {k>1}
end;
20 1. ZLICZANIE REKURENCYJNE
Początkowe wartości d(n, k), obliczone przy użyciu tej procedury
zawiera tabela:
n k 0 1 2 3 4 5 6 7 8 9 10
0 0
1 1 2
2 1 4 6
3 1 6 16 22
4 1 8 30 68 90
5 1 10 48 146 304 394
6 1 12 70 264 714 1412 1806
7 1 14 96 430 1408 3534 6752 8558
8 1 16 126 652 2490 7432 17718 33028 41586
9 1 18 160 938 4080 14002 39152 89898 164512 206098
10 1 20 198 1296 6314 24396 77550 206600 461010 831620 1037718
Z tabeli odczytujemy, że liczba różnych ścieżek prowadzących z punktu
A do punktu B w grafie z rysunku 20, tj. d(5, 5), jest równa 394.
Zadanie 13 (por. Junior 2006, pytanie 30). W meczu piłki ręcznej
drużyna gospodarzy objęła prowadzenie i utrzymała je do stanu n : k.
Na ile sposobów mogły padać bramki w tym meczu do tego momentu?
Rozwiązanie. Zilustrujmy możliwy przebieg meczu do stanu n : k,
n > k, za pomocÄ… grafu zorientowanego. Wynikowi x : y przyporzÄ…d-
y
(6, 5)
5
4
3
2
1
x
O 1 2 3 4 5 6
Rysunek 23. Graf przebiegu meczu
kujmy punkt kratowy o współrzędnych (x, y), a punkty (x, y) łączymy
5. ŚCIEżKI W GRAFACH 21
strzałkami z punktami (u, v), gdy wynik u : v jest możliwym wynikiem
bezpośrednio po wyniku x : y. Graf taki dla n = 6 i k = 5 przedstawia
rysunek 23.
Liczba możliwości zdobywania bramek przez obie drużyny do stanu
n : k zgodnie z warunkami zadania jest równa liczbie ścieżek w gra-
fie prowadzących od punktu O = (0, 0) do punktu o współrzędnych
(n, k). Oznaczmy tę liczbę przez w(n, k). Posługując się grafem z ry-
sunku 23, spróbujmy opisać zależności rekurencyjne pomiędzy poszu-
kiwanymi liczbami. Mamy:

a) jeżeli k = 0, to w(0, 0) = 0 oraz w(n, 0) = 1 , dla n > 0;


b) jeżeli k = 1, to w(2, 1) = 1 oraz:


w(n, 1) = w(n, 0) + w(n - 1, 1) ,

dla n > 2;
c) jeżeli 1 < k < n - 1, to:

w(n, k) = w(n, k - 1) + w(n - 1, k) ;

d) jeżeli k = n - 1, to:

w(n, k) = w(n, k - 1) ,

czyli:

w(n, n - 1) = w(n, n - 2) .

Wartości w(n, k) w dość wąskim zakresie zebrano poniżej w tabeli:
n k 0 1 2 3 4 5 6 7 8 9 10
0 0
1 1
2 1 1
3 1 2 2
4 1 3 5 5
5 1 4 9 14 14
6 1 5 14 28 42 42
7 1 6 20 48 90 132 132
8 1 7 27 75 165 297 429 429
9 1 8 35 110 275 572 1001 1430 1430
10 1 9 44 154 429 1001 2002 3432 4862 4862
11 1 10 54 208 637 1638 3640 7072 11934 16796 16796
Z tabeli możemy odczytać, że przykładowy wynik 6 : 5 można uzyskać
na 42 sposoby.
22 1. ZLICZANIE REKURENCYJNE
Większe wartości można obliczać przy pomocy programu kompute-
rowego, wykorzystujÄ…cego ustalony opis rekurencyjny. Oto kilka przy-
kładów otrzymanych tym sposobem:
w(20, 15) = 463991880,
w(20, 16) = 811985790,
w(20, 17) = 1289624490,
w(20, 18) = 1767263190,
w(20, 19) = 1767263190.
6. Zadania do samodzielnego rozwiÄ…zania
Zadanie 14. Rysujemy kolejne trójkąty równoboczne o bokach dłu-
gości całkowitej i dzielimy je na trójkąty równoboczne o boku 1 (rysu-
nek 24).
1 2 3 4
Rysunek 24. Kolejne trójkąty równoboczne
a) Z ilu trójkątów o boku długości 1 składa się trójkąt o boku długo-
ści n?
b) Ile jest wszystkich trójkątów równobocznych na n tym rysunku?
c) Ile jest wszystkich rombów na n tym rysunku?
Zadanie 15. Na ile sposobów można pokryć prostokąt o wymiarach
n × 3, prostokÄ…tami o wymiarach 2 × 1?
Zadanie 16. Liczba a jest iloczynem n parami różnych liczb pierw-
szych p1, p2, . . . , pn. Ile jest możliwych przedstawień liczby a w postaci
iloczynów liczb całkowitych większych od 1 (iloczyny różniące się po-
rządkiem czynników uważamy za takie same)?
Zadanie 17. Ile jest wszystkich rozkładów dodatniej liczby całko-
witej n w sumę dodatnich składników całkowitych nie większych niż
LITERATURA 23
ustalona dodatnia liczba całkowita k? Rozkłady różniące się porząd-
kiem składników uważamy za takie same.
Zadanie 18. W meczu koszykówki drużyna gości pierwsza zdobyła
punkty i nie przegrywała tego meczu do stanu n : k. Na ile sposobów
mogły być zdobywane punkty w tym meczu do tego momentu?
Literatura
[1] Richard. A. Dunlap, The Golden Ratio and Fibonacci Numbers, World Scien-
tific, Singapore 1998.
[2] Jürgen Flachsmeyer, Kombinatoryka. Podstawowy wykÅ‚ad w ujÄ™ciu mnogoÅ›cio-
wym, PWN, Warszawa 1977.
[3] Maciej M. Sysło, Piramidy, szyszki i inne konstrukcje algorytmiczne WSiP,
Warszawa 2000.
[4] Matematyka z wesołym kangurem (Testy z rozwiazaniami kategorii Kadet i
Junior z lat 1991-2009), Aksjomat, Toruń 2009.