L'analyse combinatoire est une branche des mathématiques discrètes qui consiste à dénombrer des structures définies sur des ensembles finis par des propriétés combinatoires. Elle s'approche, beaucoup plus que l'on ne pense, de l'informatique.
Le dénombrement est un calcul. Le véritable but en cette matière ne se restreint pas à trouver l'expression de la série finie qui donnera la valeur de ce calcul. Elle cherche à donner une expression, qui peut être plus générales qu'une série, la plus efficace à calculer ou la plus simple à définir. Autrement dit, un algorithme de calcul qui soit de complexité économe (simple à calculer) ou de définition économe (simple à écrire), soit à chaque fois deux objectifs potentiellement contradictoires, et donc souvent deux formulations.
C'est donc un effort de conception du langage des algorithmes et du langage des démonstrations sur ces algorithmes qu'il convient de mettre en oeuvre. Prenons par exemple la suite de Fibonacci qui est définie par :
`F(0)=0`
`F(1)=1`
`AAn">"1, F(n)=F(n"-"1)+F(n"-"2)`
La formule de Binet trouve un autre moyen de calcul :
`varphi = (1+sqrt(5))/2`
`AAn"⩾"0, F(n) = "arrondi"(( varphi^n)/sqrt(5) )`
La première expression, si elle est programmée avec mémoire des résultats intermédiaires, est la plus efficace en terme de complexité de calcul, tandis que la seconde formule peut être considérée d'un certain point de vue comme plus simple à écrire.
On suit en parallèle le chapitre De l'algèbre et du dénombrement
On commence par décrire 4 types d'assemblages rudimentaires que sont la liste, l'arrangement, le sac (ou multi-ensemble), et l'ensemble.
Le premier type d'assemblage que l'on conçoit sont les listes. On peut considérer la liste comme une succession de choix d'éléments pour produire un assemblage dans lequelle il n'y a aucune perte d'information.
On note entre parenthèse `(a,a,b)` les éléments d'une listes, sachant qu'ils peuvent être répétés plusieurs fois et que l'ordre compte. Soit une liste `L`, on note sa taille `|L|`. Exemple `"|"(a,b,a,a)"|"=4`. La liste vide se note `()`.
On appelle case n°`n` (ou cellule n°`n`) de la liste `L` , notée `L[n]`, l'emplacement n°`n` dans la liste, en commençant par `0`. Exemples `L"=" (a,b,c,d)`, `L[0]"="a`, `L[2]"="c`. On verra par la suite que la liste constitue l'archétype de l'application.
En faisant abstraction des répétitions, chaque liste `L` se transforme canoniquement en un arrangement notée `"%repetition"(L)` qui est l'arrangement des premières occurences des éléments de la liste.
En faisant abstraction de l'ordre des cases, chaque liste `L` se transforme canoniquement en un sac notée `"%ordre"(L)`, qui est le sac des éléments de la liste.
En faisant abstraction à la fois des répétitions et de l'ordre des cases, chaque liste `L` se transforme canoniquement en un ensemble notée `"%repetition"("%ordre"(L))` ou bien `"%ordre"("%repetition"(L))` qui est l'ensemble des éléments présents au moins une fois dans la liste. Cet ensemble est aussi appelé le support de `L`.
Lorsque l'on fait abstraction de l'ordre des éléments, on perd l'existence d'une forme normale. Pour retrouver cette forme normal il suffit de définit un ordre système de tous les éléments. En utilisant un tel ordre complet, le sac et l'ensemble possèdent alors une forme normale qui est la liste de leurs éléments dans cet ordre système.
Un arrangement est une liste d'éléments distincts. C'est aussi un ensemble muni d'un ordre total.
On note entre chevrons `⟨a,b,c⟩` les éléments d'un arrangement sachant qu'ils doivent être distincts et que l'ordre compte. Soit un arrangement `A`, on note sa taille `|A|`. Exemple `|⟨a,b,c⟩|=3`. L'arrangement vide se note `⟨⟩`.
En faisant abstraction de l'ordre, chaque arrangement `A` se transforme canoniquement en un ensemble notée `"%ordre"(A)`, qui est l'ensemble des éléments présents dans l'arrangement. Cet ensemble est aussi appelé le support de `A`.
Un sac est une liste d'éléments à l'ordre près. Autrement dit, le sac est une classe d'équivalence regroupant des listes, où la relation d'équivalence en question est : deux listes sont équivalentes si l'une peut être obtenue de l'autre en permutant ses cases.
On note entre symbole de sac `⟅a,a,b⟆` les éléments d'un sac, sachant qu'ils peuvent être répétés plusieurs fois. L'ordre n'y a pas d'importance. Soit un sac `S`, on note sa taille `|S|`. Exemple `|⟅a,a,b⟆|=3`. Le sac vide se note `⟅⟆`.
En faisant abstraction des répétitions, chaque sac `S` se transforme canoniquement en un ensemble notée `"%repetition"(S)`, qui est l'ensemble des éléments présents au moins une fois dans le sac. Cet ensemble est aussi appelé le support de `S`.
Un ensemble est un sac particulier où tous les éléments n'apparaissent qu'une seuls fois et sont deux à deux distincts. Un ensemble est un arrangement dans lequelle l'ordre n'a pas d'importance. Autrement dit l'ensemble est une classe d'équivalence regroupant des arrangements, où la relation d'équivalence en question est : deux arrangements sont équivalents si l'un peut être obtenue de l'autre en permutant ses éléments.
On note entre accolades `{a,b,c}` les éléments d'un ensemble sachant que l'ordre n'y a pas d'importance mais que les éléments doivent n'apparaitre qu'une seule fois et doivent être deux à deux distincts. Soit un ensemble `E`, on note sa taille `|E|`. Exemple `|{a,b,c}|=3`. L'ensemble vide se note `{}`.
Pour transformer un ensemble en un arrangement il faut y définir un ordre totale.
L'assemblage le plus précis est la liste, les autres assemblages correspondent à des ensembles de listes de même taille qui regroupe les différentes possibilités de listes. Une représentation globale disjonctive apparait sous forme d'ensemble de listes de même taille. Exemples où `Sigma` est le sous-groupe des permutations circulaires :
`(a,b,a,c) = {(a,b,a,c)}` `⟅a,b,a,c⟆={(a,a,b,c), (a,b,a,c), (b,a,a,c), (a,a,c,b), (a,b,c,a), (b,a,c,a), (a,c,a,b), (a,c,b,a), (b,c,a,a), (c,a,a,b), (c,a,b,a), (c,b,a,a) }`
`⟨a,b,c⟩={(a,b,c)}`
`{a,b,c}={(a,b,c),(b,c,a),(c,a,b)(a,c,b),(c,b,a),(b,a,c)}`
La fonction `"%repetition(.)"` qui veut dire "aux répétions d'éléments près", appliquée à une liste va produire la liste des premières occurences.
La fonction `"%ordre(.)"` qui veut dire "à l'ordre près", appliquée à une liste va produire toutes les listes possibles obtenue par permutation de ses cases.
La suppression de l'ordre, qui est mise en oeuvre dans l'ensemble et le sac, consiste à compléter ces ensembles de listes par les listes obtenues en appliquant toutes les permutations possibles. Il est alors possible de concevoir des assemblages intermédiaires, non pas à l'ordre près, mais à un sous-groupe de permutation près, par exemple à une permutation circulaire près.
La suppression des répétitions d'élément, qui est mise en oeuvre dans les ensembles et les arrangements, s'obtient en ne gardant que les premières occurrences des éléments.
L'approche informatique introduit un ordre système de tous les objets, et introduit la notion de classe d'objets. L'objets correspondra à l'élément, et la classe correspondra au type.
On définie 4 types qui vous jouer le rôle de classe dans un langage de programmation objet :
Le type fondamental est la liste qui mémorise une succession de choix d'éléments sans perte d'information.
L'ensemble se définie comme un ensemble d'arrangements de même taille, et il admet une représentation unique en l'arrangement des éléments de l'ensemble dans l'ordre système.
Le sac se définie comme un ensemble de listes de même taille, et il admet une représentation unique en la liste des éléments du sac dans l'ordre système.
L'arrangement est une liste d'éléments distincts.
L'héritage peut-être multiple. La liste à deux fils, le sac et l'arrangement. Cela signifie entre-autre que le sac est une liste particulière, et que l'arrangement est une liste particulière :
L'ensemble à deux pères, le sac et l'arrangement. Cela signifie entre-autre que l'ensemble est un sac particulier, et que l'ensemble est un arrangement particulier :
On définie l'opération d'union, noté `uu`, et s'appliquant aux objets de ces 4 types comme suit :
Ainsi par exemples :
`{a,b}uu{a,c} = {a,b,c}`
`⟨a,b⟩uu⟨a,c,b⟩=⟨a,b,c⟩`
`⟅a,a,b⟆uu⟅a,a,c⟆ = ⟅a,a,a,a,b,c⟆`
`(a,a,b)uu(a,a,c) =(a,a,b,a,a,c)`
On définit l'opération d'union disjointe notée `"+"` , c'est une union qui duplique le jeux des éléments du second membre déjà présent dans le premier membre, pour simuler une union disjoint. Elle s'applique aux objets de ces 4 types. L'opération d'union disjointes, `"+"` se comporte pareillement que l'union à part le fait qu'elle utilise une copie des éléments pour simuler une union disjointe. Ainsi par exemples :
`{a,b}uu{a,c} = {a,b,c}`
`{a,b}+{a,c} = "{a,b,a_1,c}`
`⟨a,b⟩uu⟨a,c,b⟩=⟨a,b,c⟩`
`⟨a,b⟩+⟨a,c,b⟩=⟨a,b,a_1,c,b_1⟩`
`⟅a,a,b⟆uu⟅a,a,c⟆ = ⟅a,a,a,a,b,c⟆`
`⟅a,a,b⟆+⟅a,a,c⟆ = ⟅a,a,a_1,a_1,b,c⟆`
`(a,a,b)uu(a,a,c) =(a,a,b,a,a,c)`
`(a,a,b)+(a,a,c) = (a,a,b,a_1,a_1,c)`
L'union disjointe est une opération de construction très pratique. Considérons par exemple l'ensemble `E={a,b}` alors nous avons :
`E+E+E={a,b,a_1,b_1,a_2,b_2}=E uu E_1 uu E_2`
Les ensembles totalement ordonnés sont des arrangements. Grace à cette opération on peut concevoir facilement des ensembles totalement ordonnée plus sophistiqués tel que `NN"+"NN` où `ZZ"+"ZZ`
Si l'on part de la méta-hypothèse de l'existence d'une infinité d'éléments distincts pouvant être librement choisis, alors la succession de choix de tels éléments est représentée par sa liste. Et entendez-bien qu'il n'y a alors aucune perte d'information dans cette mise en forme.
Les structures sont ce qu'elles sont et peuvent réduire cette information, formant des structures quotients, quotientées par une théorie d'égalité ou un ensemble d'égalités entre listes.
Une telle structure construite selon ce principe est appelé une "structure de listes quotientée", et si elle admet une forme normale, nous lui donnons alors un deuxième nom, celui de "conformation". Quelles sont donc les conformations les plus simples, et peut-on les énumérer de façon exhaustive ?
La liste est la conformation mère.
L'arrangement s'obtient en quotientant la liste par la théorie d'égalité suivante où `vec x, vecy, vecz` désigne 3 séquences quelconques d'éléments (pouvant être vides), et où `a` désigne un élément quelconque :
`AAvecxAAvecyAAveczAAa,`
`(vec x,a,vec y,a,vec z) = (vec x,a,vec y,vec z)`
Notez que l'on entend par séquence `vec x` une portion contigüe de liste qui s'insère dans la liste où se trouve le symbole `vec x`. Ainsi, par exemple, si `vec x "=" (a,b)` alors `(vec x, c, vecx) "=" (a,b,c,a,b)`. On voit comment l'arrangement admet une forme normale, la plus petite représentation, qu'est la liste des premières occurrences.
Le sac s'obtient en quotientant la liste par la théorie d'égalité suivante :
`AAvecxAAvecyAAveczAAaAAb,`
`(vec x,a,vec y,b,vec z) = (vec x,b,vec y,a,vec z)`
En effet, l'ensemble de toutes les permutations de deux éléments engendre par composition toutes les permutations possibles. La théorie d'égalité ici présentée abolit l'ordre.
L'ensemble s'obtient en quotientant la liste par ces deux théories d'égalité :
`AAvecxAAvecyAAveczAAaAAb,`
`(vec x,a,vec y,a,vec z) = (vec x,a,vec y,vec z)`
`(vec x,a,vec y,b,vec z) = (vec x,b,vec y,a,vec z)`
L'ensemble admet une forme normale que si on admet l'existence d'un ordre système des éléments, c'est alors la liste des premières occurrences mis dans l'ordre système.
On limite la définition des conformations aux seuls listes quotientées admettant une forme normale. Quant il n'y a pas de possibilité de définir une forme normale cela devient un problème souvent indécidable, d'une autre nature et dans lequel il n'y a généralement pas de dénombrement possible.