Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Corrigé 2016 Centrale TSI Math I 1/13 I Généralités sur les nombres de Stirling

Corrigé 2016 Centrale TSI Math I 1/13 I Généralités sur les nombres de Stirling I.A. Premières propriétés des nombres de Stirling I.A.1. a) La seule décomposition de 3 en somme de deux entiers non nuls est 3 = 1 + 2. Ainsi, si E est de cardinal 3, toute partition de E en deux, comporte deux ensembles de cardinal respectif 1 et 2. Pour l’ensemble de cardinal 1, il existe 3 1 = 3 possibilités, l’ensemble de cardinal 2 est entièrement déterminé comme le complémentaire du premier dans E. On en déduit S3,2 = 3 b) La seule partition de E en une partie est {E}. Sn,1 = 1 ∀n ∈N∗ Il n’y a qu’une façon de faire une partition d’un ensemble de cardinal n en n sous-ensembles non vides : chaque sous-ensemble est un singleton (de cardinal 1) ; l’ordre de ces singletons n’ayant pas d’incidence, on a Sn,n = 1 ∀n ∈N∗ I.A.2. a) i. La seule partition de E en deux parties, dont l’une est le singleton {4} est : {{1, 2, 3} , {4}} a) ii. Les partitions de E en deux, qui ne contiennent pas le singleton {4}, sont : {{1, 4} , {2, 3}} {{2, 4} , {1, 3}} {{3, 4} , {1, 2}} {{1} , {2, 3, 4}} {{2} , {1, 3, 4}} {{3} , {1, 2, 4}} a) iii. Considérons une partition en deux parties de E. Soit elle contient le singleton {4}, soit elle ne le contient pas. Dénombrons séparément celles qui contiennent le singleton {4} et les autres. Si elle contient comme partie le singleton {4}, l’autre partie est nécessairement une partition en un seul élément de E −{4}. Le nombre de partitions de E en deux parties dont l’une est le singleton {4} est donc S3,1 Si elle ne contient pas le singleton {4}, on peut l’interpréter comme une partition en deux parties de E −{4} à laquelle l’élément 4 a été ajouté dans l’une des deux parties. Réciproquement, chaque partition de E −{4} en deux parties, fournit ainsi deux partitions de E en deux parties, qui sont des partitions non composées du singleton {4}. Ainsi, le nombre de partitions de E en deux parties ne comportant pas le singleton {4} est le double du nombre de partitions de E −{4} en deux parties, soit 2S3,2. En résumé, on a montré S4,2 = S3,1 + 2S3,2 ce qui est bien un cas particulier de Sn,k = Sn−1,k−1 + kSn−1,k L. Pharamond Lycée Chaptal Corrigé 2016 Centrale TSI Math I 2/13 b) i. Les partitions de E en k parties dont l’une est {xn} sont en bijection avec les partitions de E −{xn} en k −1 parties. Elles ont donc même cardinal Le nombre de partitions de E en k parties dont l’une est {xn} est Sn−1,k−1 b) ii. De toute partition de E −{xn} en k parties, on peut construire k partitions distinctes de E en k parties, il suﬃt d’ajouter xn à l’une des k parties. On construit ainsi toutes les partitions de E en k parties qui ne comportent pas le singleton {xn} Le nombre de partitions de E en k parties dont aucune n’est {xn} est kSn−1,k b) iii. Soit une partition de E en k parties contient le singleton {xn}, soit elle ne le contient pas. Le nombre de partitions de E en k parties est donc la somme du nombre de partitions de E en k parties qui contiennent {xn} et du nombre de partitions de E en k parties qui ne contiennent pas {xn} : Sn,k = Sn−1,k−1 + kSn−1,k ∀n ≥2 , ∀k ∈{1, . . . , n −1} I.A.3. Soit Pn la propriété Sn,n−1 = n(n−1) 2 pour n ≥2. Démontrons la par récurrence. Pour n = 2, la propriété aﬃrme S2,1 = 1, ce qui est cohérent avec le résultat de la question I.A.1.b. Supposons Pn vraie à un certain rang n et démontrons-la à l’ordre n + 1. On a Sn+1,n = Sn,n−1 + nSn,n (d’après la question précédente) = n(n −1) 2 + n × 1 (d’après la question I.A.1.b et l’hypothèse de récurrence) = n(n −1) + 2n 2 = n(n + 1) 2 Ce qui termine la démonstration. Sn,n−1 = n(n −1) 2 ∀n ≥2 I.A.4. En utilisant Sn,k = Sn−1,k−1 + kSn−1,k ∀n ≥2 , ∀k ∈{1, . . ., n −1}, dans le cas n ≥3 et k = 2 (ce qui est compatible avec les conditions), on en déduit successivement : Sn,2 = Sn−1,1 + 2Sn−1,2 Sn,2 = 1 + 2Sn−1,2 Sn,2 + 1 = 2 + 2Sn−1,2 Sn,2 + 1 = 2(Sn−1,2 + 1) Ainsi, la suite (Sn,2 + 1)n≥2 est une suite géométrique de raison 2. On en déduit (puisque S2,2 = 1) Sn,2 + 1 = 2n−2(S2,2 + 1) = 2n−1 Sn,2 = 2n−1 −1 ∀n ≥2 L. Pharamond Lycée Chaptal Corrigé 2016 Centrale TSI Math I 3/13 I.A.5. a) On suppose n < k. Soit f une application de E dans F. Le cardinal de f(E) est inférieur ou égal à Card(E) = n, et donc l’image de E par f est de cardinal strictement plus petit que k. L’application f ne peut pas être surjective. σn,k = 0 si k < n b) On suppose n = k. Toute application surjective est alors nécessairement bijective. Compter le nombre de surjections, c’est compter le nombre de bijections dont on sait qu’il est égal à n! σn,k = n! si k = n c) Soit f une surjection de E dans F. On a F = {y1, y2}. Notons A1 l’image réciproque de y1 et A2 celle de y2 ; ce sont deux parties de E non vides puisque f est une surjection. De plus, {A1, A2} est une partition de E. Toutefois, {A2, A1} est la même partition de E mais correspond à une autre surjection de E dans F. Ainsi, à toute partition en deux parties de E correspond exactement deux surjections de E dans F. On en déduit σ3,2 = 2S3,2 = 6 d) i. Montrons que A = {A1, . . . , Ak} est une partition de E : • Soit i ∈{1, . . . , k}. L’ensemble Ai est une partie de E puisque c’est l’image réciproque par f d’une partie de F. • Soit i ∈{1, . . ., k}. L’ensemble Ai n’est pas vide puisque f est surjective. • Soit i, j ∈{1, . . . , k} distincts. L’ensemble Ai ∩Aj est vide car sinon un élément de cette intersection aurait à la fois pour image yi et yj ; ce qui est impossible car yi et yj sont supposés distincts. • La réunion des Ai pour i ∈{1, . . . , k} est par construction f −1(F) = E A = {A1, . . . , Ak} est bien une partition de E d) ii. Soit A ′ = {A′ 1, . . . , A′ k} une partition de E. Le nombre de surjections associées à cette partition est égal au nombre de bijections entre {A′ 1, . . . , A′ k} et F ; or le nombre de bijections entre deux ensembles de cardinal k est k! . Le nombre de surjections associées à A ′ est k! d) iii. On en déduit immédiatement σn,k = k!Sn,k I.A.6. Démontrons la propriété par récurrence sur n : Pour n = 0, la seule valeur de k comprise entre 0 et n est 0. Comme S0,0 = 1 ≤00, la propriété est vériﬁée.Pour n = 1, les valeurs de k comprises entre 0 et 1 sont 0 et 1 et on vériﬁe que S1,0 = 0 ≤01 et que S1,1 = 1 ≤21. Soit n ≥2. Supposons la propriété vraie à l’ordre n −1, avec k compris entre 0 et n −1. On cherche à démontrer la propriété à l’ordre n, avec k compris entre 1 et n. Nous allons traiter d’abord le cas où k est compris entre 0 et n −1, puis le cas où k = n. Tout d’abord considérons k un entier compris entre 0 et n −1. On a Sn,k = Sn−1,k−1 + kSn−1,k ≤ (2(k −1))n−1 + k(2k)n−1 ≤ 2n−1[(k −1)n−1 + kn] ≤ 2n−1[kn + kn] ≤ (2k)n Traitons maintenant le cas k = n. On a Sn,n = 1 ≤(2n)n. L. Pharamond Lycée Chaptal Corrigé 2016 Centrale TSI Math I 4/13 La propriété est donc vraie à l’ordre n pour toute valeur de k comprise entre 0 et k. Sn,k ≤(2k)n ∀n ∈N, ∀k ∈{0, . . . , n} I.B. Utilisation des nombres de Stirling en algèbre linéaire I.B.1. La famille {P0, . . . , PN} est une famille de N + 1 polynômes à degré échelonné ; {P0, . . . , PN} est une base de RN[X] I.B.2. a)Soit k ∈{0, . . . , N −1}, Pk+1 = k Y j=0 (X −j) = (X −k) k−1 Y j=0 (X −j) = uploads/Societe et culture/ i-generalites-sur-les-nombres-de-stirling.pdf