Remerciez-le!

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

Combinaisons avec r´ ep´ etition Cette notion ne ﬁgure pas dans les programmes

Combinaisons avec r´ ep´ etition Cette notion ne ﬁgure pas dans les programmes oﬃciels des classes de Lyc´ ee, mais elle m´ erite d’ˆ etre connue car elle peut intervenir dans une interrogation orale aussi bien que dans un probl` eme d’´ ecrit. Dans la note qui suit, on va s’attacher ` a d´ eﬁnir rigoureu- sement une telle combinaison et ` a proposer quelques d´ emonstrations de th´ eor` emes qui permettent de mettre l’ensemble des combinaisons avec r´ ep´ etition (cap en abr´ eg´ e) en bi- jection avec des ensembles qui interviennent souvent dans le domaine du d´ enombrement (on parle de combinatoire) et qui sont assez faciles ` a d´ enombrer. Avant de donner une d´ eﬁnition, il est bon de se familiariser avec la notion em- pirique de combinaison avec r´ ep´ etition. Si E d´ esigne un ensemble ﬁni d’objets, di- sons de cardinal n ∈N∗et si k est un entier naturel, il est possible de choisir k ´ el´ ements de E en acceptant de r´ ep´ eter certains ´ el´ ements plusieurs fois. Par exemple, si E = {D, H}, o` u D et H repr´ esentent « la droite » et « le haut » dans un d´ eplacement plan qui n’admet que ces deux orientations, il est possible de d´ eﬁnir un 5-d´ eplacement qui sera cod´ e {D, D, D, H, H} ou encore {D, H, D, H, D} et qui consiste ` a se d´ eplacer, d’une distance convenue, trois fois vers la droite et deux fois vers le haut (l’ordre des d´ eplacements n’ayant pas d’importance). Un tel d´ eplacement est appel´ e une 5- combinaison avec r´ ep´ etition des ´ el´ ements de E. Notez que la notation choisie n’est pas sans ´ equivoque. En eﬀet, en math´ ematique, usuellement, la notation entre accolades est r´ eserv´ ee ` a la notation d’un ensemble d´ efni en extension. Mais alors, tous les ´ el´ ements qui ﬁguent entre les accolades sont distincts deux ` a deux ; ce n’est pas la convention qui a ´ et´ e adopt´ ee ici. D´ eﬁnition : Soit n ∈N∗, E un ensemble de cardinal n et k ∈N. On appelle k- combinaison avec r´ ep´ etition d’´ el´ ements de E toute application f de E dans {0, 1, ..., k}, telle que X x∈E f(x) = k. Remarque : la valeur f(x) est le nombre de fois o` u l’´ el´ ement x de E est r´ ep´ et´ e dans la combinaison. On dit aussi parfois que f est une combinaison des n ´ el´ ements de E pris k ` a k. Si on revient ` a l’exemple introductif, l’application f de {D, H} dans {0, 1, 2, 3, 4, 5} qui est ´ egale ` a la 5-combinaison avec r´ ep´ etition compos´ ee de trois d´ eplacements vers la droite et de deux d´ eplacements vers le haut, est d´ eﬁnie par f(D) = 3 et f(H) = 2. Le parcours constitu´ e de cinq d´ eplacements vers le haut est l’application d´ eﬁnie par f(D) = 0 et f(H) = 5. Notation : On note d´ esormais Cn,k l’ensemble des k-combinaisons avec r´ ep´ etition d’un ensemble ` a n ´ el´ ements. 1 Proposition 1 : Il existe une bijection entre Cn,k et l’ensemble des solutions S(n, k), en entiers naturels αi, de l’´ equation (⋆) α1 + ... + αn = k. Proposition 2 : Il existe une bijection entre Cn,k et l’ensemble des distributions de k boules indiscernables dans n boˆ ıtes distinctes. D´ emonstrations : – Proposition 1 : Si on note E = {e1, ..., en}, ` a f ∈Cn,k on associe α1 = f(e1), ..., αn = f(en). par d´ eﬁnition d’une k-combinaison, la somme des αi, i ∈{1, ..., n} est ´ egale ` a k. Les αi ´ etant des entiers naturels, ils constituent une solution de l’´ equation (⋆). Si on note Ψ l’application pr´ ec´ edente entre Cn,k et S(n, k), Ψ est injective car Ψ(f) = Ψ(g) implique que ∀i ∈{1, ..., n}, ei est r´ ep´ et´ e le mˆ eme nombre de fois dans les k-combinaisons avec r´ ep´ etition f et g, celles-ci sont donc ´ egales. La surjectivit´ e de Ψ est triviale, ` a chaque solution en entiers (α1, ...αn) de (⋆) on associe f de E dans {0, ..., k} d´ eﬁnie par f(ei) = αi. – Proposition 2 : ´ A f ∈Cn,k on associe la distribution de boules d´ eﬁnies par : – f(e1) est le nombre de boules plac´ ees dans la boˆ ıte un ; – ... – f(en) est le nombre de boules plac´ ees dans le boˆ ıte n. Le caract` ere bijectif de cette association est ´ evident, il suﬃt de revenir ` a la d´ eﬁnition d’une k-combinaison avec r´ ep´ etition. Il est utile de donner une autre d´ eﬁnition d’une k-combinaison avec r´ ep´ etition. L’en- semble E ´ etant ﬁni, il peut ˆ etre suppos´ e totalement ordonn´ e et on peut noter ses ´ el´ ements de fa¸ con que si E = {x1, ..., xn} on ait x1 < x2 < ... < xn. Une k-combinaison avec r´ ep´ etition est alors associ´ ee bi-univoquement ` a un k-uplet croissant : (x1, ..., x1, x2, ..., x2, ..., xs, ..., xs), o` u chaque xi est r´ ep´ et´ e autant de fois que dans la k-combinaison avec r´ ep´ etition, ´ eventuellement 0 fois. Or, un tel k-uplet est lui-mˆ eme associ´ e bi-univoquement ` a l’application croissante, au sens large, de {1, ..., k} dans E qui est d´ eﬁnie par f(i) = l’´ el´ ement deE plac´ e en i-` eme position dans le k-uplet croissant. Il en r´ esulte que |Cn,k| = |Ac(k, n)|, o` u Ac(k, n) d´ esigne l’ensemble des applications croissantes de {1, ..., k} dans l’ensemble E de cardinal n. Supposons d´ esormais que E = {1, ..., n}. 2 Proposition 3 : Avec les notations pr´ ec´ edentes, l’application Φ d´ eﬁnie sur Ac(k, n) par Φ(f) : x 7→f(x) + x −1, ou encore Φ(f) = f + Id −1, transforme une application croissante au sens large de {1, ..., k} dans E en une application strictement croissante de {1, ..., n + k −1} dans E. De plus, Φ est bijective. D´ emonstration : La stricte croissance de Φ(f) est ´ evidente. En eﬀet, pour tout (i, j) ∈ {1, ..., k}2, si i < j, alors f(i) ≤f(j) et f(i) + i −1 < f(j) + j −1, c’est-` a-dire Φ(f)(i) < Φ(f)(j). Pour montrer que Φ est bijective, il suﬃt de construire une application qui en soit la r´ eciproque. Consid´ erons l’application Ψ d´ eﬁnie sur l’ensemble des applications stricte- ment croissantes de {1, ..., n + k −1} dans E (not´ e Asc(n + k −1, n)) par Ψ(f) : x 7→ f(x) −x + 1, ou Ψ(f) = f −Id + 1. Il est parfaitement ´ evident que Ψ ◦Φ = IdAc(k,n) et Φ ◦Ψ = IdAsc(n+k−,n). Pour d´ enombrer commod´ ement Cn,k, on va construire une bijection entre cet ensemble et un ensemble dont le d´ enombrement r´ esultera de connaissances ´ el´ ementaires. Pour cela revenons sur la notion basique de combinaison (sans r´ ep´ etition). Th´ eor` eme 1(suppos´ e ici bien connu) : Soit n ∈N∗et E un ensemble de cardinal n. Si p est un entier inf´ erieur ou ´ egal ` a n, l’ensemble not´ e Cn,p des p-combinaisons de E a pour cardinal n p . Th´ eor` eme 2 : Si on note Asc(p, n+p−1) l’ensemble des applications strictement crois- santes de {1, ..., p} dans {1, ..., n+p−1}, alors les ensembles Cn+p−1,p et Asc(p, n+p−1) sont ´ equipotents. Pour d´ emontrer ce th´ eor` eme il suﬃt de construire une bijection de Cn+p−1,p sur Asc(p, n+ p −1). ` A chaque p-combinaison d’´ el´ ements de {1, ..., n + p −1}, not´ ee c, on associe le p-uplet : (i1, ..., ip) o` u les coordonn´ ees sont rang´ ees dans l’ordre croissant. Alors, l’ap- plication qui ` a c associe f d´ eﬁnie par f(1) = i1, f(2) = i2, ..., f(p) = ip est strictement croissante de {1, ..., p} dans {1, ..., n+p−1}. Il est clair que la correspondance est bijective. Th´ eor` eme 3 : Pour tout n ∈N∗et k ∈N, les ensembles Cn,k et Asc(n + k −1, k) sont ´ equipotents. On en d´ eduit que le cardinal de Cn,k est ´ egal ` a n + k −1 k . D’apr` es la proposition 3 pr´ ec´ edemment ´ etablie, Cn,k et Asc(n+k−1, k) sont ´ equipotents. D’apr` es le th´ eor` eme 2, Asc(n+k−1, k) et Ck,n+k−1 sont ´ equipotents et d’apr` es le th´ eor` uploads/Religion/ combinaisons-avec-repetitions-deduccion-por-aplicaciones.pdf