[PDF] Combinatoire énumérative

View - Download Combinatoire énumérative

Previous PDF

Next PDF

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,quotesdbs_dbs50.pdfusesText_50

[PDF] demontage banquette arriere peugeot 2008

[PDF] demontage thermomix 3000

[PDF] demontage thermomix tm21

[PDF] démontrer droite parallèle plan

[PDF] démontrer par récurrence que pour tout entier naturel n

[PDF] démontrer qu'un point est le milieu d'un segment

[PDF] démontrer qu'une fonction est croissante

[PDF] démontrer qu'une fonction est décroissante sur un intervalle

[PDF] démontrer qu'une suite est arithmético-géométrique

[PDF] démontrer que deux droites sont orthogonales produit scalaire

[PDF] démontrer que deux plans sont parallèles

[PDF] démontrer que l'affirmation l'homme descend du singe est fausse

[PDF] démontrer que les droites (ab) et (cd) sont parallèles

[PDF] démontrer suite géométrique

[PDF] démucilagination