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
7
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
7
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Publié par
Langue
Français
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)! .
Voir
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
Publié par
Langue
Français
Notations
Dans tout le problÈme,KdÉsigneRouC.L’ensemble des suites d’ÉlÉments deKest N notÉK. Une suite(an)n∈Nd’ÉlÉments deKsera 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 entierk∈Non aak=bk. N Soient(an)et(bn)deux ÉlÉments deK, on dÉfinit leur somme(an) + (bn), leur produit (an)×(bn)et le produit d’une suite par un ÉlÉmentλ∈Krespectivement par : (an) + (bn) = (an+bn) n P (an)×(bn) = (cn)oÙ, pour tout entiern∈N:cn=akbn−k k=0 λ∙(an) = (λan) N On admet queK,+est un groupe commutatif d’ÉlÉment nul(0). pN Pour toutp∈N, on noteraXla suite(xn)∈KdÉfinie par : ( xp= 1 xn= 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(an)
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(an)est un ÉlÉment non nul de N K, on pourra considÉrer le plus petit entierktel queak6= 0.) N N 1.c) Montrer qu’un ÉlÉment(an)deKest inversible dansKsi et seulement sia06= 0. N 1.d) Montrer queK,+,∙est unK-espace vectoriel.
N Les rÉsultats prÉcÉdents montrent que toute suite(an)∈Kpeut s’Écrire formellement X P P n n n sous la formeanX. Lorsqu’on noteA(X) =anXouA=anX, alors n>0n>0 n>0 A(X)ouAsera appelÉe sÉrie gÉnÉratrice de la suite(an). 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 } kfacteurs On remarquera aussi que s’il existe un entierptel queap6= 0et tel que pour tout entier n > pon aan= 0alors la sÉrie gÉnÉratrice de la suite(an)n’est autre qu’un polynÔme p P n de degrÉpqu’on noteraanX. n=0 P n D’aprÈs la question1.c)ci-dessus, la sÉrie gÉnÉratriceanXest inversible si et seule-n>0 ment sia06= 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=anX7→D(A) =nanX= (n+ 1)an+1X 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(an)n∈Ndont la sÉrie gÉnÉratrice est : 1 A(X) = 2 (1−X) est dÉfinie pour tout entiernparan=n+ 1. ∗ 4.b) Monter que, pour toutp∈N, la suite(ap,n)n∈Ndont la sÉrie gÉnÉratrice est 1 Ap(X) = p (1−X) est dÉfinie pour tout entiernpar : n+p−1 ap,n= n
2
A(X) 4.c) SoitA(X)la sÉrie gÉnÉratrice d’une suite(an)n∈Nest la sÉrie. Montrer que 1−X gÉnÉratrice de la suite(bn)n∈NdÉfinie par : n X bn=ak 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(an)n∈NdÉfinie par : ( a0= 0 ∀n∈N, an+1= 2an+n On se propose de dÉterminer la formule explicite deanen fonction den. On noteA(X) la sÉrie gÉnÉratrice de la suite(an)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 deanen fonction den. 2) On considÈre la suite de Fibonacci(Fn)n∈NdÉfinie par : F0= 0 F1= 1 ∀n∈N, Fn+2=Fn+1+Fn et on noteF(X)la sÉrie gÉnÉratrice de la suite(Fn)n∈N. 2.a) Montrer que : 1 1 1 F(X) =√ − 5 1−α1X1−α2X oÙ √ √ 1 + 5 1−5 α1=etα2= 2 2 2.b) En dÉduire l’expression deFnen fonction den. 3) Suites rÉcurrentes linÉaires d’ordrek(k≥1). k Soit(a1, ..., ak)∈C, avecak6= 0. On considÈre l’ensembleUdes suites complexes(un) k dÉfinies par la donnÉe de(u0, ..., uk−1)∈Cet par la relation de rÉcurrence ∀n≥k, un=a1un−1+a2un−2+...+akun−k. (On utilisera, sans le dÉmontrer, le fait que(U,+,∙)est unC-espace vectoriel). Soit(un)∈ U. On noteSla sÉrie gÉnÉratrice de(un), et(E)l’Équation caractÉristique de(un): k k−1k−2 z=a1z+a2z+...+ak(E).
3
k 3.a) Montrer queφ: (un)∈ U 7→(u0, u1, ..., uk−1)est un isomorphisme deUdansC. k 3.b) On poseQ(X) = 1−a1X−...−akXetP(X) =Q(X)×S(X). Montrer queP(X) est un polynÔme de degrÉ au plusk−1, À coefficients dansC. 3.c) On notez1,∙ ∙ ∙, zples racines dansC, de l’Équation(E)etα1,∙ ∙ ∙, αples ordres de multiplicitÉ respectifs dez1,∙ ∙ ∙, zp. Montrer qu’il existe des nombres complexesbi,j,1≤i≤p,1≤j≤αitels que : p αi X X P(X)bi,j =. j Q(X) (X−1/zi) i=1j=1
3.d) Montrer alors qu’il existe des polynÔmesR1, ..., Rptels que pour toutn p X n )zoÙ∀i, deg(R)< α . un=Ri(nii i i=1 p X n 3.e) On noteVl’ensemble des suites(vn)dont le terme gÉnÉral s’Écritvn=Pi(n)zi i=1 oÙ pour touti∈ {1,2∙ ∙ ∙, p},Piest un polynÔme tel quedeg(Pi)< α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{S1, S2, . . . , Sk}est une partition deSenkclasses si : ∀i∈ {1,∙ ∙ ∙, k}, Si6=∅ 2 ∀(i, j)∈ {1,∙ ∙ ∙, k}, Si∩Sj=∅sii6=j k S Si=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 Ak(X) =X k n>0
3.a) Montrer que pour tout entierk>1, on a :
Ak(X) =X×Ak−1(X) +kX×Ak(X)
3.b) En dÉduire que, pour tout entierk>1, on a :
k X Ak(X) = k Q (1−mX) m=1
3.c) Montrer que, pour tout entierk>1, on a :
k X 1αr = k Q1−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 nk−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 noteSnl’ensemble des permutations de{1, ..., n}. Un dÉrangement de l’ensemble{1, ..., n}est une permutationσ∈Snsans point fixe c’est-À-dire telle que pour tout entieri∈ {1,2, . . . , n},σ(i)6=i. On notednle nombre de dÉrangements de l’ensemble{1, ..., n}. dn On posed0= 1et pour tout entier natureln,pn=. n! 1) Calculerd1, d2etd3. 2) Pour0≤k≤n, on noteBkl’ensemble des permutations deSnayant exactementk points fixes.
5
n 2.a) Montrer que le cardinal deBkvÉrifie l’ÉgalitÉ :Card (Bk) =dn−ket en dÉduire k que : n X n dk=n! k k=0 2.b) SoitPla sÉrie gÉnÉratrice de la suite(pn). Montrer que X X 1 n n E(X)×P(X) =X ,oÙE(X) =X . n! n>0n≥0
2.c) DÉterminer la sÉrie gÉnÉratrice inverse deE(X). 2.d) En dÉduire que n X k (−1) dn=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(s0, s1, . . . , s2n)de points du plan dont les coordonnÉes sont des entiers positifs tels ques0= (0,0),s2n= (2n,0)et, tels que, pour tout entierk∈ {0,1,∙ ∙ ∙,2n−1},sk+1est l’image deskpar 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 notecnle nombre de chemins de Dyck de longueur2n. Les nombrescnsont appelÉsnombres de Catalan. Pour tout chemin de DyckC= (s0, s1, . . . , s2n)de longueur2non notek(C)le plus petit entier tel quesk(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 Àcn−1. 1.c) Montrer que le nombre de chemins de DyckCde longueur2ntel quek(C) = 2p avecp∈ {1,∙ ∙ ∙, n−1}est Égal Àcp−1cn−p.(Par convention, on posec0= 1). 1.d) En dÉduire que la suite(cn)vÉrifie la relation de rÉcurrence : n X cn=cj−1cn−j j=1
6
