4 Funkcje tworz¡ce

Wielomiany tworz¡ce

4.1 Do tej pory na ci¡gach dokonywali±my dwóch operacji arytmetycznych:

mno»enia ci¡gu przez skalar i dodawania ci¡gów (`"po wspóªrz¦dnych"). Dzia-

ªania te wprowadzaj¡ na zbiorze ci¡gów struktur¦ przestrzeni liniowej. Wpro-

wadzimy teraz jeszcze jedn¡ operacj¦ tzw. splot ci¡gów. Jakkolwiek  przynaj-

mniej na razie  b¦dziemy zajmowa¢ si¦ ci¡gami sko«czonymi, to dla jednolito-

±ci zapisów wygodnie b¦dzie traktowa¢ wszystkie ci¡gi jako ci¡gi niesko«czone

indeksowane liczbami naturalnymi N, uzupeªniaj¡c brakuj¡ce wyrazy ci¡gów

sko«czonych zerami. W takim uj¦ciu ci¡g (a

i

)

∞
i=0

jest sko«czony, je±li istnieje

takie n ∈ N, »e a

i

= 0

dla wszystkich i > n.

Denicja. Niech a = (a

i

)

∞
i=0

i b = (b

i

)

∞
i=0

b¦d¡ ci¡gami (sko«czonymi lub

niesko«czonymi). Splotem ci¡gów a i b nazywamy ci¡g c = a ∗ b, w którym

c

i

=

i

X

j=0

a

j

b

i−j

= a

0

b

i

+ a

1

b

i−1

+ · · · + a

i

b

0

(1)

dla ka»dego i ∈ N.

Przykªad. Niech a

i

=

x

i

, b

i

=

y

i

i c

i

=

x+y

i

. Wówczas wzór Chu-

Vandermonde'a z ?? jest równowa»ny stwierdzeniu, »e c = a ∗ b.
4.2 Zauwa»my podobie«stwo formalne splotu do operacji mno»enia wielomia-

nów. Uzasadnia to wprowadzenie nast¦puj¡cej denicji.

Denicja. Je»eli (a

i

)

n
i=0

jest ci¡giem sko«czonym, to wielomianem generuj¡-

cym dla ci¡gu a nazywamy wielomian A(t) = P

n
i=0

a

i

t

i

.

Uwaga. Z logicznego punktu widzenia wielomian jest niczym innym jak ci¡giem

swoich wspóªczynników i w ten sposób deniuje si¦ go w algebrze. ‘ci±le rzecz

bior¡c, powy»sza denicja nie deniuje wi¦c »adnego nowego obiektu, a jedynie

wskazuje na algebraiczne aspekty ci¡gów.

Technika wielomianów wie»owych

4.3 Wiele zagadnie« kombinatorycznych sprowadza si¦ do wyliczenia ilo±ci

permutacji speªniaj¡cych pewn¡ ilo±¢ ogranicze« zabraniaj¡cych na pewnych

miejscach stawia¢ pewne z góry okre±lone elementy. Zagadnienia takie mo»na

przetªumaczy¢ na zadanie wyliczenia ilo±ci rozstawie« pewnej liczby wzajemnie

nie atakuj¡cych si¦ wie» na specycznej szachownicy.

Problem. Niech B b¦dzie prostok¡tem zªo»onym z pewnej liczby kwadratów

jednostkowych zwanych polami. Zaªó»my, »e w±ród wszystkich pól jednostko-

wych B wyró»niono pewien zbiór pól nazywanych polami dozwolonymi. Pole,

które nie jest polem dozwolonym, nazywamy polem zabronionym. Prostok¡t,

w którym wyró»niono pola dozwolone, nazywamy szachownic¡. (Rysyj¡c sza-

chownic¦, b¦dziemy pola zabronione oznacza¢ znakiem x , a pola dozwolone

1

b¦dziemy pozostawia¢ puste.) Na ile sposobów mo»na na szachownicy B roz-

stawi¢ i wzajemnie nie atakuj¡cych si¦ wie»? (Wie»a atakuje wszystkie pola,

które le»¡ w tym samym rz¦dzie pionowym lub poziomym).

Poka»emy, jak rozwi¡za¢ ten problem, wykorzystuj¡c wielomiany generu-

j¡ce. Przedtem jednak kilka zada« równowa»nych poszczególnym przypadkom

powy»szego problemu.
4.4 Przykªad. Cztery osoby A, B, C i D zostaªy wybrane przez komisj¦

kwalikacyjn¡ do podj¦cia pracy na czterech stanowiskach a, b, c i d. Osoba A

nie mo»e obj¡¢ stanowiska b ani c, osoba B nie mo»e obj¡¢ stanowiska a, osoba
C

nie mo»e obj¡¢ stanowiska a, b ani d natomiast osoba D nie mo»e obj¡¢

stanowiska c ani d. Na ile sposobów mo»na przydzieli¢ stanowiska?

Obsadzenie stanowisk jest równowa»ne rozstawieniu czterech nie atakuj¡cych

si¦ wie» na nast¦puj¡cej szachownicy.

a

b

c

d

A

x x

B

x

C

x x

x

D

x x

4.5 Przykªad. Ile jest permutacji zbioru [5], w których dla ka»dego i =
1, 2, . . . , 5

, liczba i nie stoi ani na miejscu i-tym, ani na (i + 1)-szym?

Permutacji (k

1

, k

2

, . . . , k

5

)

przyporz¡dkowujemy rozstawienie wie» na sza-

chownicy

x x

x x

x x

x x

x

,

w którym wie»a w i-tej kolumnie stoi w k

i

-tym wierszu.

4.6 Przykªad. Prostok¡tem ªaci«skim wymiary m × n nazywamy macierz o
m

wierszach i n kolumnach, w której ka»dy wiersz jest permutacj¡ [n] i »adna

kolumna nie zawiera dwóch równych liczb.

Na ile sposobów mo»na do prostok¡ta ªaci«skiego





4

1

5

3

2

1

2

4

5

3

2

5

3

4

1





dopisa¢ czwarty wiersz tak, aby znowu otrzyma¢ prostok¡t ªaci«ski?

2

Zadanie jest równowa»ne policzeniu rozstawie« 5 wie» na szachownicy

x x

x

x x

x

x x x
x x x

x x x

.

4.7 Denicja. Niech B b¦dzie szachownic¡ i niech r

B

i

oznacza ilo±¢ rozstawie«

i

nie atakuj¡cych si¦ wie» na polach dozwolonych szachownicy B (przyjmujemy

przy tym, »e r

B

0

= 1

). Wielomian generuj¡cy r

B

(t)

dla ci¡gu (r

B

i

)

i=0,1,...

nazy-

wamy wielomianem wie»owym B:

r

B

(t) =

∞

X

i=0

r

B

i

t

i

.

Zauwa»my, »e poniewa» na szachownicy o wymiarach m × n nie mo»na usta-

wi¢ wi¦cej ni» min(m, n) wzajemnie nie atakuj¡cych si¦ wie», to r

B

(t)

jest w

istocie wielomianem.
4.8 Wyliczenie wielomianu wie»owego

Zacznijmy od kilku prostych uwag dotycz¡cych wyliczenia wielomianów wie»o-

wych.

•

Je»eli jaki± wiersz lub kolumna B skªada si¦ z samych pól zabronionych,

to usuni¦cie go nie zmienia r

B

(t)

.

•

Permutacja wierszy (kolumn) szachownicy nie zmienia r

B

(t)

.

•

Je»eli szachownica B jest postaci

B =

B

1

B

2

B

3

B

4

,

gdzie szachownice B

2

i B

3

skªadaj¡ si¦ wyª¡cznie z pól zabronionych, to

r

B

(t) = r

B

1

(t)r

B

4

(t)

.

Powy»sze uwagi uªatwiaj¡ wyliczenie wielomianu wie»owego, ale nie rozwi¡zuj¡

caªkowicie problemu. Wªa±ciwego narz¦dzia dostarcza nast¦puj¡ce twierdzenie.

Twierdzenie. Niech B b¦dzie dowoln¡ szachownic¡ i niech s b¦dzie jednym z

dozwolonych pól w B. Niech B

1

b¦dzie szachownic¡ powstaª¡ z B przez zamian¦

pola s na zabronione i niech B

2

b¦dzie szachownic¡ powstaª¡ przez usuni¦cie z

B

wiersza i kolumny zawieraj¡cej s. Wówczas

r

B

(t) = r

B

1

(t) + t · r

B

2

(t).

(2)

Dowód. Dzielimy zbór wszystkich rozstawie« i wie» na dwa podzbiory: zbór

rozstawie«, w których na polu s nie stoi »adna wie»a i zbór rozstawie«, w których

na polu s stoi wie»a. Pierwszych rozstawie« jest dokªadnie r

B

1

i

, a drugich r

B

2

i−1

.

3

4.9 Negatywem szachownicy B nazywamy szachownic¦ ¯

B

otrzyman¡ z B przez

zamian¦ wszystkich pól zabronionych na dozwolone i odwrotnie.

Twierdzenie. Niech B b¦dzie kwadratow¡ szachownic¡ n × n. Ilo±¢ sposobów

rozmieszczenia n nie atakuj¡cych si¦ wie» na polach dozwolonych szachownicy

¯

B

jest równa

n! − (n − 1)!r

B

1

+ (n − 2)!r

B

2

− · · · + (−1)

n

0!r

B

n

.

(3)

Dowód. Zastosujemy schemat wª¡czania i wyª¡czania. Niech A b¦dzie zbiorem

rozstawie« n nie atakuj¡cych si¦ wie» na wszystkich (dopuszczalnych i zabro-

nionych) polach szachownicy B. Dla dowolnego i = 1, 2, . . . , n oznaczmy przez
A

i

zbór tych rozstawie« z A, w których wie»a stoj¡ca w wierszu i-tym stoi na

polu dozwolonym szachownicy B. Rozstawienia n wie» na polach dozwolonych

¯

B

to dokªadnie te rozstawienia z A, w których »adna wie»a nie stoi na polu

dozwolonym w B, a wi¦c ich liczba jest równa

|A| − |

n

[

i=1

A

i

| = |A| −

X

i

|A

i

| +

X

i<j

|A

i

∩ A

j

| − · · · + (−1)

N

|A

1

∩ A

2

∩ · · · ∩ A

n

|.

Typowy skªadnik w tej sumie |A

i

1

∩ A

i

2

∩ · · · ∩ A

i

k

|

jest równy ilo±ci rozstawie«

n

wie», w których wie»e stoj¡ce w wierszach i

1

, i

2

, . . . , i

k

stoj¡ na polach do-

zwolonych szachownicy B. Liczba ta jest iloczynem ilo±ci rozstawie« k wie» na

polach dozwolonych le»¡cych w wierszach o numerach i

1

, i

2

, . . . , i

k

szachownicy

B

i liczby (n − k)! (=liczba rozstawie« pozostaªych (n − k) wie»). Dla usta-

lonego k sumowanie po wszystkich mo»liwych ci¡gach i

1

< i

2

< · · · < i

k

daje

(n − k)!r

B

k

co dowodzi (3).

4.10 Przykªad. Poprzednie twierdzenie pozwala na szybkie wyliczenie ilo±ci

permutacji bez punktów staªych. Zauwa»my, »e permutacje [n] bez punktów

staªych odpowiadaj¡ rozstawieniom n wie» na kwadratowej szachownicy B wy-

miaru n × n, na której polami dozwolonymi s¡ wszystkie pola z wyj¡tkiem prze-

k¡tnej. Wielomian wie»owy r

¯

B

(t)

mo»na ªatwo wyliczy¢, stosuj¡c wielokrotnie

trzeci¡ reguª¦ z 4.8:

r

¯

B

(t) = (1 + t)

n

=

n

X

i=0

n

i



t

i

.

(Dwumian 1 + t jest wielomianem wie»owym dla szachownicy zªo»onej z poje-

dynczego pola dozwolonego.)

Na podstawie twierdzenia, ilo±¢ permutacji bez punktów staªych jest równa

n

X

i=0

(−1)

i

(n − i)!

n

i



=

n

X

i=0

(−1)

i

n!

i!

.

4

Funkcje tworz¡ce

4.11 Denicja. Funkcj¡ tworz¡c¡ ci¡gu a = (a

i

)

∞
i=0

nazywamy szereg

A(t) =

∞

X

i=0

a

i

t

i

= a

0

+ a

1

t + a

2

t

2

+ . . . .

W naszych zastosowaniach ci¡gi (a

i

)

b¦d¡ zazwyczaj ci¡gami liczb natural-

nych i wobec tego szereg A(t) prawie nigdy nie b¦dzie zbie»ny. My jednak nie

b¦dziemy si¦ interesowa¢ kwest¡ zbie»no±ci, traktuj¡c szeregi czysto formalnie,

jako wygodny sposób zapisu ci¡gu uªatwiaj¡cy wykonywanie operacji na ci¡-

gach, zwªaszcza operacji splotu. Je±li bowiem szeregi A(t) i B(t) odpowiadaj¡

ci¡gom a i b, to splotowi a ∗ b odpowiada szereg

a

0

b

0

+ (a

0

b

1

+ a

1

b

0

)t + (a

0

b

2

+ a

1

b

1

+ a

2

b

0

)t

2

+ . . . ,

który jest formalnym iloczynem szeregów A(t) i B(t). Jest to proste uogólnie-

nie iloczynu wielomianów na szeregi. Zbiór szeregów o wyrazach rzeczywistych

(zespolonych) z dziaªaniami dodawania i mno»enia tworzy pier±cie«.

Uwaga. Cen¡ jak¡ pªacimy za formalne traktowanie szeregów jest to, »e nie

mo»emy traktowa¢ t jako parametru: podstawienie za t liczby ró»nej od 0 zazwy-

czaj nie ma sensu. Ma natomiast sens podstawianie za t dowolnego wielomianu

(a nawet szeregu) bez wyrazu wolnego.
4.12 Je±li A(t) = P

∞
i=0

a

i

t

i

jest szeregiem, to przez [t

i

]A(t)

oznaczamy wspóª-

czynnik przy t

i

:

[t

i

]A(t) = a

i

.

Stopniem dolnym szeregu A(t) 6= 0 nazywamy najmniejszy wska¹nik i, dla któ-

rego a

i

6= 0

. Je»eli stopie« dolny A(t) jest równy n, to piszemy ldegA(t) = n.

Stwierdzenie. (1) ldegA(t) · B(t) = ldegA(t) + ldegB(t)

(2) Szereg A(t) = P

∞
i=0

a

i

t

i

jest odwracalny wtedy i tylko wtedy, gdy ldegA(t) =

0

(tzn. a

0

6= 0

). Dowód. (1) Proste przeliczenie.

(2) Konieczno±¢ warunku wynika z (1). Poka»emy, »e je±li A(t) = P

∞
i=0

a

i

t

i

i

a

0

6= 0

, to istnieje szereg B(t) = P

∞
i=0

b

i

t

i

taki, »e A(t)B(t) = 1. Warunek ten

jest równowa»ny niesko«czonemu ukªadowi równa«



a

0

b

0

=

1

a

0

b

i

+ a

1

b

i−1

+ · · · + a

i

b

0

=

0

dla i > 0,

który jest równowa»ny nast¦puj¡cej rekurencji dla ci¡gu (b

i

)

:



b

0

=

1

a

0

b

i

=

−

1

a

0

(a

1

b

i−1

+ · · · + a

i

b

0

)

dla i > 0.

W szczególno±ci mamy

1

1 − λt

=

∞

X

i=0

λ

i

t

i

.

(4)

5

(Na wzór ten mo»na patrze¢ jako na sum¦ szeregu geometrycznego.)
4.13 Dla dowolnej liczby rzeczywistej x niech P

x

(t)

b¦dzie funkcj¡ generuj¡c¡

dla ci¡gu (uogólnionych) symboli dwumianowych

x

i

∞

i=0

:

P

x

(t)

=

∞

X

i=0

x

i



t

i

=

1 + xt +

x(x − 1)

2

t

2

+ · · · +

x(x − 1) . . . (x − i + 1)

i!

t

i

+ . . . .

Ze wzoru dwumianowego Newtona wynika, »e je±li x = n jest liczb¡ naturaln¡,

to P

n

(t) = (1 + t)

n

. Z kolei ze wzoru Chu-Vadermonde'a otrzymujemy

P

x

(t)P

y

(t) = P

x+y

(t)

dla dowolnych x, y ∈ R. St¡d P

x

(t)

mo»emy traktowa¢ jako x-t¡ pot¦g¦ dwu-

mianu (1 + t). Szczególne znaczenie maj¡ szeregi dla x = −n i x =

1

n

, gdzie n

jest dodatni¡ liczb¡ naturaln¡:

(1 + t)

−n

=

1

(1 + t)

n

=

∞

X

i=0

(−1)

i

i + n − 1

n − 1



t

i

(5)

(1 − t)

−n

=

1

(1 − t)

n

=

∞

X

i=0

i + n − 1

n − 1



t

i

(6)

(1 + t)

1/n

=

n

√

1 + t = 1 −

∞

X

i=1

(−1)

i

(n − 1)(2n − 1) · · · ((i − 1)n − 1)

n

i

i!

t

i

(7)

(1 − t)

1/n

=

n

√

1 − t = 1 −

∞

X

i=1

(n − 1)(2n − 1) · · · ((i − 1)n − 1)

n

i

i!

t

i

(8)

Szeregi (6) i (8) otrzymujemy z szeregów (5) i (7) przez podstawienie t 7→ −t.

Przykªady zastosowa« szeregów

4.14 Przykªad. Na ile sposobów mo»na wypªaci¢ sum¦ n groszy przy pomocy

monet jedno, dwu i pi¦ciogroszowych?

Rozwi¡zanie. Ilo±¢ sposobów dokonania wypªaty jest równa wspóªczynnikowi

przy t

n

w iloczynie

(1 + t + t

2

+ · · · + t

i

+ . . . )(1 + t

2

+ t

4

+ · · · + t

2i

+ . . . )(1 + t

5

+ t

10

+ · · · + t

5i

+ . . . ) =

=

1

(1 − t)(1 − t

2

)(1 − t

5

)

.

4.15 Liczby Fibonacciego raz jeszcze.

Liczby Fibonacciego zdeniowali±my za pomoc¡ rekurencji

F

n

=







0

dla n = 0;

1

dla n = 1;

F

n−1

+ F

n−2

dla n ≥ 2.

6

Niech F(t) = F

0

+ F

1

t + F

2

t

2

+ . . .

b¦dzie funkcj¡ generuj¡c¡ dla ci¡gu Fibo-

nacciego. Wówczas

t

2

F (t)

=

F

0

t

2

+ f

1

t

3

+ · · · + F

n−2

t

n

+ . . .

tF (t)

=

F

0

t+F

1

t

2

+ F

2

t

3

+ · · · +F

n−1

t

n

+ . . .

(t + t

2

)F (t)

=

F

2

t

2

+ F

3

t

3

+ · · · + F

n

t

n

+ . . .

=

F (t) − t,

sk¡d otrzymujemy

F (t) =

t

1 − t(t + 1)

.

(9)

Ostatni wzór mo»emy rozwin¡¢, wykorzystuj¡c (4).

F (t)

=

t

∞

X

i=0

t

i

(1 + t)

i

=

=

t

∞

X

i=0

t

i

i

X

j=0

 i

j



t

j

=

=

t

∞

X

n=0





X

j

n − j

j







t

n

=

=

t

∞

X

n=0





X

j

n − 1 − j

j







t

n

St¡d otrzymujemy

F

n

=

n − 1

0



+

n − 2

1



+

n − 3

2



+ . . . .

Inne rozwini¦cie otrzymujemy rozkªadaj¡c praw¡ stron¦ (9) na uªamki proste.

Poniewa»

1 − t − t

2

= (1 − λ

1

t)(1 − λ

2

t),

gdzie λ

1,2

=

1 ±

√

5

2

,

wi¦c F(t) jest kombinacj¡ liniow¡ uªamków

1

1−λ

1

t

i

1

1−λ

2

t

. Rozwijaj¡c ka»dy

uªamek w szereg, otrzymujemy

F (t)

=

α

1

1 − λ

1

t

+

α

2

1 − λ

2

=

=

∞

X

n=0

(α

1

λ

n
1

+ α

2

λ

n
2

)t

n

.

Wyliczenie wspólczynników daje nam ponownie wzór otrzymany w ??.
4.16 Technik¦ rozkªadu na uªamki proste mo»na zastosowa¢ do rozwi¡zania

rekurencji liniowej.

7

Twierdzenie. Zaªó»my, »e ci¡g (u

n

)

∞

n=0

speªnia równanie rekurencyjne

u

n+r

+ a

r−1

u

n+r−1

+ · · · + a

1

u

n+1

+ a

0

u

n

= 0,

(10)

przy czym a

0

6= 0

. Je±li

λ

r

+ a

r−1

λ

r−1

+ · · · + a

1

λ + a

0

= (λ − λ

1

)

k

1

. . . (λ − λ

s

)

k

s

,

(11)

gdzie λ

i

6= λ

j

dla i 6= j, to ci¡g (u

n

)

∞

n=0

jest kombinacj¡ liniow¡ ci¡gów

(n

j

λ

n
i

)

∞

n=0

, gdzie 1 ≤ i ≤ s, 0 ≤ j ≤ k

i

− 1

.

Dowód. Mno»¡c równanie (10) stronami przez t

n+r

i dodaj¡c po wszystkich

liczbach naturalnych n, otrzymujemy

∞

X

n=0

u

n+r

t

n+r

+a

r−1

t

∞

X

n=0

u

n+r−1

t

n+r−1

+· · ·+a

1

t

r−1

∞

X

n=0

u

n+1

t

n+1

+a

0

t

r

∞

X

n=0

u

n

t

n

= 0.

Niech U(t) = P

∞
n=0

u

n

t

n

b¦dzie szeregem generuj¡cym dla ci¡gu (u

n

)

∞

n=0

. Wów-

czas powy»sze równanie przyjmuje posta¢

U (t) −

r−1

X

i=0

a

i

t

i

!

+a

r−1

U (t) −

r−2

X

i=0

a

i

t

i

!

+· · ·+a

1

t

r−1

(U (t) − u

0

)+a

0

t

r

U (t) = 0,

sk¡d otrzymujemy

U (t) =

W(t)

1 + a

r−1

t + · · · + a

1

t

r−1

+ a

0

t

r

,

gdzie W(t) jest wielomianem zmiennej t stopnia co najwy»ej r − 1. Rozkªad

(11) pozwala rozªo»y¢ funkcj¦ wymiern¡ pojawiaj¡c¡ si¦ po prawej stronie na

uªamki proste:

U (t)

=

α

1

1 − λ

1

t

+

α

2

(1 − λ

1

t)

2

+ · · · +

α

k

1

(1 − λ

1

t)

k

1

+

+

α

k

1

+1

1 − λ

2

t

+

α

k

1

+2

(1 − λ

2

t)

2

+ · · · +

α

k

1

+k

2

(1 − λ

2

t)

k

2

+ · · · +

+

α

k

1

+···+k

s−1

+1

1 − λ

s

t

+

α

k

1

+···+k

s−1

+2

(1 − λ

s

t)

2

+ · · · +

α

k

1

+···+k

s−1

+k

s

(1 − λ

2

t)

k

s

,

gdzie α

i

s¡ pewnymi staªymi liczbowymi. Korzystaj¡c ze wzoru (6), mo»emy

wszystkie uªamki proste rozwin¡¢ w szeregi postaci

1

(1 − λ

i

t)

j

=

∞

X

n=0

n + j − 1

j − 1



λ

n
i

t

n

,

sk¡d wynika, »e (u

n

)

∞

n=0

jest kombinacj¡ liniow¡ ci¡gów



n+j−1

j−1

λ

n
i



∞

n=0

, przy

czym 1 ≤ i ≤ s, 0 ≤ j ≤ k

i

. Poniewa»

n+j−1

j−1

jest wielomianem stopnia

j − 1

od n, wi¦c (u

n

)

∞

n=0

jest te» kombinacj¡ liniow¡ ci¡gów wypisanych w tezie

twierdzenia.

8

Drzewa binarne i liczby Catalana

4.17 Denicja. Drzewem binarnym o n wierzchoªkach nazywamy zbiór pusty
∅

, gdy n = 0, a gdy n > 0, par¦ uporz¡dkowan¡ (L, R), gdzie L i R s¡ drzewami

binarnymi, dla których suma ilo±ci wierzchoªków jest równa n − 1.

Niech c

n

oznacza ilo±¢ drzew binarnych o n wierzchoªkach. Wówczas











c

0

= 1,

c

n

=

n−1

X

j=0

c

j

c

n−1−j

, n > 0.

(12)

Liczby c

n

nazywaj¡ si¦ liczbami Catalana. Na podstawie rekurencji mo»na

policzy¢

n

0

1

2

3

4

5

6

7

8

9

10

11

12

13

. . .

c

n

1

1

2

5

14

42

132

429

1430

4862

16796

58786

208012

742900

. . .

4.18 Funkcja generuj¡ca i wzór zwarty. Niech C(t) b¦dzie funkcj¡ generu-

j¡c¡ dla ci¡gu liczb Catalana. Aby otrzyma¢ jawn¡ posta¢ funkcji generuj¡cej,

przemnó»my drugie równanie w (12) przez t

n

i posumujmy po wszystkich n ≥ 1.

Otrzymamy

∞

X

n=1

c

n

t

n

= t

∞

X

n=1





n−1

X

j=0

c

j

c

n−1−j





t

n−1

,

co daje

C(t) − c

0

= t · C

2

(t),

lub równowa»nie

t · C

2

(t) − C(t) + 1 = 0.

Szereg C(t) jest wi¦c pierwiastkiem równania kwadratowego. Stosuj¡c wzór na

pierwiastki otrzymujemy, »e C(t) jest jednym z wyra»e«

1 ±

√

1 − 4t

t.

Do wyliczenia pierwiastka stosujemy wzór (8):

√

1 − 4t

=

1 −

∞

X

i=1

1 · 3 · · · · · (2i − 3)

2

i

i!

(4t)

i

=

1 −

∞

X

i=1

2

i

2i − 2

i − 1



t

i

.

St¡d wniosek, »e do wyliczenia C(t) nale»y uwzgl¦dni¢ znak + i otrzymujemy

Wniosek. Dla ka»dego n ∈ N zachodzi

c

n

=

1

n + 1

2n

n



.

(13)

9

4.19 Liczby Catalana maj¡ wiele wa»nych interpretacji kombinatorycznych.

Niektóre z nich to:

1. Nawiasowanie iloczynów.

2. Permutacje sortowalne za pomoc¡ stosu.

3. Drogi w kwadracie n × n, które nie schodz¡ poni»ej przek¡tnej.

4. Ci¡gi (a

1

, a

2

, . . . , a

2n

)

o wyrazach ±1 takie, »e ka»da suma pocz¡tkowa

a

1

+ · · · + a

r

jest nieujemna.

Relacje rekurencji a funkcje generuj¡ce

4.20 Z logicznego punktu widzenia ci¡g i jego funkcja generuj¡ca s¡ tymi sa-

mymi obiektami. Podobnie, informacja zawarta w rekurencji dla danego ci¡gu

jest równowa»na informacji zawartej w równaniu (np. algebraicznym, ró»nicz-

kowym itd.) dla funkcji generuj¡cej ci¡gu. Mo»na powiedzie¢, »e s¡ to ró»ne

prezentacje tego samego obiektu. Oczywi±cie wybór tej czy innej prezenta-

cji jest poniek¡d spraw¡ indywidualn¡ i zale»y od naszego sposobu my±lenia

i do±wiadcze« zebranych w operowaniu ró»nymi obiektami, ale wydaje si¦, »e

funkcje generuj¡ce s¡ tym obiektem, na którym szczególnie ªatwo operowa¢, bo-

wiem mo»na wykorzysta¢ intuicje i do±wiadczenia pochodz¡ce z wielu ró»nych

dziedzin matematyki.

Powy»ej pokazali±my na przykªadach jak przeksztaªci¢ relacj¦ rekurencji w

równanie dla funkcji generuj¡cej. W przyszªo±ci poka»emy przypadki, gdy pro-

±ciej jest napisa¢ funkcj¦ generuj¡c¡ i z jej postaci wydedukowa¢ rekurencj¦.

Okazuje si¦, »e nawet je±li potramy napisa¢ jak¡± rekurencj¦ dla danego ci¡gu,

to funkcje generuj¡ce pozwalaj¡ na zast¡pienie jej prostsz¡ rekurencj¡. Roz-

wa»my nast¦puj¡cy przykªad pochodz¡cy z egzaminu w roku 2000/01.
4.21 Przykªad. Niech s

n

oznacza ilo±¢ ci¡gów binarnych dªugo±ci n, które

zawieraj¡ parzyst¡ liczb¦ jedynek i ka»de dwie jedynki rozdzielone s¡ przynaj-

mniej jednym zerem. Znale¹¢ wzór rekurencyjny dla ci¡gu s

n

i wzór zwarty dla

szeregu generuj¡cego P

∞
n=0

s

n

t

n

.

4.22 Moja propozycja rozwi¡zania.

We¹my dowolne sªowo binarne dªugo±ci n speªniaj¡ce warunki okre±lone w zada-

niu i popatrzmy na ostatnia liter¦ tego sªowa. Je±li jest to 0, to sªowo powstaªe

przez jego odci¦cie jest sªowem dªugo±ci n − 1 speªniaj¡cym warunki podane

w zadaniu. Je±li jednak ostatni¡ liter¡ jest 1, to sprawa jest bardziej skom-

plikowana: z warunków zadania wiemy, »e o ile tylko n > 1, to przed ko«cow¡

jedynk¡ musi wyst¡pi¢ 0 i sªowo powstaªe przez odci¦cie przez odci¦cie ko«cówki

01 dalej ma t¦ wªasno±¢, »e ka»de dwie jedynki rozdzielone s¡ przynajmniej jed-

nym zerem, lecz ilo±¢ jedynek w nim jest nieparzysta. St¡d naturalny pomysª

wprowadzenia pomocniczego ci¡gu (p

n

)

∞

n=0

zliczaj¡cego ci¡gi binarne dªugo±ci

10

n

, w których ka»de dwie jedynki s¡ jak uprzednio rozdzielone zerami, lecz ich

liczba jest nieparzysta. Powy»sza analiza pokazuje, »e

s

n

= s

n−1

+ p

n−2

,

a anlogiczne rozumowanie dla ci¡gu p

n

daje

p

n

= p

n−1

+ s

n−2

,

przy czym obydwa równania s¡ prawdziwe dla n ≥ 2 i uzupeªnione o warunki

pocz¡tkowe s

0

= s

1

= 1

i p

0

= 0

, p

1

= 1

jednoznacznie wyznaczaj¡ oba ci¡gi.

Poniewa» interesuje nas relacja rekurencji dla ci¡gu s

n

, mogliby±my spróbowa¢

wyrugowa¢ z powy»szych równa« ci¡g p

n

i mo»na to w tym przypadku prosto

zrobi¢ (jedna osoba przedstawiªa takie rozwi¡zanie). Wygodniej jednak posªu»y¢

si¦ funkcjami generuj¡cymi, które zagadnienie algebraizuj¡ i w konsekwencji

automatyzuj¡ rozumowanie.

Niech S(t) = P

∞
n=0

s

n

t

n

i P (t) = P

∞
n=0

p

n

t

n

. Wówczas powy»sze relacje

rekurencyjne tªumacz¡ si¦ na ukªad równa«



S(t) − s

0

− s

1

t

=

t(S(t) − s

0

) + t

2

· P (t)

P (t) − p

0

− p

1

t

=

t(P (t) − p

0

) + t

2

· S(t),

co po przeksztaªceniu i uwzgl¦dnieniu warunków pocz¡tkowych daje



(t − 1)S(t)

+

t

2

· P (t)

=

−1

t

2

· S(t)

+

(t − 1)P (t)

=

−t.

Rozwi¡zujac powy»szy ukªad wzgl¦dem S(t), otrzymujemy

S(t) =

1 − t + t

3

1 − 2t + t

2

− t

4

.

(∗)

Z postaci funkcji generuj¡cej wynika, »e iloczyn

(1 − 2t + t

2

− t

4

)S(t)

jest wielomianem stopnia 3, wi¦c dla ka»dego n ≥ 4 mamy

[t

n

](1 − 2t + t

2

− t

4

)S(t) = 0,

co daje rekurencj¦

s

n

= 2s

n−1

− s

n−2

+ s

n−4

dla n ≥ 4.

(∗∗)

Aby powy»sza rekurencja jednoznacznie wyznaczaªa ci¡g s

n

, poprzednio zna-

lezione warunki pocz¡tkowe s

0

= s

1

= 1

nale»y uzupeªni¢ warunkami s

2

= 1

,

s

3

= 2

.

4.23 Próby powi¡zania s

n

z wcze±niejszymi wyrazami tego samego ci¡gu pro-

wadz¡ tak»e do rekurencji postaci

s

n

= s

n−1

+

n−4

X

k=0

s

k

+ 1,

dla n ≥ 4,

11

(pierwszy skªadnik po prawej stronie odpowiada jak uprzednio ci¡gom zako«-

czonym na 0, suma odpowiada ci¡gom zako«czonym na 010 . . . 01, a jedynka 

ci¡gowi 10 . . . 01), a nawet

s

n

= 1 +

n−2

X

k=1

(1 +

n

X

l=k+3

s

l−k−3

)

(k i l s¡ pozycjami, na których stoj¡ odpowiednio najbardziej na lewo i najbar-

dziej na prawo poªo»one jedynki).

Czy te rekurencje stanowi¡ odpowied¹ na pytanie o rekurencj¦ dla ci¡gu s

n

?

Mniej wi¦cej w takim samym stopniu w jakim `"60 −

1
3

· 12

"jest odpowiedzi¡

na pytanie `"ile jest 7 razy 8?". W pewnych, raczej rzadkich przypadkach, taka

odpowied¹ mo»e rzuci¢ nowe ±wiatªo na zagadnienie (kopa bez trzeciej cz¦±ci

tuzina?), ale zazwyczaj oczekujemy odpowiedzi jak najbardziej bezpo±redniej.

W zadaniu miar¡ prostoty odpowiedzi byªo pytanie o s

10

: ze wzoru (∗∗) ªa-

two mo»na wyliczy¢ s

10

= 72

. Je±li kto± chciaªby porówna¢ ró»ne przytoczone

powy»ej wzory, to wystarczy oszacowa¢ zªo»ono±¢ wyliczenia s

n

na podstawie

poszczególnych wzorów.

Czy to znaczy, »e trzeba `"wpa±¢«a to `"jedynie sªuszne»ozwi¡zanie? Otó»

nie, caªa rzecz w tym, »e ka»da z powy»szych rekurencji przetªumaczona na

równanie dla funkcji generuj¡cej daje dla S(t) wyra»enie (∗), sk¡d mo»na ju»

wywnioskowa¢ (∗∗) jak uprzednio.

Co wi¦cej, do tej samej odpowiedzi prowadzi bezpo±rednie wyliczenie liczby

s

n

. Ilo±¢ ci¡gów ustalonej dªugo±ci, w których jest dokªadnie k jedynek roz-

dzielonych zerami mo»na policzy¢ nast¦puj¡co. Wyobra¹my sobie, »e mamy r

miejsc, spo±ród których wybieramy k. Na pierwszych k−1 wybranych miejscach

stawiamy ci¡g '10', na ostatnim z wybranych stawiamy '1', a wszystkie pozostaªe

miejsca uzupeªniamy zerami. Otrzymujemy ci¡g dªugo±ci r + k − 1 zawieraj¡cy

dokªadnie k jedynek rozdzielonych co najmniej jednym zerem i wszystkie takie

ci¡gi mo»emy otrzyma¢ w powy»szej procedurze na jeden sposób. Mamy wi¦c

s

n

=

∞

X

k=0

n − 2k + 1

2k



.

(Oczywi±cie pojawiaj¡ca si¦ tutaj suma jest w rzeczywisto±ci sko«czona.) Wy-

liczenie, »e

∞

X

n=0

∞

X

k=0

n − 2k + 1

2k



t

n

zadaje si¦ wzorem (∗) jest prostym ¢wiczeniem w operowaniu szeregami pot¦-

12

gowymi:

∞

X

n=0

∞

X

k=0

n − 2k + 1

2k



t

n

=

∞

X

k=0

∞

X

n=0

n − 2k + 1

2k



t

n

=

∞

X

n=0

t

n

+

∞

X

k=1

∞

X

n=4k−1

n − 2k + 1

2k



t

n

=

1

1 − t

+

∞

X

k=1

∞

X

r=0

r + 2k

2k



t

r+4k−1

=

1

1 − t

+

∞

X

k=1

t

4k−1

(1 − t)

2k+1

=

1 − t + t

3

(1 − t)

2

− t

4

4.24 Na koniec jeszcze uwaga o pochodzeniu problemu sformuªowanego w za-

daniu. Otó» nie zostaª on wymy±lony, by utrudni¢ »ycie zdaj¡cym matematyk¦

dyskretn¡, a wynika z zastosowa« praktycznych: niektóre rzeczywiste urz¡dze-

nia u»ywane do transmisji danych nie radz¡ sobie z dwoma kolejno nast¦puj¡-

cymi bezpo±rednio po sobie identycznymi sygnaªami. St¡d potrzeba rozdziele-

nia ich interwaªem nie zawieraj¡cym sygnaªu (odczytywanym jako '0'). Waru-

nek parzystej liczby jedynek jest oczywi±cie wynikiem powszechnie stosowanego

kodu kontroli parzysto±ci.

Dalsze wªasno±ci szeregów

Szereg jako granica ci¡gu wielomianów

4.25 Szereg f(t) = P

∞
i=0

a

i

t

i

mo»emy traktowa¢ jako `"granic¦¢i¡gu wielo-

mianów f

N

(t) =

P

N
i=0

a

i

t

i

, N = 0, 1, . . . . Formalizacja tej intuicji prowadzi do

nast¦puj¡cej denicji.

Denicja. Powiemy, »e ci¡g szeregów (f

n

(t))

∞
n=0

wyznacza szereg f(t) =

P

∞
i=0

a

i

t

i

, je±li dla ka»dego i ∈ N istnieje takie N

i

, »e dla ka»dego n > N

i

mamy [t

i

]f

n

(t) = a

i

. Piszemy wówczas f(t) = lim

n→∞

f

n

(t)

.

W tym sensie ka»dy szereg jest granic¡ ci¡gu wielomianów: P

∞
i=0

a

i

t

i

=

lim

N →∞

P

N
i=0

a

i

t

i

.

4.26 Niech (f

n

(t))

∞
n=0

b¦dzie takim ci¡giem szeregów, »e

lim

n→∞

ldegf

n

(t) = ∞.

(14)

Wówczas ci¡g szeregów



Q

N
n=0

(1 + f

n

(t))



∞

N =0

wyznacza szereg, który b¦dziemy

oznacza¢ symbolem

∞

Y

n=0

(1 + f

n

(t)).

(15)

13

Zauwa»my, »e warunek (14) jest warunkiem koniecznym, aby wyra»enie (15)

miaªo sens.
4.27 Traktowanie szeregu jako granicy wielomianów pozwala szybko dowodzi¢

niektórych wªasno±ci szeregów na podstawie analogicznych wªasno±ci wielomi-

nów.

Ró»niczkowanie szeregów

4.28 Na szeregach wprowadzamy w sposób czysto formalny operacj¦ ró»nicz-

kowania

d

dt

:

d

dt

∞

X

i=0

a

i

t

i

!

=

∞

X

i=1

ia

i

t

i−1

=

∞

X

i=0

(i + 1)a

i+1

t

i

.

Z wªasno±ci ró»niczkowania dla wielomianów wynika natychmiast (por. 4.27),

»e

d

dt

(f (t) + g(t))

=

d

dt

(f (t)) +

d

dt

(g(t))

d

dt

(f (t) · g(t))

=

d

dt

(f (t)) · g(t) + f (t) ·

d

dt

(g(t)).

Prawdziwa jest te» reguªa ró»niczkowania `"funkcji zªo»onej": je±li f(t) jest do-

wolnym szeregiem, a g(t) szeregiem bez wyrazu wolnego i przez h(t) oznaczymy

szereg

d

dt

f (t)

, to

d

dt

f (g(t)) = h(g(t)) ·

d

dt

g(t).

(16)

Operacje exp i ln

4.29 Szereg generuj¡cy dla ci¡gu odwrotno±ci silni jest szeregiem Tylora funkcji

wykªadniczej, st¡d b¦dziemy go oznacza¢ symbolem e

t

lub exp(t):

e

t

= exp(t) =

∞

X

n=0

1

n!

t

n

.

(17)

Podstawiaj¡c w powy»szym równaniu za t dowolny szereg f(t) bez wyrazu wol-

nego, mo»emy zdeniowa¢ funkcj¦ wykªadnicz¡ na takich szeregach:

e

f (t)

= exp(f (t)) =

∞

X

n=0

1

n!

f (t)

n

.

(18)

14

Funkcja ta zachowuje podstawow¡ wªasno±¢ rzeczywistej funkcji wykªadniczej

exp(f (t) + g(t)) = exp(f (t)) · exp(g(t)).

(19)

Bezpo±rednim rachunkiem mo»na te» sprawdzi¢, »e

d

dt

exp(t) = exp(t).

(20)

4.30 Drugim wa»nym szeregiem maj¡cym swoje ¹ródªo w szeregach Tylora jest

szereg

ln(1 + t) =

∞

X

n=1

(−1)

n+1

n

t

n

.

(21)

Stosuj¡c podstawianie, mo»emy za pomoc¡ tego szeregu zdeniowa¢ operacj¦

logarytmowania dla dowolnego szeregu o wyrazie wolnym równym 1 (lub nieco

ogólniej o niezerowym wyrazie wolnym): je±li f(t) = P

∞
i=1

a

i

t

i

, to

ln(1 + f (t)) =

∞

X

n=1

(−1)

n+1

n

(f (t))

n

.

(22)

Operacja ta tak»e zachowuje podstawowe wªasno±¢ logarytmu dla liczb rzeczy-

wistych. Je»eli f(t) i g(t) s¡ szeregami o wyrazach wolnych równych 1, to

ln(f (t)g(t)) = ln(f (t)) + ln(g(t)).

(23)

Bezpo±rednim rachunkiem mo»na sprawdzi¢, »e

d

dt

ln(1 + t) =

∞

X

n=1

(−1)

n+1

t

n−1

=

1

1 + t

.

(24)

4.31 Jak nale»aªo si¦ spodziewa¢, operacje exp i ln s¡ wzajemnie odwrotne tzn.

ln(exp(f (t)) = f (t),

exp(ln(1 + f (t)) = 1 + f (t)

dla dowolnego szeregu f(t) bez wyrazu wolnego.

15