Remerciez-le!

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

160 E.N.S.A.I. 1997 lère épreuve 1/6 INSTITUT NATIONAL DE LA STATISTIQUE ET DES

160 E.N.S.A.I. 1997 lère épreuve 1/6 INSTITUT NATIONAL DE LA STATISTIQUE ET DES ÉTUDES ÉCONOMIQUES ÉCOLE NATIONALE DE LA STATISTIQUE ET DE L’ANALYSE DE L’INFORMATION concours d‘élève titulaire de I‘ENSAI concours externe d‘attaché de l’INSEE Option A. - MATHÉMATIQUES première composition de mathématiques Durée : 4 heures Notations - rappels On note 1 E 1 le cardinal d’un ensemble fini E . N* désigne l’ensemble des entiers naturels privés de O. Si n E N*, on désigne par [n] un ensemble S, désigne l’ensemble des permutations de ( 1, 2;. . . , n ) (n E N*) . On rappelle que 1 S, 1 = n ! . On note R O(] l’ensemble des polynômes à coeflcients réels à n Cléments que l’on identifiera à ( 1, 2, . . . , n ) pour simplifier. Rappels : On note . l’opération d’un groupe G sur un ensemble X. Si x E X, l’orbite de x est l’ensemble, noté G . x , égal à ( g . x , g E G}. Les orbites de X forment une partition de X . Lorsque G est un sous-groupe de S , , G opère sur [n] par : g . k = g ( k ) ( g E G , k E [n 1). Le but du problème est de passer en revue quelques techniques de dénombrement. Les quatre parties sont indépendantes. PARTIE 1 Cardinaux d’ensembles finis 1. Formule du produit. Soient E, , . . . , En n ensembles finis (n E N*) . On admet la formule : IE, X ... X E n [ = IE,I X ... X IE,I (*). E.N.S.A.I. 1997 lkre épreuve 2/6 161 ci. Déduire de (*) que le nombre d’applications de [ n ] dans [ m ] est m”(m E N*). On appelle nombre de Stirling de deuxième espèce le nombre de partitions d’un ensemble à n Cléments en m classes non vides ((n, m ) E ( N * ) * , m < n ) . On note S y ce nombre. b. Justifier que m! S; est le nombre de surjections de [ n ] sur [ m ] . c. Justifier I’égalité : k = I d. Déduire de la question c. que : I l ( V X E R ) , ,f=C S f : x x ( x - l ) X ... X ( x - k + l ) , (nfixédansN*). k = 1 2. Formule de PoincarC. Soient E, , . . . , E, II ensembles finis (n E N*) . On admet la formule : n IE, U ... U E , l = C (- l),-’ 1 E,, n E,, n ... nEi, 1 ) (**). k = I ci. Soit n E N*. On note : D, = { u E S , / a(k) f k , V k E { 1, 2, .... n } } et E, = {u E S,,/ u ( k ) = k } (k E ( 1 , 2, ..., n )). À l’aide de la formule (**) précédente, montrer que : ...+- n! 1 1 l ! 2! ) D , , I = n ! ( 1 -- +-- b. Soit ( n , m ) E (N*)’, n 2 m . Montrer que le nombre s ( n , m ) .de surjections de [n ] sur [m ] s’écrit : ni s ( n , m ) = C (-l)k C t ( m - k ) ” = r n ! S r (d’après 1.b.). PARTIE II k = O Formules d’inversions 1 . Formules binomiales inverses. a. Soient Po, P I , . . . , P,, Qo, Q I , . . . , Q, 2n + 2 polynômes àcoefficients réels vérifiant : degré ( P k ) = degré (Q,) = k , k = O, 1, 2 , . . . , n (n E N). a. Montrer que {Po, P, , . . . , P, ) forme une base de W,, [ X I = { P E R [ X I / degr6 (P) S n } . On pose : k k P, = (yk., Qi et QI, = Phi Pi. r = O i = O les a , , et les pk,, étant des scalaires (O S i 6 k S n ) . 162 E.N.S.A.I. 1997 lère épreuve 3/6 p. En déduire que, quels que soient les 2n + 2 nombres réels a,, a , , . . ., a,, b,, b , , . . ., b,, les relations : I=o impliquent : h (2) b, = C pk, a, (k E 1 0 , 1 , 2 , . . . , n 1). , = O On pourra chercher une interprétation matricielle des relations (1) et (2). b. Application : d’après la formule du binôme : n n ( V X E R ) , Y=C C;(X-I)‘ et ( X - I ) ~ = ~ ~ : ( - 1 ) ~ - ~ X k . k = O k = O Utiliser I’égalité de la question 1.1 .c. pour montrer que l’on retrouve la formule de la question 1.2.b. donnant le nombre de surjections de [ n ] sur [m J ( ( n , m ) E (N *)’, m S n ) . 2. Formule d’inversion de Mobius. On munit l’ensemble A des fonctions de N * dans Z de la loi T définie par u. Montrer que T possède un Clément neutre e . On admettra par la suite que T est associative. h. Soit n E N \ (O, 1 ] . On note : n = ppl X . . . X ptk sa décomposition unique en produit de nombres premiers p , , . . . , pk (k E N * ; a,, . . . , a, étant des entiers positifs, non tous nuls). L‘entier n 2 2 étant ainsi décomposé, on pose : p ( n ) = (- 1)’ et p(1) = 1 , ce qui définit ainsi une fonction p . de A (fonction de Mobius). Montrer que : z : N * + Z n - 1 , est l’inverse de p pour T. c. Soient f’ et g deux Cléments de A . Montrer I’équivalence : [ ( v n n ~ ~ * ) , f ( n ) = c g ( d ) ( ~ J ~ E N * ) , g ( n ) = c p ( d ) x j ( ; ) ) I S d G n : d divise n 1 S d S n : d divise n (remarquer que f s’exprime simplement à l’aide de z et g ) . E.N.S.A.I. 1997 lère épreuve 4/6 163 d. Application : un alphabet est un ensemble de m symboles distincts { a , , . . ., a , ) (m E N*). Un mot de longueur n est une application de [n] dans (a, ,..., a,) (m E N * ) . Si deux mots cp et cp‘ de longueur n vérifient : cp’(i)=cp(i + p ) (i = l , 2 , . . . ,n), on dit qu’ils sont équivalents ou qu’ils constituent le même mot circulaire (les sommes étant modulo n). Si un mot cp de longueur n est tel que : on dit que p est période de cp. La plus petite période est appelée période primitive de cp. Par exemple, le mot abcabc est de période primitive 3. On admettra qu’une période p est nécessairement un diviseur de n. Soit M ( p ) le nombre de mots circulaires de longueur n et de période primitive p . Montrer que le nombre total de mots circulaires est : 3 p E ( 1 , 2 ,... n ) : cp(i+p)=cp(i) ( i = l , 2 ,..., n), PARTIE III Utilisation de fonctions génératrices Exemple 1 : En reprenant l’expression de Sr trouvée dans la partie 1, question 2.b., montrer que : cette série ayant un rayon de convergence infini (on fait la convention que S : = O si n < m). Calculer Sg, (n E N). Exemple 2 : Soit n E N*. On note 1 , le nombre d‘involutions de [n], c’est-à-dire le nombre d’applications j ’ de [n] dans lui-même vérifiant : f o f ’ = Id (identité de Sn). 1. 2. 3. 4. Justifier la formule de récurrence : 1 , = In-, + ( n - 1) (n 3 3). + O 0 . 1 Soit Y ( x ) = 2 Y (x E R). Montrer que le rayon de convergence de Y est au moins égal à 1 et “ = O n! que l’on a l’égalité : V x E 3- 1, + 1 [, uploads/s3/ concours-d-eleve-titulaire-de-i-ensai-concours-externe-d-attache-de-l-x27-insee 1 .pdf