Dans tout le problème K désigne R ou C L'ensemble des suites d'éléments de K est noté KN Une suite an n N d'éléments de K sera noté plus simplement an On note la suite constante dont tous les termes sont nuls et on rappelle que deux suites an et bn sont égales si et seulement si pour tout entier k N on a ak bk

Description

Niveau: Supérieur, Bac+5
Notations Dans tout le problème, K désigne R ou C. L'ensemble des suites d'éléments de K est noté KN. Une suite (an)n?N d'éléments de K sera noté plus simplement (an). On note (0) la suite constante dont tous les termes sont nuls et on rappelle que deux suites (an) et (bn) sont égales si et seulement si, pour tout entier k ? N on a ak = bk. Soient (an) et (bn) deux éléments de KN, on définit leur somme (an)+ (bn), leur produit (an)? (bn) et le produit d'une suite par un élément ? ? K respectivement par : (an) + (bn) = (an + bn) (an)? (bn) = (cn) où, pour tout entier n ? N : cn = n∑ k=0 akbn?k ? · (an) = (?an) On admet que ( KN,+ ) est un groupe commutatif d'élément nul (0). Pour tout p ? N, on notera Xp la suite (xn) ? KN définie par : { xp = 1 xn = 0 si n 6= p On écrira aussi X0 et X1 respectivement 1 et X. Pour tout (k, n) ? N2 tel que 0 ≤ k ≤ n, le coefficient binomial ( n k ) est égal à n! k!(n? k)! .

• ordres de multiplicité respectifs de z1


• polynôme de degré


• ?n ?


• appelée série


• sn sans point fixe


• partitions contenant le singleton


• série génératrice

Sujets

• Fonction génératrice

Informations

• Publié par: profil-meshug-2012
• Nombre de lectures: 34
• Langue: Français

Extrait

Notations

Dans tout le problÈme,KdÉsigneRouC.L’ensemble des suites d’ÉlÉments deKest N notÉK. Une suite(a n ) n∈N d’ÉlÉments deKsera notÉ plus simplement(a n ). On note (0)la suite constante dont tous les termes sont nuls et on rappelle que deux suites(a n ) et(b n )sont Égales si et seulement si, pour tout entierk∈Non aa k =b k . N Soient(a n )et(b n )deux ÉlÉments deK, on dÉfinit leur somme(a n ) + (b n ), leur produit (a n )×(b n )et le produit d’une suite par un ÉlÉmentλ∈Krespectivement par : (a n ) + (b n ) = (a n +b n ) n P (a n )×(b n ) = (c n )oÙ, pour tout entiern∈N:c n =a k b n−k k=0 λ∙(a n ) = (λa n )   N On admet queK,+est un groupe commutatif d’ÉlÉment nul(0). pN Pour toutp∈N, on noteraXla suite(x n )∈KdÉfinie par : ( x p = 1 x n = 0sin6=p

0 1 On Écrira aussiXetXrespectivement1etX.   n n! 2 Pour tout(k, n)∈Ntel que0≤k≤n,le coefficient binomial est Égal À. k k!(n−k)!

Partie I : sèrie gènèratrice d’une suite(a n )

1)Propriètès algèbriques   N 1.a) Montrer queK,+,×est un anneau commutatif dont on prÉcisera l’ÉlÉment neutre.   N 1.b) Montrer queK,+,×est intÈgre. (Indication :si(a n )est un ÉlÉment non nul de N K, on pourra considÉrer le plus petit entierktel quea k 6= 0.) N N 1.c) Montrer qu’un ÉlÉment(a n )deKest inversible dansKsi et seulement sia 0 6= 0.   N 1.d) Montrer queK,+,∙est unK-espace vectoriel.

N Les rÉsultats prÉcÉdents montrent que toute suite(a n )∈Kpeut s’Écrire formellement X P P n n n sous la formea n X. Lorsqu’on noteA(X) =a n XouA=a n X, alors n>0n>0 n>0 A(X)ouAsera appelÉe sÉrie gÉnÉratrice de la suite(a n ). On remarque que par dÉfinition p q p+q2 du produit des suites on aX×X=Xpour tout(p, q)∈N.D’autre part, siAest k une sÉrie gÉnÉratrice, pour tout entierk>2,AdÉsigne le produitA×A× ∙ ∙ ∙ ×A. | {z } k facteurs On remarquera aussi que s’il existe un entierptel quea p 6= 0et tel que pour tout entier n > pon aa n = 0alors la sÉrie gÉnÉratrice de la suite(a n )n’est autre qu’un polynÔme p P n de degrÉpqu’on noteraa n X. n=0 P n D’aprÈs la question1.c)ci-dessus, la sÉrie gÉnÉratricea n Xest inversible si et seule- n>0 ment sia 0 6= 0. Dans toute la suite, si la sÉrie gÉnÉratriceA(X)est inversible, on Écrira 1 son inverse sous la forme . Plus gÉnÉralement si la sÉrie gÉnÉratriceA(X)est A(X)

1

1 inversible et siB(X)est une sÉrie gÉnÉratrice quelconque, le produitB(X)×sera A(X) B(X) notÉ.Si de plusB(X)etA(X)sont des sÉries gÉnÉratrices sous la forme de poly- A(X) B(X) nÔmes alors peut tre assimilÉe À une fraction rationnelle surKet on admet que A(X) B(X) les techniques de dÉcomposition en ÉlÉments simples surKrestent valables pour. A(X) 2)Èlèments inversibles P n 2.a) Montrer que la sÉrie gÉnÉratrice inversibleXa pour inverse1−X, c’est-À-dire n≥0 que : X 1 n =X 1−X n≥0 2.b) Soita∈K− {0}, montrer que : X 1 n n =a X 1−aX n>0

2.c) Soienta∈K− {0},b∈K− {0}aveca6=b, montrer que :     1a1b1 = + (1−aX)×(1−bX)a−b1−aX b−a1−bX

3)L’opèrateur de dèrivation N N L’opÉrateur de dÉrivation,D:K→Kest dÉfini par : +∞ X X X n n−1n D:A=a n X7→D(A) =na n X= (n+ 1)a n+1 X n>0n>1n>0

N 3.a) Montrer queDest un endomorphisme duK-espace vectorielK. SoientAetBdeux sÉries gÉnÉratrices. Montrer que : 3.b)D(A×B) =D(A)×B+A×D(B) p q2 (on pourra commencer par traiter le cas oÙA=XetB=XoÙ(p, q)∈N). 3.c) SiBest inversible   A D(A)×B−A×D(B) D= 2 B B 4)Quelques exemples 4.a) Montrer que la suite(a n ) n∈N dont la sÉrie gÉnÉratrice est : 1 A(X) = 2 (1−X) est dÉfinie pour tout entiernpara n =n+ 1. ∗ 4.b) Monter que, pour toutp∈N, la suite(a p,n ) n∈N dont la sÉrie gÉnÉratrice est 1 A p (X) = p (1−X) est dÉfinie pour tout entiernpar :   n+p−1 a p,n = n

2

A(X) 4.c) SoitA(X)la sÉrie gÉnÉratrice d’une suite(a n ) n∈N est la sÉrie. Montrer que 1−X gÉnÉratrice de la suite(b n ) n∈N dÉfinie par : n X b n =a k k=0 ∗ 4.d) En dÉduire que, pour tout entierp∈Non a : n    X k+p−1n+p = k n k=0

Partie II : sèries gènèratrices et suites rècurrentes

1) On considÈre la suite(a n ) n∈N dÉfinie par : ( a 0 = 0 ∀n∈N, a n+1 = 2a n +n On se propose de dÉterminer la formule explicite dea n en fonction den. On noteA(X) la sÉrie gÉnÉratrice de la suite(a n ) n∈N . 1.a) Montrer que : X 2n A(X) = 2X×A(X) +X×(n+ 1)X n>0 1.b) DÉterminer la dÉcomposition en ÉlÉments simples surKde la fraction rationnelle 2 X . 2 (1−X)×(1−2X) 1.c) En dÉduire l’expression dea n en fonction den. 2) On considÈre la suite de Fibonacci(F n ) n∈N dÉfinie par :   F 0 = 0  F 1 = 1   ∀n∈N, F n+2 =F n+1 +F n et on noteF(X)la sÉrie gÉnÉratrice de la suite(F n ) n∈N . 2.a) Montrer que :   1 1 1 F(X) = √ − 5 1−α 1 X1−α 2 X oÙ √ √ 1 + 5 1−5 α 1 =etα 2 = 2 2 2.b) En dÉduire l’expression deF n en fonction den. 3) Suites rÉcurrentes linÉaires d’ordrek(k≥1). k Soit(a 1 , ..., a k )∈C, aveca k 6= 0. On considÈre l’ensembleUdes suites complexes(u n ) k dÉfinies par la donnÉe de(u 0 , ..., u k−1 )∈Cet par la relation de rÉcurrence ∀n≥k, u n =a 1 u n−1 +a 2 u n−2 +...+a k u n−k . (On utilisera, sans le dÉmontrer, le fait que(U,+,∙)est unC-espace vectoriel). Soit(u n )∈ U. On noteSla sÉrie gÉnÉratrice de(u n ), et(E)l’Équation caractÉristique de(u n ): k k−1k−2 z=a 1 z+a 2 z+...+a k (E).

3

k 3.a) Montrer queφ: (u n )∈ U 7→(u 0 , u 1 , ..., u k−1 )est un isomorphisme deUdansC. k 3.b) On poseQ(X) = 1−a 1 X−...−a k XetP(X) =Q(X)×S(X). Montrer queP(X) est un polynÔme de degrÉ au plusk−1, À coefficients dansC. 3.c) On notez 1 ,∙ ∙ ∙, z p les racines dansC, de l’Équation(E)etα 1 ,∙ ∙ ∙, α p les ordres de multiplicitÉ respectifs dez 1 ,∙ ∙ ∙, z p . Montrer qu’il existe des nombres complexesb i,j ,1≤i≤p,1≤j≤α i tels que :   p α i X X P(X) b i,j   =. j Q(X) (X−1/z i ) i=1j=1

3.d) Montrer alors qu’il existe des polynÔmesR 1 , ..., R p tels que pour toutn p X n )zoÙ∀i, deg(R)< α . u n =R i (n ii i i=1 p X n 3.e) On noteVl’ensemble des suites(v n )dont le terme gÉnÉral s’Écritv n =P i (n)z i i=1 oÙ pour touti∈ {1,2∙ ∙ ∙, p},P i est un polynÔme tel quedeg(P i )< α i . DÉmontrer que(V,+,∙)est unC-espace vectoriel dont la dimension vÉrifie l’inÉgalitÉ dimV ≤ket dÉduire queV=U.

Partie III : Nombre de partitions d’un ensemble

Soientk>1un entier etSun ensemble non vide, on dit que{S 1 , S 2 , . . . , S k }est une partition deSenkclasses si :  ∀i∈ {1,∙ ∙ ∙, k}, S i 6=∅   2 ∀(i, j)∈ {1,∙ ∙ ∙, k}, S i ∩S j =∅sii6=j k S   S i =S i=1   n Pour tout entiern>1et tout entierk∈ {1,∙ ∙ ∙, n}on note le nombre de partitions k d’un ensemble de cardinalnenkclasses. On pose par convention :   n pour tout entiern>1:= 0 0   n pour tout entierk > n:= 0 k   0 = 1 0 1) Donner toutes les partitions de l’ensembleS={1,2,3,4}en 2 classes.     4n Cette question montre que= 7. On se propose dans ce qui suit de calculer 2k en fonction denetk. 2) Montrer que, pour tout entiern>1on a :       n n−1n−1 = +k k k−1k

(On fixera un ÉlÉments∈Set on considÈrera les partitions contenant le singleton{s} et les partitions qui ne le contiennent pas).

4

3) On considÈre la sÉrie gÉnÉratrice   X n n A k (X) =X k n>0

3.a) Montrer que pour tout entierk>1, on a :

A k (X) =X×A k−1 (X) +kX×A k (X)

3.b) En dÉduire que, pour tout entierk>1, on a :

k X A k (X) = k Q (1−mX) m=1

3.c) Montrer que, pour tout entierk>1, on a :

k X 1α r = k Q 1−rX r=1 (1−mX) m=1

k−1 r k−r oÙ, pour toutr∈ {1,∙ ∙ ∙, k},α r = (−1) (r−1)!(k−r)! 3.d) En dÉduire que, pour tout entiern>k:   k n X r n k−r = (−1) k r !(k−r)! r=1

4) Application : nombre de surjections On considÈre un ensembleEde cardinalnet un ensembleFde cardinalpoÙnetp sont deux entiers strictement positifs. On se propose de calculer le nombreS(n, p)de surjections deEsurF. 4.a) Que vautS(n, p)lorsquep > n? 4.b) Que vautS(n, n)? 4.c) On suppose maintenant quep∈ {1,∙ ∙ ∙, n}.Montrer que :   n S(n, p) =p! p

Partie IV : Nombre de dèrangements

∗ Soitn∈N. On noteS n l’ensemble des permutations de{1, ..., n}. Un dÉrangement de l’ensemble{1, ..., n}est une permutationσ∈S n sans point fixe c’est-À- dire telle que pour tout entieri∈ {1,2, . . . , n},σ(i)6=i. On noted n le nombre de dÉrangements de l’ensemble{1, ..., n}. d n On posed 0 = 1et pour tout entier natureln,p n =. n! 1) Calculerd 1 , d 2 etd 3 . 2) Pour0≤k≤n, on noteB k l’ensemble des permutations deS n ayant exactementk points fixes.

5

  n 2.a) Montrer que le cardinal deB k vÉrifie l’ÉgalitÉ :Card (B k ) =d n−k et en dÉduire k que : n   X n d k =n! k k=0 2.b) SoitPla sÉrie gÉnÉratrice de la suite(p n ). Montrer que X X 1 n n E(X)×P(X) =X ,oÙE(X) =X . n! n>0 n≥0

2.c) DÉterminer la sÉrie gÉnÉratrice inverse deE(X). 2.d) En dÉduire que n X k (−1) d n =n!. k! k=0

Partie V : Nombres de Catalan

1)Chemins de Dyck #» #» Le plan est rapportÉ À un repÈre(, O, ı ). Pour tout entiern≥1,on appelle chemin de Dyck de longueur2n, toute suite(s 0 , s 1 , . . . , s 2n )de points du plan dont les coordonnÉes sont des entiers positifs tels ques 0 = (0,0),s 2n = (2n,0)et, tels que, pour tout entierk∈ {0,1,∙ ∙ ∙,2n−1},s k+1 est l’image des k par la translation #» #» #» #» de vecteurı+ou de vecteurı−. Voici un chemin de Dyck de longueur 16.

4

3

2

1

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

On notec n le nombre de chemins de Dyck de longueur2n. Les nombresc n sont appelÉsnombres de Catalan. Pour tout chemin de DyckC= (s 0 , s 1 , . . . , s 2n )de longueur2non notek(C)le plus petit entier tel ques k(C) soit d’ordonnÉe nulle et d’abscisse non nulle. 1.a) Justifier quek(C)est un entier pair. 1.b) Montrer que le nombre de chemins de DyckCde longueur2ntel quek(C) = 2n est Égal Àc n−1 . 1.c) Montrer que le nombre de chemins de DyckCde longueur2ntel quek(C) = 2p avecp∈ {1,∙ ∙ ∙, n−1}est Égal Àc p−1 c n−p .(Par convention, on posec 0 = 1). 1.d) En dÉduire que la suite(c n )vÉrifie la relation de rÉcurrence : n X c n =c j−1 c n−j j=1

6