ZLICZANIE
REKURENCYJNE
Andrzej Sendlewski
Wydział Matematyki i Informatyki UMK w Toruniu
MA-TA II, Ciechanów 22 maja 2010
ZLICZANIE
REKURENCYJNE
Andrzej Sendlewski
Wydział Matematyki i Informatyki UMK w Toruniu
MA-TA II, Ciechanów 22 maja 2010
♣ Liczby figuralne jako
jeden z najprostszych
sposobów wprowadzenia w
myślenie rekurencyjne
PROBLEM 1.
Rysujemy kolejne kwadraty
o bokach długości całkowitej i dzielimy je na
kwadraty jednostkowe.
1
2
3
4
Z ilu kwadratów jednostkowych składa się
kwadrat o boku długości n?
Ile jest wszystkich kwadratów na n-tym ry-
sunku?
3
4
'
&
$
%
k(n) =
1, jeżeli n = 1;
k(n − 1) + 2n − 1, jeżeli n > 0.
2
3
4
'
&
$
%
k(n) =
1, jeżeli n = 1;
4, jeżeli n = 2;
k(n − 2) + 4n − 4, jeżeli n > 0.
PROBLEM 2.
Rysujemy kolejne trójkąty
o bokach długości całkowitej i dzielimy je na
przystające trójkąty o boku 1.
3
4
2
1
Z ilu małych trójkątów składa się trójkąt
o boku długości n?
Ile jest wszystkich trójkątów równobocz-
nych na n-tym rysunku?
3
4
'
&
$
%
k(n) =
1, jeżeli n = 1;
k(n − 1) + n + (n − 1), jeżeli n > 0.
PROBLEM 3.
Z jednakowych monet ukła-
damy kolejne „trójkąty równoboczne”, tak
jak na rysunku.
3
4
2
1
Jaka jest wartość monet tworzących n–ty
trójkąt?
3
4
'
&
$
%
t(n) =
1, jeżeli n = 1;
t(n − 1) + n, jeżeli n > 1.
1
2
3
4
1
2
3
4
k(n) = t(n) + t(n − 1)
1
2
3
4
Z równości
(n + 1)
2
= k(n + 1) = 2t(n) + (n + 1)
mamy
#
"
!
t(n) =
n(n + 1)
2
PROBLEM 4.
Z jednakowych sześcien-
nych klocków budujemy kolejne piramidy
trójkątne, jak na rysunku.
1
2
3
4
Z ilu sześciennych klocków zbudowana jest
n–ta piramida trójkątna?
3
4
Żółta ściana zbudowana jest z t(n) sześcien-
nych klocków, a więc
'
&
$
%
pt(n) =
1, jeżeli n = 1;
pt(n − 1) +
n(n + 1)
2
, jeżeli n > 1.
PROBLEM 5.
Z jednakowych sześcien-
nych klocków budujemy kolejne piramidy
„kwadratowe”, jak na rysunku
1
2
3
4
Z ilu sześciennych klocków zbudowana jest
n–ta piramida?
3
4
Żółta podstawa zbudowana jest z k(n) sze-
ściennych klocków, a więc
'
&
$
%
p(n) =
1, jeżeli n = 1;
p(n − 1) + n
2
, jeżeli n > 1.
♦ Co wspólnego z ciągiem
Fibonacci’ego ma:
bieganie po schodach,
układanie kafelków,
gra w koszykówkę,
liczenie kodów kreskowych?
PROBLEM 6.
Na taras wieży widokowej
prowadzą schody o n stopniach.
0
1
2
3
n−2
n−1
n
Turysta wchodzi na taras wykonując lo-
sowo kroki co 1 albo co 2 stopnie. Na ile spo-
sobów turysta może przejść schody?
0
1
2
3
n−2
n−1
n
'
&
$
%
s(n) =
1, jeżeli n = 1;
2, jeżeli n = 2;
s(n − 2) + s(n − 1), jeżeli n > 2.
PROBLEM 7.
Mamy pokryć prostokątny
pas podłogi o wymiarach n × 2 prostokątnymi
kafelkami o wymiarach 2 × 1. (kafelków nie
wolno łamać.) Na ile sposobów możemy to
zrobić?
2
1
2
3
3
3
n−1
1
n−2
2
'
&
$
%
s(n) =
1, jeżeli n = 1;
2, jeżeli n = 2;
s(n − 2) + s(n − 1), jeżeli n > 2.
PROBLEM 8.
Ile jest sposobów zdobycia
n punktów w meczu koszykówki przez jedną
z drużyn?
+2
+2
+3
+1
+1
+1
0
1
2
3
l(1) = 1,
l(2) = 2,
l(3) = 4.
+1
+2
+3
n−3
n−2
n−1
n
'
&
$
%
l(n) =
1, jeżeli n = 1;
2, jeżeli n = 2;
4, jeżeli n = 3;
l(n − 3) + l(n − 2) + l(n − 1), jeżeli n > 3.
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
PROBLEM 9.
(porównaj Junior 2010, py-
tanie 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 (przykładowy kod na rysunku).
n
Ile jest pasków długości n o różnych ko-
dach (kody zawsze czytamy od lewej do pra-
wej strony)?
1
2
3
4
4
4
L(1) = 1,
L(2) = 1,
L(3) = 1,
L(4) = 3.
n
n−2
n
n−3
n−3
n
n
n−4
L(n) = L(n − 2) + 2 · L(n − 3) + L(n − 4)
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
♥ Zbiór skończony i jego
podzbiory, rozkłady zbioru
w rodziny podzbiorów
PROBLEM 10.
Zbiór X ma n elementów.
Ile jest różnych podzbiorów zbioru X o k ele-
mentach?
Jeśli k > n, to nie istnieje żaden podzbiór
zbioru X o k elementach. Załóżmy więc, że
0
6 k 6 n.
Niech
C(n, k)
oznacza liczbę wszystkich k–elementowych
podzbiorów zbioru X.
Oczywiście
C(n, 0) = 1,
C(n, n) = 1.
Ustalmy element x ∈ X. Niech Y będzie do-
wolnym k–elementowym podzbiorem zbioru
X. Mamy dwa przypadki: x /
∈ Y albo x ∈ Y
x
x
Y
Y
X
X
C(n, k) = C(n − 1, k − 1) + C(n − 1, k)
Trójkąt Pascala
n k 0 1
2
3
4
5
6
7 8 9
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
PROBLEM 11.
Danych jest n różnoko-
lorowych kredek. Kredki te rozkł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ć?
Niech X oznacza zbiór kredek. Każde roz-
łożenie kredek do k pudełek powoduje roz-
bicie zbioru X na k niepustych podzbiorów
X
1
, X
2
, . . . , X
k
.
Oznaczmy poszukiwaną liczbę przez
S(n, k).
Jeśli k > n, to żądany rozkład jest niemoż-
liwy. Załóżmy więc, że 1 6 k 6 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 roz-
kładem jest rodzina zbiorów jednoelemento-
wych {{z}; z ∈ X}, więc:
S(n, n) = 1 .
Niech 1 < k < n. Ustalmy element x ∈ X. Je-
żeli weźmiemy dowolny rozkład zbioru X na
k klas, to mamy dwa przypadki: albo {x} jest
klasą tego rozkładu, albo {x} nie jest klasą
tego rozkładu
x
X
x
X−{x}
klasa {x}
k−1 klas
k klas
S(n, k) = S(n − 1, k − 1) + k · S(n − 1, k)
Liczby Stirlinga
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
♠ O pewnym meczu
piłkarskim, czyli o zliczaniu
ścieżek w grafie
skierowanym
PROBLEM 12.
(porównaj Junior 2006,
pytanie 30)
W meczu piłki ręcznej drużyna gospodarzy
objęła prowadzenie i utrzymała je do stanu
n : k (oczywiście n > k). Na ile sposobów mo-
gły padać bramki w tym meczu do tego mo-
mentu?
Zilustrujmy możliwy przebieg meczu do
stanu n : k, n > k, za pomocą grafu zorien-
towanego. Wynikowi x : y przyporządkujmy
punkt kratowy o współrzędnych (x, y), a
punkty (x, y) łączymy strzałkami z punktami
(u, v), gdy wynik u : v jest możliwym wyni-
kiem bezpośrednio po wyniku x : y. Graf taki
dla n = 6 i k = 5 przedstawia rysunek na na-
stępnym slajdzie.
5
4
3
2
1
O
1
2
3
4
5
6
x
y
B
Oznaczmy przez w(n, k) liczbę wszystkich
ścieżek prowadzących od punktu (0, 0) do
punktu (n, k). 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) .
Tabela wartości w(n, k)
n k 0 1
2
3
4
5
6
7
8
9
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
Większe wartości w(n, k) mogące być
wynikami rzeczywistego meczu:
w(20, 15) = 463991880,
w(20, 16) = 811985790,
w(20, 17) = 1289624490,
w(20, 18) = 1767263190,
w(20, 19) = 1767263190.