[PDF] MINI-COURS DE COMBINATOIRE

[PDF] 1 Démonstrations du formulaire de trigonométrie -

[PDF] Primitives et intégrales

[PDF] Charlemagne sur Internet - Statim

[PDF] ROC - Math France

[PDF] III- Raisonnement par récurrence

[PDF] Raisonnement par récurrence - Math France

[PDF] Planche no 2 Raisonnement par récurrence : corrigé

[PDF] Planche no 2 Raisonnement par récurrence : corrigé

[PDF] Raisonnement par récurrence Suites numériques I -

[PDF] PGCD et PPCM de deux entiers :

[PDF] pgcd et nombres premiers - Maths-et-tiques

[PDF] RÉUSSIR L 'ÉPREUVE DE PHYSIQUE Baccalauréat 2015 -

[PDF] Intégration et primitives - Lycée d 'Adultes

[PDF] Démonstration de la formule de conjugaison pour le

[PDF] Optique géométrique

[PDF] MINI-COURS DE COMBINATOIRE - Igor Kortchemski

Combinatoire énumérative

Igor Kortchemski

-Introduction- La Combinatoire est un sous-art des mathématiques qui consiste à compter et à étudier

des structures finies. De nombreux problèmes difficiles sont formulés de manière très simple

(mais la résolution nécessite des outils avancés). Le but de ce cours est de présenter quelques

réflexes et idées de bases pouvant être utiles dans la résolution d"exercices de combinatoire

de type olympiades. On parlera de coefficients binomiaux, double-comptage, injections, surjections, bijections. 1

Coef ficientsbinomiaux

1.1

Définitions

On rappelle qu"un ensembleEest une collection d"éléments dont l"ordre n"a pas d"impor- tance (ainsi, les ensemblesf2,3getf3,2gsont les mêmes ensembles) et comptés sans multipli- cité (par exemple, 2,2=2). On notex2Asixappartient à l"ensembleA. SiAetBsont deux ensemble, on écritABet on dit queAest inclus dansBsi chaque élément deAappartient à B. L"ensemble vide, qui ne contient aucun élément, est noté;. On note Card(A)(on prononce " cardinal deA») le nombre d"éléments deA. On dit queAest infini si Card(A) =1, fini sinon.

Définition 1.Pour des entiers 06k6n, on noten

k(et on prononce "kparmin») le nombre

de manières de choisir un sous-ensemble àkéléments d"un ensemble ànéléments différents.

Pourk > n, on posen

k=0. Il est clair que dans la définition précédente, n kne dépend pas de l"ensemble ànéléments différents considéré.

Exemple 2.On a4

2=6, car les sous-ensembles à 2 éléments def1,2,3,4gsontf1,2g,f1,3g,

f1,4g,f2,3g,f3,4get il y en a 6 Pour un entiern>1, rappelons la notationn!=123 (n-1)n. On lit "n factorielle". Proposition 3.Le nombre de manières d"ordonnernéléments estn!.

Démonstration.Nous avonsnpossibilités pour choisir le premier élément,n-1 possibilités

pour le deuxième, et ainsi de suite jusqu"au dernier élément pour lequel nous avons une seule

possibilité. Le résultat en découle.1

Proposition 4.Pour des entiers 06k6n, on a :

n k =n!(n-k)!k!. Démonstration.Utilisons le principe dedouble-comptage, très important en combinatoire. Il

consiste à établir une égalité en comptant de deux manières différentes une certaines quan-

tité. Ici, comptons le nombre de suites àkéléments qu"on peut créer en utilisant lesnéléments

d"un ensemble ànéléments différents. D"une part, comme pour la proposition précédente, nous avonsnchoix pour le premier

terme de la suite;n-1 choix pour le deuxième, et ainsi de suite jusqu"auk-ième élément pour

lequel nous avonsn-k+1 choix. Finalement, il y a en toutn(n-1)(n-k+1) =n!(n-k)!suites àkéléments.

D"autre part, pour créer une suite àkéléments, on peut commencer par choisir leskélé-

ments qui vont constituer la suite (n kpossibilités), puis les ordonner (k! manières possibles de les ordonner). Il y a donc en toutk!n ksuites àkéléments.1.2Propriétés combinatoires

Exercice 1Pour des entiers 06k6n, on a :

n k =n n-k Solution de l"exercice 1Première méthode :On utilise la formulen k=n!(n-k)!k!et le résultat en découle immédiatement.

Deuxième méthode :On remarque que choisirkéléments parminrevient à sélectionner les

n-kéléments qu"on ne choisira pas. L"exercice précédent, bien que facile, est assez représentatif des exercices ayant pour but

de prouver des relations d"égalité entre coefficients binomiaux. Très souvent, il y a toujours

(au moins) deux approches possibles : remplacer les coefficients binomiaux par leur formule

et ramener le problème à un exercice de manipulation de relations algébriques, ou bien inter-

préter de manière combinatoire les deux termes de part et d"autre de l"égalité et prouver qu"ils

sont égaux. La deuxième approche est bien sûr bien plus élégante et fournit très souvent des

preuves courtes, mais requiert davantage d"ingéniosité. Proposition 5.(formule de Pascal) Soientnet 06k6ndes entiers (avec(k,n)6= (0,0)).

Alors :

n k =n-1 k +n-1 k-1 2 Démonstration.Pr emièreméthode : On utilise la formule : n-1 k +n-1 k-1 =(n-1)!k!(n-1-k)!+(n-1)!(k-1)!(n-k)! (n-1)!(k-1)!(n-1-k)! 1k +1n-k (n-1)!(k-1)!(n-1-k)! nk(n-k) n!k!(n-k)! f1,2,...,nget dénombrons ses sous-ensembles àkéléments. On distingue les ensembles qui contiennent l"élémentnet les ensembles qui ne le contiennent pas. Il y an-1 kensembles qui ne contiennent pasn(on choisitkéléments dansf1,2,...,nget il y en an-1 k-1qui contiennent n. Au total on a doncn-1 k+n-1 k-1manières de choisir noskéléments parmi nosnentiers,

d"où le résultat.La formule de Pascal nous permet ensuite de construire le triangle de Pascal, que vous

connaissez peut-être déjà. La case située dans lak-ième colonne de lan-ième ligne contient le

coefficient binomialn-1 k-1. D"après la formule de Pascal, on obtient donc chaque case comme la somme des deux cases qui sont au-dessus. 111
121
1331
14641

15101051

1615201561

172135352171

de(x+y)n: Proposition 6(Formule du binôme de Newton).Soientx,ydes nombres réels etn>1 un entier. Alors : nX k=0 n k x kyn-k= (x+y)n. Notation.Avant de démontrer cette formule, un petit rappel de notation : 3 Lorsqu"on veut faire une grosse somme de termes qui peuvent s"exprimer selon un entier, souvent noték(ouimais cela n"a pas d"importance), qui varie entre deux valeurs, on utilise le symboleP. Par exemple : n X k=01=1+1+...+1=n+1 n X k=0k=0+1+2+...+n=n(n+1)2 n X k=0 n k =n 0 +n 1 +...+n n-1 +n n Pour un produit on utilise de la même manière le symbole

Q. Par exemple :

n Y k=1k=n!

Démonstration.

Pr emièreméthode : par récurrence surn(s"entraîner à le faire). Seconde méthode :lorsqu"on développe(x+y)(x+y)(x+y), pour trouver le coefficient devantxkyn-k, parmi lesntermes(x+y), il faut en choisirkpour lesquels on garde lexet qui vont donner un termexk, et lesn-kautres termes pour lesquels on sélectionney(et qui

sont fixés par le choix deskpremiers) vont donner le termeyn-k. Le résultat s"ensuit.Exercice 2Pour tout entiern>1, on a

n X k=0 n k =2n.

Exercice 3Pour 06k6n, on a :

k n k =nn-1 k-1 Exercice 4Quel est le cardinal moyen d"un sous-ensemble def1,2,...,ng?

Exercice 5Prouver que pour 06m6n:

n X k=0 n k k m =n m 2 n-m. Exercice 6Combien y a-t-il de chemins surZ2issus de(0,0), faisant des pas+(1,0)ou+(0,1), et finissant en(m,n), oùm,n>0? Exercice 7De combien de manières peut-on placer 5 pièces identiques dans 3 poches diffé- rentes? 4 Solution de l"exercice 2Première méthode :Si on n"a pas d"idée comment commencer de ma-

nière astucieuse, on peut essayer de procéder par récurrence surn. Pourn=1, le résultat est

clair. Supposons le résultat acquis au rangnet montrons-le au rangn+1 en écrivant, avec la formule de Pascal : n+1X k=0 n+1 k =1+n+1X k=1 n k +n k-1 nX k=1 n k +nX k=0 n k =2n+2n(par hypothèse de récurrence) =2n+1, Seconde méthode :Démontrons ce résultat de manière combinatoire en comptant le nombre Nde sous-ensembles def1,2,...,ng. D"une part, pour un entier 06k6n, il y an ksous- ensembles àkéléments. En sommant le tout, on voit queN=Pn k=0 n k. Mais, pour construire un sous-ensemble def1,2,...,ng, on a le choix de choisir 1 ou non,

2 ou non, et ainsi de suite jusqu"àn. On a doncnchoix à faire entre deux possibilités et ces

choix sont indépendants (le choix de prendrekou non n"influence pas le choix de prendrek0 ou non sik6=k0), d"oùN=2n, ce qui permet de conclure. En particulier, la solution précédente montre qu"il existe 2 nsous-ensembles d"un ensemble

ànéléments.

Troisième méthode :On utilise la formule du binôme de Newton avecx=y=1. Solution de l"exercice 3Première méthode :On utilise la formule exprimantn k(on vous laisse le faire). Seconde méthode :Démontrons ce résultat de manière combinatoire en comptant de deux manières différentes le nombre de sous-ensembles def1,2,...,ngde cardinalkayant un élé- ment distingué (qu"on appellera chef). D"une part, il suffit de choisir un sous-ensemble de cardinalk(n kchoix), puis de choisir un chef (kchoix indépendants). On obtient donc en toutkn kpossibilités. D"autre part, on peut d"abord choisir un chef (nchoix) puis compléter lesk-1 éléments à choisir dansf1,2,...,ngprivé du chef (donc un ensemble àn-1 éléments). Il y a alorsnn-1 k-1

éléments.

Solution de l"exercice 4

Première méthode (d"après une idée d"élèves) :On regroupe un ensemble avec son complémen-

taire. SiAf1,2,...,ng, on noteAcl"ensemble des entiers def1,2,...,ngqui ne sont pas dans

A. NotonsNce cardinal moyen. Alors :

N=12 nX

Af1,2,...,ngCard(A) =12

Af1,2,...,ngCardA+Card(Ac)2

12 nX

Af1,2,...,ngn2

=12 nn2 2n=n2

Autre méthodes :Il faut évaluer la somme

S n=12 nn X k=0kn k 5 Si on ne sait pas commencer, il faut étudier les premiers cas :n=1,2,.... On trouve toujours S n=n=2. Essayer donc de démontrer cela. Seconde méthode :Si on n"a pas d"idée, on peut procéder par récurrence surn.

Troisième méthode, plus avancée. On utilise le résultat de la proposition6 . Considérons le

polynômePn(x) =Pn k=0 n kxk. D"après la formule du binôme de Newton,Pn(x) = (1+x)n. Dérivons cette égalité par rapport àx: nX k=0kn k x k-1=n(1+x)n-1.

Évaluons alors cette quantité enx=1 :

nX k=0kn k =n2n-1.

Le résultat en découle.

Solution de l"exercice 5On remarque d"abord que seuls lesktels quek>mcontribuent de manière non nulle. On va procéder à un double comptage en comptant le nombreNde sous-ensemblesA,Bdef1,2,...,ngtels queABet Card(A) =m. En effet, d"une part, pour construireA,Bon peut d"abord choisirAde cardinalm(n mchoix), puis rajouter un sous- ensemble quelconque de l"ensemblef1,2,...,ngprivé des éléments deA, qui an-méléments (et donc 2 n-mchoix indépendants). En ainsi,N=n m2n-m. D"autre part, pour construireA,Bon peut d"abord choisirBde cardinal quelconque entre metn(siBest de cardinalk,n kchoix), puis choisirAde cardinalmcomme sous-ensemble deB(k mchoix siBest de cardinalk). Ainsi,N=Pn k=0 n k k m. Il suffit donc de choisir parmi lesm+npas possibles la position desmqui font+(1,0). Le nombre total vaut doncm+n m.

Solution de l"exercice 7Considérons la figure suivante (avec deux barres) :Remplaçons chaque rond soit par une pièce, soit par une barre de sorte qu"il y ait en tout 2

poche, et finalement les pièces entre la troisième barre et la quatrième barre seront contenues

dans la troisième poche.

Ainsi, placer 5 pièces identiques dans 3 poches différentes, revient à choisir la position des

2 barres parmi 7 positions possibles. La réponse est donc7

2=21. Plus généralement, en procédant de la même façon, on voit qu"il y aa+b-1 b-1=a+b-1 a manières de placerapièces identiques dansbpoches différentes. 6

2Principe d"Inclusion-Exclusion

On sait que siAetBsont deux ensembles finis, alors Card(A[B) =Card(A)+Card(B)- Card(A\B). La formule suivante, dite d"inclusion-exclusion, généralise cela au cas où nous en avons un nombre quelconque. Proposition 7(Formule d"inclusion-exclusion).SiA1,...,Ansont des ensembles finis, alors :

Card(A1[A2[ [An) =nX

k=1(-1)k+1X

16i1< (Ai1\ \Aik).
Démonstration.Par récurrence (bon courage!)Exercice 8Combien y a-t-il d"entiers strictement positifs inférieurs ou égaux à 120 et qui ne
sont divisibles ni par 3, ni par 5, ni par 7? Exercice 9Lesnstagiaires au stage de Montpellier vont se baigner et laissent leurs t-shirts Animath en vrac sur le sable. Ils reviennent et prennent un t-shirt complètement au hasard.quotesdbs_dbs29.pdfusesText_35

[PDF] [PDF] MINI-COURS DE COMBINATOIRE - Igor Kortchemski