Cours Maths: analyse combinatoire

Fiche 1

Analyse combinatoire

1/ Généralités

L'analyse combinatoire est l'ensemble des techniques qui servent à compter,

énumérer ou dénombrer des structures finies. Plusieurs éléments importants

interviennent dans cette analyse de structure :

· Le nombre de positions (emplacements) du mot à construire

· La notion d'ordre ou de non-ordre sur ces positions

· Le nombre de valeurs acceptées à chaque position (l'alphabet)

· La répétition ou la non répétition de valeurs de l'alphabet pour chacune

des différentes positions

2/ Ensemble dénombrable et dénombrement

On appelle un ensemble dénombrable un ensemble de même cardinal que

Ð. On note par À0 ce cardinal (À0 : lire aleph 0).

Dans la pratique nous sommes amenés à compter des ensembles autres que

ceux qui ont un cardinal À0. Plus particulièrement, nous sommes fréquemment

amenés à dénombrer le nombre d’arrangements possible de caractères en nombre

fini, dans un mot de longueur fixe.

Différentes situations sont possibles suivant que l’on puisse utiliser à

volonté ces caractères en les dupliquant, en utilisant les caractères sans duplication,

ou encore en tenant compte d’une notion d’ordre sur ceux-ci.

Les formes correspondantes sont :

· pn , lire "p à la puissance n"

· p! lire "Factorielle p"

· n

p A lire "Arrangement de p caractères pris n à la fois"

· cn

pLes ensembles – représentations et réductions – Cas des représentations

binaires

1/ Les ensembles

C’est une notion qui nous est familière. Un groupe d’éléments de même

nature constitue un ensemble :

L’ensemble des individus composant un foyer fiscal, l’ensemble des parts fiscales

d’un foyer, l’ensemble des objets déposés sur une étagère, l’ensemble des nombres

naturels…

L’appartenance d’un élément ‘e’ à un ensemble ‘E’ se représente par le

signe ‘Î’ et dans le cas contraire sa non appartenance se représenterait par le signe

‘Ï’.

E={a, e, i, o, u} ; e Î E et y Ï E

Un ensemble E peut être caractérisé en extension ou en compréhension(=intention).

En extension : E={a, e, i, o, u}

En compréhension :E={ toutes les voyelles minuscules de l’alphabet privé de y}

2/ Dénombrabilité - ensemble fini - ensemble infini

Tout ensemble ayant le même cardinal que Ð est dit dénombrable. Cardinal de Ð est

appelé À0 (lire Aleph zéro). Par exemple l’ensemble des

...