Matematyka dyskretna , studia zaoczne-semestr 2
zestaw 3
Funkcja tworzÄ…ca:
"
Danemu ciągowi a przyporządkowujemy szereg formalny Aśą xźą= an xn , którego wyznaczamy sumę.
n
"
n=0
" "
Dla szeregów Aśą xźą= an xn B śą xźą= bn xn definiujemy:
" "
n=0 n=0
" " "
Ä… operacjÄ™ dodawania:
Aśą xźąƒÄ…B śą xźą= an xnƒÄ… bn xn= śąanƒÄ…bnźą xn
" " "
n=0 n=0 n=0
"
ą operację mnożenia przez liczbę (rzeczywistą lub zespoloną):
pÅ"Aśą xźą= pÅ"an xn
"
n=0
" " "
ą operację mnożenia (tzw. Iloczyn Cauch'ego): gdzie
Aśą xźąÅ"B śą xźą= an xnÅ" bn xn= cn xn,
" " "
n=0 n=0 n=0
n
cn= ai bn-i .
"
i=0
"
Aśąn źąśą0źą
Z funkcji tworzącej Aśą xźą= an xn można otrzymać wyrazy szeregu an= dla n=0, 1,2.....A(n)(0) oznacza n-tą
"
n!
n =0
pochodnÄ… funkcji A w punkcie x=0.
Z funkcji tworzącej można również wyznaczać postać jawną ciągu rozkładając ją na ułamki proste.
1. Wyznacz funkcje tworzące podanych ciągów:
a) a = n , n e" 0
n
a
ëÅ‚ öÅ‚
an = ìÅ‚ , n e" 0
b)
ìÅ‚n÷Å‚
÷Å‚
íÅ‚ Å‚Å‚
c)
an = an , n e" 0
a
ëÅ‚ öÅ‚
d) an = nìÅ‚ , n e" 0
ìÅ‚n÷Å‚
÷Å‚
íÅ‚ Å‚Å‚
a0 = 2
Å„Å‚
ôÅ‚a = 5
2. Dla danego ciÄ…gu rekurencyjnego
òÅ‚
1
ôÅ‚a = 5an+1 - 6an n >1
ół n+2
a) Wyznacz funkcjÄ™ tworzÄ…cÄ… ciÄ…gu.
a0
b) Sprawdz
czy funkcja tworzÄ…ca jest prawdziwa dla i a1 .
c) Znajdz
postać jawną ciągu na podstawie funkcji tworzącej.
3. Wyznacz funkcje tworzące dla ciągów:
a0 = 1
Å„Å‚
1 dla n = 0,...,N
Å„Å‚
ôÅ‚a = 2
a) b) a =
òÅ‚ òÅ‚0 dla n > N
1 n
ół
ôÅ‚a = n +1
ół n
4. a) Wyznacz funkcjÄ™ tworzÄ…cÄ… ciÄ…gu a = nÄ…n .
n
b) Wyznacz funkcjÄ™ tworzÄ…cÄ… ciÄ…gu
cn = n2n
"
n
bn , g(x) = x
5. Dana jest funkcja tworzÄ…ca ciÄ…gu .
"b
n
n= 0
a) Policz funkcję tworzącą dla ciągu o wyrazie ogólnym nbn .
6. Wyznacz funkcje tworzące podanych ciągów i sprawdz
czy funkcje tworzÄ…ce sÄ… prawdziwe dla poczÄ…tkowych
wyrazów ciągów.
a = 1 Å„Å‚b = 1
Å„Å‚
0 0
ôÅ‚a = 2 ôÅ‚
a) b) = 2
òÅ‚ òÅ‚b1
1
ôÅ‚a = a - a + n + 2 , n > 1
ôÅ‚b = bn + bn + 2n , n > 1
ół n + 2 n +1 n
ół n+ 2 +1
Cn
7. **Podaj zależność rekurencyjną na liczbę wszystkich drzew binarnych o n wierzchołkach. Za pomocą funkcji
tworzącej wyznacz wzór jawny dla tego ciągu.
(W. Lipski- Kombinatoryka dla programistów )