Functii generatoare
5
Funcţii generatoare În matematică o funcţie generatoare este o serie de puteri = G ( ∑ ∞ = = 0 ) ( n n n x a x f x a n , ) ai cărei coeficienţi codifică informaţia despre un şir care este indexat după numerele naturale. n a Sunt numeroase tipuri de funcţii generatoare cum ar fi: funcţia generatoare uzuală, funcţia generatoare exponenţială, seriile Lambert, seriile Bell şi seriile Dirichlet. Funcţiile generatoare uzuale pot fi generalizate la secvenţe cu indecşi multipli. Un exemplu de funcţie generatoare uzuală a unei secvenţe este: n m a , G ( ) = . y x a n m , ; , ∑ ∞ =0 , , n m n m n m y x a Funcţia generatoare exponenţială: EG ( ) = x a n , ∑ ∞ =0 ! n n n n x a . Funcţia generatoare a lui Poisson: PG ( x a ) = n , ∑ ∞ = − 0 ! n n x n n x e a . Seriile Lambert: LG ( ) = x a n , ∑ ∞ = − 1 1 n n n n x x a . De observat că în seriile Lambert indexarea începe de la 1, nu de la 0. Seriile Bell pentru o funcţie aritmetică f(n) şi un număr prim p este: . ∑ ∞ = = 0 ) ( ) ( n n n p x p f x f Seriile Dirichlet: DG ( s) = , n a ∑ ∞ =1 n s n n a . Pentru un şir funcţia generatoare este: 2 n a n = G ( x n ) = , 2 ∑ ∞ = − + = 0 3 2 ) 1 ( ) 1 ( n n x x x x n ; EG ( x n , ) = 2 ∑ ∞ = + = 0 2 ) 1 ( ! n x n e x x n x n ; x p x p x f n n n p 2 0 2 1 1 ) ( − = = ∑ ∞ = etc. Alte exemple: 1
-
Upload
cilibiu-ionut-alin -
Category
Documents
-
view
223 -
download
5
description
Functii generatoare
Transcript of Functii generatoare
-
Funcii generatoare n matematic o funcie generatoare este o serie de puteri
= G ( =
=0
)(n
nn xaxf xan , )
ai crei coeficieni codific informaia despre un ir care este indexat dup numerele naturale.
na
Sunt numeroase tipuri de funcii generatoare cum ar fi: funcia generatoare uzual, funcia generatoare exponenial, seriile Lambert, seriile Bell i seriile Dirichlet. Funciile generatoare uzuale pot fi generalizate la secvene cu indeci multipli. Un exemplu de funcie generatoare uzual a unei secvene este: nma ,
G ( ) = . yxa nm ,;, =0,
,nm
nmnm yxa
Funcia generatoare exponenial:
EG ( ) = xan , =0 !n
n
n nxa .
Funcia generatoare a lui Poisson:
PG ( xa ) = n , =
0 !n
nx
n nxea .
Seriile Lambert:
LG ( ) =xan , = 1 1n n
n
n xxa .
De observat c n seriile Lambert indexarea ncepe de la 1, nu de la 0. Seriile Bell pentru o funcie aritmetic f(n) i un numr prim p este:
. =
=0
)()(n
nnp xpfxf
Seriile Dirichlet:
DG ( s) =,na =1n
sn
na
.
Pentru un ir funcia generatoare este: 2nan = G ( xn ) = ,2
= +=
03
2
)1()1(
n
n
xxxxn ;
EG ( xn , ) = 2 =
+=0
2 )1(!n
xn
exxnxn ;
xp
xpxfn
nnp 2
0
2
11)( ==
= etc.
Alte exemple:
1
DobreText BoxRevista MateInfo.Ro ISSN 2065 - 6432 noiembrie 2009
-
Funciile generatoare pot fi create prin extinderea unor funcii generatoare simple. De exemplu se ncepe cu
G (1, x) = = =0 1
1n
n
xx
i nlocuind x cu 2x obinem:
G (1, 2x) = ),2()2()2()2(121
1 2 xGxxxx
nn =+++++= . Operaii cu funcii generatoare: Funciile generatoare sunt una dintre cele mai surprinztoare i mai folositoare invenii n Matematica Discret.
1. (1, 0, 1, 0, 1, 0, ...) 2642
111x
xxx =++++ . nmulind funcia generatoare cu 2 obinem:
++++=642
2 222212 xxxx
care genereaz irul (2, 0, 2, 0, 2, 0, ...) Dac , )(),,,( 210 xFfff atunci )(),,,( 210 xFccfcfcf . Ideea: +++ 2210210 ),,,( xcfxcfcfcfcfcf )( 2210 +++= xfxffc )(xFc = . 2. Adunarea: A aduna dou funcii generatoare nseamn a aduna dou iruri termen cu termen. De exemplu:
(1, 1, 1, 1, 1, 1, ...)x 1
1
+ (1,-1,1,-1,1,-1, ...)x+ 1
1
________________________________
(2, 0, 2, 0, 2, 0, ...)xx ++ 1
11
1 .
Am gsit dou expresii diferite, ambele genernd irul (2, 0, 2, 0, 2, 0, ...). Ele sunt, bineneles, egale:
2
-
212
)1)(1()1()1(
11
11
xxxxx
xx =+++=++ .
Dac i )(),,,( 210 xFfff )(),,,( 210 xGggg atunci )()(),,,( 221100 xGxFgfgfgf ++++ . Ideea:
=
++++0
221100 )(),,,(n
nnn xgfgfgfgf
+
= =
= 00 nn
nn
nn xgxf
)()( xGxF += . 3. Derivarea:
Exemplu:
=+++++ xdx
dxxxxdxd
11)1( 432
232
)1(14321x
xxx =++++
(1, 2, 3, 4, ...) 2)1(1x .
Dac )(),,,,( 3210 xFffff atunci )('),3,2,( 321 xFfff . Ideea: +++ 2321321 32),3,2,( xfxfffff )( 33
2210 ++++= xfxfxffdx
d
)(xFdxd= .
4. Produsul: Dac i )(),,,( 210 xAaaa )(),,,( 210 xBbbb atunci )()(),,,( 210 xBxAccc , unde 022110: babababac nnnnn ++++= . Pentru a nelege aceast regul vom face:
=
==0
)()(:)(n
nn xcxBxAxC
Putem efectua produsul )()( xBxA utiliznd un tabel:
3
-
. . . 00 xb1
1xb2
2 xb3
3 xb
0
0 xa 1
1xa 2
2 xa 3
3 xa . . .
0
00 xba 1
10 xba2
20 xba3
30 xba1
01 xba . . . 2
11 xba3
21 xba2
02 xba . . . 3
12 xba3
03 xba . . . . . .
Se observ c toi termenii care conin aceeai putere a lui x se gsesc pe diagonal. Lund aceti termeni mpreun gsim coeficientul lui n produs, i anume, este suma tuturor termenilor de pe a (n + 1) a diagonal:
nx
022110 babababa nnnn ++++ Pentru irul lui Fibonacci funcia generatoare este:
=
++++=== 0432
2 321)(
n
nn xxxxxx
xxfxf Funcia generatoare pentru este xf i pentru este . Din relaia de recuren se observ c seria de puteri xf + se potrivete cu f cu excepia primilor doi coeficieni. innd seama de aceasta se gsete c:
1nf 2nf fx2
fx 2
f = xf + + x. fx 2
Rezolvnd aceast ecuaie pentru f rezult c 21 xxxf = .
O alt form pentru funcia generatoare pentru numerele lui Fibonacci: , unde )1)(1(1 21
2 xaxaxx =)51(
21
1 +=a i )51(21
2 =a . Apoi gsim i care ndeplinesc condiia: 1A 2A
xa
Axa
Axx
x2
2
1
12 111 += i se afl 5
11
211 == aaA i
511
212 =
=aa
A .
nlocuind obinem:
= xaxaxxx
212 1
11
15
11
, unde
+++=22
111
11
1 xaxaxa
4
-
+++=22
222
11
1 xaxaxa
=
= x)( xaxaF 21 11
11
51
( ))1()1(5
1 2222
2211 ++++++ xaxaxaxa , =
prin urmare
+==
nn
naaf 5151121 .
nn
2255
Aceast formul pare complicat n schimb este foarte util.
. V. Tma, I. Tofan, V. Leoreanu Curs de aritmetic, Ed. Univ. Iai, 2001.
. http://theory.csail.mit.edu/classes/6.042/spring06/ln10.pdf
coala cu clasele I-VIII Bogata Comuna Baia, judeul Suceava
Bibliografie:
1
2
Prof. Alexandru Elena-Marcela
5
