Accueil
Suivant

De l'algèbre
et du dénombrement

 

On part du point de vue élémentarien où tout est calcul. Puis dans une spirale exploratrice ascendante, on revisite les bases de l'algèbre en réordonnant les définitions et en créant des interconnexions à chaque tour de la spirale. Nous revisitons ainsi les thèmes récurrents et pour chacun d'eux nous refrayons sans cesse nos pérégrinations en les complétants du savoir des autres thèmes.

Les mathématiques élémentariennes sont jumelles de l'informatique, n'usant comme seul fondement le langage et la programmation.

La formalisation des démonstrations entraine une complexité qui nuit à la compréhension globale noyant l'important dans le détail. Mais le choix d'un langage adapté résoud d'autant cette complexité. Ne dit-on pas que l'exposé d'un problème dans un langage adapté constitue la moitier de sa résolution ?

Au départ, toutes les structures sont finies. Puis, usant de la capacité énumérative des programmes, on construit des structures infinies, désignées par les programmes qui les énumèrent, et qui eux, sont de taille finie.

1) Élément

Un élément est une construction dans un langage d'opérateurs, qui sert de référence pour désigner toute chose que nous créons.

Du point de vue élémentarien, un élément ne peut contenir qu'une quantité finie d'information.

2) Liste

Le premier type d'assemblage que l'on conçoit sont les listes. Et dans un premier temps on ne concidèrera que des listes dont les éléments ne sont pas des listes.

On note entre parenthèse `(a,b,a)` les éléments d'une liste sachant qu'ils peuvent être répétés plusieurs fois et que l'ordre compte, la liste n'est pas commutative, ses éléments sont mis dans un ordres précis, toutes permutations de deux de ses éléments distincts change la liste. Et dans l'exemple, rien n'empêche que `a` puisse être égale à `b`.

Chaque liste finie possède un cardinal entier qui est le nombre d'éléments, égaux ou distincts, qu'elle contient. Soit une liste `L`, on note sa taille ou son cardinal `|L|`. Exemple `|"("a,b,a")"|=3`.

Chaque liste possède une base qui est l'ensemble des éléments présents au moins une fois dans la liste. Par exemple, la base de `"("a,b,a")"` est égale à `{a,b}`.

Les listes sont construites par des programmes. Un programme est par principe de taille finie, mais il peut énumérer une liste infinie. Dans le cas des listes finies, la liste elle-même constitue un programme qui l'énumére.

La liste vide se note `()` et constitue un élément particulier, et nous avons `|()|=0`.

3) Ensemble

Première définition : un ensemble fini est une liste finie d'éléments à permutation près et à répétition près. Deuxième définition : un ensemble fini est une liste finie d'éléments distincts à permutation près. Ces deux définitions rendent pertinante la définition de deux objets intermédiaires en terme de généralité que sont la liste d'éléments distincts appelé arrangement et le multiensemble ou ensemble pouvant contenir plusieurs fois le même élément, appelé sac.

On note entre accolades `{...}` les éléments d'un ensemble sachant que l'ordre n'y a pas d'importance mais que les éléments doivent nécessairement être deux à deux distincts. Ainsi l'expression `{a,b,c}` signifie que `a!=b` et `a!=c` et `b!=c`.

Chaque ensemble fini possède un cardinal entier qui est le nombre d'éléments qu'il contient. Soit un ensemble `E`, on note son cardinal `|E|`. Exemple `|{a,b}|=2`.

L'ensemble vide se note `{ }` et se note aussi parfois par `Ø={ }`. Il constitue un élément particulier, et nous avons : `|{ }| = |Ø| = 0`.

4) Sac

Un sac est une liste d'éléments à l'ordre près. On note entre double accolades `⦃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. Et dans l'exemple, rien n'empêche que `a` puisse être égale à `b`.

Chaque sac fini possède un cardinal entier qui est le nombre d'éléments, égaux ou distincts, qu'il contient. Soit un sac `S`, on note son cardinal `|S|`. Exemple `|⦃a,a,b⦄|=3`

Chaque sac possède une base qui est l'ensemble des éléments présents au moins une fois dans le sac. Par exemple, la base de `⦃a,a,b⦄` est égale à `{a,b}`.

Le sac vide se note par `⦃⦄`, et nous avons `|⦃⦄|=0`

Notez qu'un ensemble est un sac.

5) Arrangement

Un arrangement est une liste d'éléments distincts. On note entre braquettes `(:a,b,c:)` les éléments d'un arrangement sachant qu'ils doivent nécessairement être distincts et que l'ordre compte, l'arrangement n'est pas commutatif, ses éléments sont mis dans un ordre précis. Toutes permutations de deux de ses éléments change l'arrangement. Par exemple, l'expression `(:a,b,c:)` signifie que `a!=b` et `a!=c` et `b!=c` et consitue un arrangement distinct de `(:b,a,c:)`.

Chaque arrangement fini possède un cardinal entier qui est le nombre d'éléments qu'il contient. Soit un arrangement `A`, on note son cardinal `|A|`. Exemple `|(:a,b,c:)|=3`

L'arrangement vide se note par `(::)`, et nous avons `|(::)|=0`

Notez qu'un arrangement est une liste.

6) Union disjointe `+`

On doit pouvoir écrire sans ambiguité une opération fondamentale qu'est l'ajout d'un nouvel élément à un ensemble. L'ajout d'un nouvel élément `e` à un ensemble `A` se note :

`A+{e}`

Mais attention, cette expression affirme en même temps que `e !in A`. Et d'une manière plus générale, la somme de deux ensembles `A+B` signifie en même temps que `B` est disjoint de `A`.

La même opération s'applique aussi pour les sac. Elle ajoute les éléments pouvant être multiples mais affirme en même temps qu'ils sont distincts de ceux appartenants au premier membre. Exemple :

`⦃a,a,b⦄ + ⦃c,c,d⦄ = ⦃a,a,b,c,c,d⦄`

Cette expression affirme en même temps que `c!=a` et `c!=b` et `d!=a` et `d!=b`. Et d'une manière plus générale, la somme de deux sacs `S+R` signifie en même temps que `R` est disjoint de `S` ou plus exactement que la base de `R` (qui est l'ensemble des éléments présent au moins une fois dans `R`) et disjointe de la base de `S`.

L'union se distingue dans son fondement de la concaténation. C'est pourquoi lorsqu'on étendra cette opération aux listes et arrangements, on choisira de maintenir cette distinction faisant que par exemple l'expression `(a,b)+(c,d)` désignera un type plus générale d'objet dont la descritpion microscopique se fera par l'ensemble de ses états microscopiques `{(a,b,c,d), (c,d,a,b)}`, et où les conditions d'inégalitées sont les mêmes que dans le cas d'une union disjointe d'ensembles, c'est à dire pour l'exemple `c!=a` et `c!=b` et `d!=a` et `d!=b`.

7) Différence exacte `-`

De même, on doit pouvoir écrire sans ambiguité une opération fondamentale qu'est le retrait d'un élément présent dans un ensemble. Le retrait d'un élément présent `e` d'un ensemble `A` se note :

`A-{e}`

Mais attention, cette expression affirme en même temps que `e in A`. Et d'une manière plus générale, la différence de deux ensembles `A-B` signifie en même temps que `B` est inclus dans `A`.

On adopte le symbole de différence exacte `-`. Ainsi `A-B` représente l'ensemble des éléments de `A` qui ne sont pas dans `B` et en même temps, affirme que `B sube A`.

La même opération s'applique aussi pour les sac. Elle enlève ou réduit la multiplicité des éléments mais affirme en même temps qu'ils sont présents au moins en nombre qu'il faut pour pouvoir les retirer. Exemple :

`⦃a,a,a,b,b,c⦄ - ⦃a,b,b⦄ = ⦃a,a,c⦄`

Les opérations d'union disjointe `+` et de différence exacte `-` ont une priorité syntaxique égale et s'évaluent conventionnellement de gauche à droite faisant que l'expression `A-B+C` signifie précisement `(A-B)+C` et `B sube A` et `C` disjoint de `A-B`, et finalement correspond à la substitution dans l'ensemble `A` d'une partie `B` par une partie `C`.

Par exemple, l'expression `E-{a}+{b}` correspond à une substitution dans `E` de l'élément `a` par l'élément `b`, et affirme que `a in E` et que `b !in E"-"{a}`.

8) Inclusion stricte `sub`

Il est utile d'adopter une notation de la relation d'ordre qu'est l'inclusion sur le même modèle de la relation d'ordre plus petit ou égale. C'est pourquoi on réseve le symbole `sub` pour désigner l'inclusion stricte de façon analogue à `<`, et le symbole `sube` pour désigner l'inclusion de façon analogue à `<=`. Notez que cela change la signification du symbole `sub` tel qu'il était jusqu'alors utilisé.

La priorité syntaxique des relation d'ordres est la plus faible juste au dessus des relations d'égalité, d'équivalence et d'implication.

Ainsi pour tout ensemble `A`, nous avons :

`A sub A+{e}`
`A sube A uu {e}`

Les formes négatives s'expriment en barrant par un slash le symbole.

L'expression `A ⊄ B` signifie que `A` n'est pas inclus strictement dans `B`, c'est à dire que soit `A` est égale à `B` ou soit il existe un élément de `A` qui n'est pas dans `B`.

L'expression `A ⊈ B` signifie que `A` n'est pas inclus dans B`, c'est à dire qu'il existe un élément de `A` qui n'est pas dans `B`.

9) Extension élémentaire et duplication

Peut-t-on créer quelque chose ex nihilo ? on ne répondra pas à cette question. L'approche mathématique est plus prudente. Elle utilise l'extension élémentaire c'est à dire l'ajout d'un nouvel opérateur qui enrichi son langage. Et cette création peut être répétée.

On crée 3 éléments en les nommant pour la première fois, par exemple `u, v, w`, ce qui enrichie le langage de trois opérateurs générateurs d'arité zéro. L'extension est intérieur à un ensemble `A` si on ajoute la condition `(u in A)` et `(v in A)` et `(w in A)`, auquel cas ces 3 éléments jouent le rôle de variables désignant des éléments inconnues dans `A`. Et la plus part du temps la condition est implicite, les éléments inconnues sont considérés appartenant à la structure. Dans ces deux cas, l'ensemble ou la structure étant énuméré, il n'y a donc pas de création d'éléments ni d'extension élémentaire. Par contre, en l'absence de telles conditions, l'extension est dite extérieur, c'est à dire qu'elle ouvre la possibilité de désigner d'autres éléments, non encore désignés jusqu'a présent, bien entendu si cela ne contredit pas la théorie en cours. C'est pourquoi dans l'optique d'accéder à de nouveaux objets mathématiques on peut être amené à renoncer à des parties de la théorie en cours. Les éléments étants des compositions closes d'opérateurs générateurs, l'ajout d'opérateurs générateurs au langage va démultiplier les possibilités de construction. Et si la théorie en cours ne reduit pas toutes ces constructions à des éléments déjà existant alors cela crée de nouveaux éléments. Autrement dit le langage s'agrandit et la structure également. L'extension élémentaire correspond donc à l'agrandissement d'une structure en ajoutant des éléments générateurs à son langage.

Souvent on a recours à une numérotation des nouvelles variables telle que par exemple `e_1, e_2, e_3`, et on les délimite comme appartenant à un ensemble connue ou bien implicitement à la structure. Dans ce cas, il ne s'agit pas d'une extension élémentaire. Cela correspond à une application de `NN` vers l'ensemble en question ou la structure, `n|->e_n`, associant à chaque entier `n` un élément inconnu dénommé `e_n`.

Mais on peut aller au delà et procéder à une extension élémentaire. Cela associe alors à chaque entier `n` un nouvel opérateur générateur d'arité zéro `e_n` qui est ajouté au langage de la structure. Tout se passe dans ce cas comme si `e` était une application de `NN` vers l'exterieur, et que `⦃e_1,e_2,e_3,...⦄` formait un sac. Notez qu'il n'y a aucune théorie nouvelle concernant ces éléments et qu'ils peuvent donc être égaux entre eux d'où le regroupement en sac, et qu'ils peuvent aussi être égaux à des éléments déjà connus. On les qualifie d'exterieurs car ils ont la possibilité de constituer de nouveau éléments si la théorie en cours le permet, et on procède à l'extension élémentaire en agrandissant la structure par l'ajoutà son langage, de ces nouveaux opérateurs générateurs .

On fondent nos constructions mathématiques de prime abord dans le langage logique du premier ordre, c'est à dire dans un langage où les éléments sont tous des compositions closes d'opérateurs générateurs et où les variables sont toutes du même type. Puis on accède à un langage logique d'ordre supérieur en introduisant différents types d'éléments et de variables pouvant possèder une arité supérieur à zéro. Puis nous munissons le langage d'un mécanisme d'inférence des types.

A toute théorie mathématique du premier ordre correspond un langage du premier ordre et une structure qui concrétise la théorie. Le langage comprend les éléments de bases de toutes constructions. Il est composé d'opérateurs générateurs et de prédicats générateurs. Les éléments sont des constructions finies du langage, et forme ce que l'on appelle en informatique, une implémentation des données, une façon mise en oeuvre par une machine de mémoriser les données.

Il est toujours possible de créer une structure par duplication, simplement en dupliquant tous les termes du langage utilisé.

Considérons un ensemble `A = {a,b,c}`. Notez que cette expression affirme que les éléments `a,b,c` sont distincts. On crée un double de cet ensemble en le nommant pour la première fois par exemple  : `A'`.

`A={a,b,c}`
`A'={a',b',c'}`

Pour cela nous avons utilisé un foncteur, c'est à dire une application qui à chaque opérateur générateur ou prédicat générateur du langage renvoie un opérateur générateur ou prédicat générateur d'un autre langage. Le foncteur permet ainsi de traduire les données et propositions d'un langage à un autre.

La duplication de l'ensemble `A` en l'ensemble `A'` correspond à une bijection de `A` vers `A'` définie par `AAx in A,  x|->x'`. L'apostrophe constitue le foncteur, il est ici à prendre comme une fonction en notation française de `A` vers `A'`. L'ensemble d'arrivé n'est pas défini dans la première structure mais dans la seconde structure, c'est pourquoi elle correspond à une extension exterieure `A'`. La dénomination différente de ces nouveaux éléments `a',b',c'` n'entraine pas qu'ils soient distincts ni différents d'éléments déjà existants, mais la propriété d'ensemble de `A` qui est transportée par le foncteur en la propriété d'ensemble de `A'` entraine qu'ils sont distincts entre eux.

10) L'itération

Dans les mathématiques élémentariennes, le langage étant le seul fondement, il joue un rôle crucial. Il va, entre autre, permettre de formaliser complètement les démonstrations comme l'on fait le groupe N.Bourbaki, mais sans introduire l'immanence, l'infini inné, puisque tout doit être construit, puisque tout est langage. En ce sens davantage intuitionniste, la formalisation s'orientera d'abord dans la construction des structures et des programmes avant celles des autres démonstrations, sachant que la construction d'une structure constitue déjà la preuve de son existence.

De même qu'en programmation où l'on se dote d'outils permettant d'effectuer des calculs itératifs, on se dote en mathématique d'opérateurs appelé itérateurs qui transcrivent ces calculs itératifs, telles notamment des énumérations et des sommations.

On adopte une convention d'écriture qui réduit le nombre de variables muettes apparentes, dans le but de simplifier la complexité des formules.

Les itérateurs, telle que l'énumération ou la sommation, possédant des déclarations de variables, peuvent déclarer des variables déjà présentes dans la formule dans le contexte parent, ce qui occasionne un masquage de celles-ci, non pas dans leur déclaration, mais dans le corps de l'itération. Exemple :

`sum_(k=1)^k k = 1+2+...+k`

`sum_(k=1)^k sum_(k=1)^k k = (1+2+...+k) + (2+3+...+k) + (3+4+...+k) ... + (k)`

Cela permet d'écrire une telle sommation sous forme d'un opérateur pouvant être répété par exemple 3 fois comme suit, et qui constitue une factorisation programmative :

`(sum_(k=1)^k)^3 k     =    (k(k+1)(k+2)(k+3))/(4!)`

Et on utilise une autre convention d'écriture pour désigner si de besoin, une variable du contexte au dessus d'un masquage, en la préfixant du symbole `"@"`. Exemple :

`U_k = sum_(k=1)^k k/("@"k-k+1) = sum_(j=1)^k j/(k-j+1)`

`U_k = 1/k + 2/(k-1) + 3/(k-2) + ... + (k-2)/3 + (k-1)/2 + k`

11) Listes, sacs et ensembles de nouveaux éléments

La construction de listes peut se programmer itérativement. On peut répéter une duplication pour produire une liste. Par exemple voici une liste `U_k` de `k` éléments inconnus :

`U_k = (e_k)_(k=1)^k`

`U_k = (e_1,e_2,...,e_k)`

De même pour les sacs, voici un sac `S_k` de `k` éléments inconnus :

`S_k = ⦃e_k⦄_(k=1)^k`

`S_k = ⦃e_1,e_2,...,e_k⦄`

La différence entre le sac et la liste est que dans un sac l'ordre de la disposition des éléments n'a pas d'importance.

Ces éléments sont-ils nouveaux ? Oui en dénomination, mais rien n'indique qu'ils soient différents entre eux ou avec des éléments déjà connus. Mais ils peuvent constituer une extension élémentaire si on les ajoute au langage de la structure comme éléments générateurs. Dans ce cas là, on parlera de `k` nouveaux éléments.

De même pour les ensembles, voici un ensemble `A_k` de `k` éléments inconnus.

`A_k = {e_k}_(k=1)^k`

`A_k = {e_1,e_2,...,e_k}`

Notez alors que l'énumération se faisant entre accolades `{}`, cela signifie en plus que :

`AA i "∈"{1..k}  AA j "∈" {1..k}"\"{i},   e_i!=e_j`

Notez que `{1..n}` désigne l'ensemble des entiers allant de `1` à `n`.

L'union disjointe d'ensembles peut s'itérer et forme alors une sommation présidée par l'itérateur `sum`.

Cette sommation permet de programmer l'énumération d'un ensemble à partir de sa définition. Ainsi par exemple, l'ensemble des couples d'un premier élément appartenant à `A` et d'un second appartenant à `B` est égal à :

`{(x,y) " / " x "∈" A, y "∈" B}   =   sum_(x in A) sum_(y in B) {(x,y)}`

Considérons un ensemble fini `A`. Voici un ensemble `B` composé d'éléments inconnus distincts en nombre égale au cardinal de l'ensemble `A` :

`B = {e_k}_(k in A)`

Cela signifie qu'il existe une bijection de `A` vers `B` définie par `k|->e_k`. L'ensemble d'arrivé `B` regroupe les éléments inconnus, supposés distincts puisque énumérés entre accolades. Nous avons :

`B = sum_(k in A) {e_k}`

Voici un sac `S` composé d'éléments inconnus, mais non nécessairement distincts, en nombre égale au cardinal de l'ensemble `A`

`S = ⦃e_k⦄_(k in A)`

Cela signifie qu'il existe une application de `A` vers la base de `S` définie par `k|->e_k`. Les éléments `e_k` avec `k` parcourant `A` peuvent être égaux entre eux puisque réunis dans un sac. Nous avons :

`S = uuu_(k in A) ⦃e_k⦄`

12) Produit cartésien d'ensembles

Etant donné deux ensembles `A` et `B`. Le produit cartésien `A"×"B` désigne l'ensemble des couples composés d'un premier élément appartenant à `A` et d'un second élément appartenant à `B`.

`A×B = {(x,y) " / " x "∈" A,  y "∈" B}`

Si les ensembles `A` et `B` sont finis, nous avons :

`|A×B|` = `|A| |B|`

Si on effectue le produit avec le même ensemble `A` on écrira le résultat à l'aide d'une puissance.

`A^2 = A×A`
`|A^2| = |A|^2`

Et pour les puissances plus grandes, l'expression `A^n` désigne l'ensemble des `n`-uplets d'éléments de `A`.

`A^n = A×A×A×... n "fois" ...`
`|A^n| = |A|^n`

Notez que l'expression, « l'ensemble des couples de `A` » est synonyme de l'expression « l'ensemble des couples `A` » et affirme que `A` est un ensemble de couples et désigne cette ensemble `A`, tandis que l'expression « l'ensemble des couples d'éléments de `A` » désigne l'ensemble `A×A`. Parcontre si les éléments de `A` s'appellent des bidules et qu'il n'y en a pas d'autre ailleurs alors l'expression « l'ensemble des couples de bidules » désigne l'ensemble `A×A`. Grammaticalement, il y a une distinction entre un ensemble et l'appellation des éléments d'un ensemble. Le « de » dans un cas signifie « appartenant à » et dans l'autre cas il précise la définition du terme « couple ».

12.1) Calcul du nombre de couples `|A×B|`

S'il nous faut définir la multiplication sur les entiers `f(a,b)=ab` à partir de la seul addition, on peut le faire de deux façons différentes, soit par récurrence :

`f(a"+"1,b)=f(a,b)+b`
`f(0,b)=0`

ou soit par itération :

`f(a,b)=sum_(a=1)^a b`

Cela correspond à deux types de programmation ; la programmation récurcive et la programmation itérative, ici de complexité égale. Mais on est encore loin de l'algorithme de calcul plus efficace qui utilise la décomposition des entiers en une liste de chiffres selon une base donnée et qui partage le travail et les résultats intermédiaires évitant ainsi d'avoir à les recalculer plusieurs fois.

Le même raisonnement peut être fait à partir des ensembles `A` et `B` et à partir du procédé de construction des couples `A×B`.

12.2) Calcul par itération de `|A×B|`

On dévoile la programmation de l'énumération de `A×B` :

`A×B = {(x,y) " / " x "∈" A, y "∈" B}`
`A×B = sum_(x in A) {(x,y) " / " y "∈" B}`
`A×B = sum_(x in A) sum_(y in B) {(x,y)}`
`|A×B| = sum_(x in A) sum_(y in B) |{(x,y)}|`
`|A×B| = sum_(x in A) sum_(y in B) 1`
`|A×B| = sum_(x in A) b`
`|A×B| = ab`

12.3) Calcul par récurrence de `|A×B|`

On note :

`a = |A|`
`b= |B|`
`f(a,b) = |A×B|`

`f(a,b)` désigne le nombre de couples composés d'un élément d'un ensemble de cardinalité `a` et d'un élément d'un ensemble de cardinalité `b`.

En bref : Si on ajoute un nouvel élément `e`, les couples de `(A"+"{e})"×"B` comprennent les couples ne contenant pas `e`, c'est à dire les couples de `A"×"B`, et comprennent les couples contenant `e`, c'est à dire les couples de `{e}"×"B`. Cela se traduit par la relation de récurrence suivante : `f(a"+"1,b) = f(a,b)+b`

On dévoile la relation de récurrence sur les ensembles :

`(A"+"{e})×B = A×B + {e}"×"B`
`|(A"+"{e})×B| = |A×B| + |B|`
`f(a"+"1,b) = f(a,b) + b`
 
`{}×B = {}`
`|{}×B| = |{}|`
`f(0,b) = 0`

Conclusion :

`f(a"+"1,b) = f(a,b) + b`
`f(0,b) = 0`

Vous pourrez vérifier que cela définit bien le produit `f(a,b) = ab`

D'une manière générale, la distributivité de `**` par rapport à `+` au niveau des entiers se retrouve au niveau des ensembles en la distributivité de `×` par rapport à `+` où le `"+"` désigne l'union disjointe. Nous avons par exemple :

`(A"+"B)×C = A×C+B×C`

Et on accorde une priorité syntaxique au produit d'ensemble `×` plus forte que celle qu'on accorde à la somme disjointe `+`.

13) Ensemble des parties d'un ensemble

Soit un ensemble `E`, on note `ccP(E)` l'ensemble des parties de `E`. Et on note `E->{0,1}` l'ensemble des applications de `E` vers `{0,1}`.

Si `E` est un ensemble de `n` éléments alors nous avons :

`|E|=n`
`|ccP(E)| = |E->{0,1}| = 2^n`

On note `ccP_k(E)` l'ensemble des parties de cardinalité `k`. Le nombre de parties de `k` éléments d'un ensemble de `n` éléments correspond au coefficient binomial :

`|E|=n`
`|ccP_k(E)| = ((n),(k)) = (n!)/(k!(n-k)!)`

On note `ccP_(<=k)(E)` l'ensemble des parties de cardinalité au plus égale à `k`. Donc d'après les égalités précédentes nous avons :

`|E|=n`
`|ccP_(<=k)(E)| = sum_(k=0)^k |ccP_k(E)| = sum_(k=0)^k ((n),(k))`

Notez que par convention d'écriture, les opérateurs de somme possédant une déclaration de variables peuvent déclarer des variables déjà présentes dans le contexte parent, ce qui occasionne un masquage de celles-ci, non pas dans leur déclaration, mais dans le corps de la somme. Ainsi dans l'exemple, la somme déclare une variable `k` qui varie de `0` à `k`. La deuxième variable `k` fait donc référence à un contexte parent. Puis dans la somme, cette variable parente est masquée par la nouvelle variable `k` qui vient d'être définie par la somme.

Notez que l'expression « l'ensemble des parties de `E` » désigne `ccP(E)`, même si `E` est un ensemble de parties. La règle est la suivante. Quant les deux sens de « de » sont possibles ; « appartenant à `E` » et précision de la définition du terme sujet « sous-ensembles de `E` », alors c'est le sens précisant la définition qui est prioriraire. On dira « l'ensemble de parties `E` » pour désigner `E` en rappelant que c'est un ensemble de parties, et on dira « l'ensemble des parties de `E` » pour désigne `ccP(E)`.

13.1) Bijection canonique entre l'ensemble des parties de `E` et l'ensemble des aplications de `E` vers `{0,1}`

La fonction caractéristique d'un sous-ensemble `A` de `E` est par définition une application de `E->{0,1}` vérifiant :

`AA x "∈" E,   (x "∈" A <=> f(x) "=" 1)" et "(x"∉"A <=> f(x) "=" 0)`

Pour chaque ensemble `A` inclus dans `E`, il y a une et une seul application de `E` vers `{0,1}` qui soit une fonction caractéristique de `A`.

Pour chaque application `f` de `E` vers `{0,1}`, il y a un et un seul ensemble caractérisé `A={x " / "f(x)=1}` qui est inclus dans `E`.

Donc il existe bien une bijection canonique entre l'ensemble des parties de `E` noté `ccP(E)` et l'ensemble des aplications de `E->{0,1}`.

Notez qu'en notation ensembliste, `2` représente l'ensemble `{0,1}`, et `2^E` représente l'ensemble `ccP(E)` ainsi que l'ensemble `E->{0,1}` .

13.2) Calcul du nombre de sous-ensembles `|ccP(E)|`

S'il nous faut définir l'élèvation de 2 à une puissance entière `f(n)=2^n` à partir de l'addition et de la multiplication, on peut le faire de deux façons différentes, soit par réccurence :

`f(n"+"1)=2f(n)`
`f(0)=1`

ou soit par itération :

`f(n)=prod_(n=1)^n 2`

Cela correspond à deux types de programmation ; la programmation récurcive et la programmation itérative, ici de complexité égale. Mais on est encore loin de l'algorithme de calcul plus efficace qui utilise une décomposition des entiers pour partager le travail et qui permet ainsi de partager les résultats intermédiaires évitant ainsi d'avoir à les recalculer plusieurs fois.

Le même raisonnement peut être fait à partir de l'ensembles `E` et à partir du procédé de construction de l'ensemble des parties `ccP(E)`.

Dans un premier temps on ne s'intéressera qu'à la programmation récurvive qui ne nécessite pas de dévolopper un langage de programmation très riche.

On note :

`n = |E|`
`f(n) = |ccP(E)|`

`f(n)` désigne le nombre de parties d'un ensemble de `n` éléments.

En bref : Si nous ajoutons un nouvel élément `e`, l'ensemble des parties de `E"+"{e}` comprend les parties ne contenant pas `e`, c'est à dire les parties de `E`, et comprend les parties comprenant `e`, c'est à dire les parties de `E` chacune complétée avec l'élément `e`. Cela se traduit par la relation de récurrence suivante : `f(n"+"1) = f(n)+f(n)`

On dévoile la relation de récurrence sur les ensembles :

`ccP(E"+"{e}) = ccP(E) + {F "+" {e}" / " F "∈" ccP(E)}`
`ccP(E"+"{e}) = ccP(E) + sum_(F in ccP(E)) {F"+" {e}}`
`|ccP(E"+"{e})| = |ccP(E)| + |ccP(E)|`
`f(n"+"1) = f(n) + f(n)`
`f(n"+"1) = 2f(n)`
 
`ccP({ }) = {{ }}`
`|ccP({ })| = 1`
`f(0) = 1`

Conclusion :

`f(n"+"1) = 2f(n)`
`f(0) = 1`

Vous pourrez vérifier que cela définit bien l'élévation à la puissance `f(n) = 2^n`

13.3) Calcul du nombre de sous-ensembles de `k` éléments `|ccP_k(E)|`

On note :

`n = |E|`
`f(n,k) = |ccP_k(E)|`

`f(n,k)` désigne le nombre de parties de `k` éléments d'un ensemble de `n` éléments.

En bref : Si nous ajoutons un nouvelle élément `e`, l'ensemble des parties de `E"+"{e}` de `k` éléments comprennent les parties ne contenant pas `e`, c'est à dire les parties de `E` de `k` éléments, et comprennent les parties contenant `e`, c'est à dire les parties de `E` de `k"-"1` éléments chacune complétée avec l'élément `e`. Cela se traduit par la relation de récurrence suivante : `f(n"+"1,k) = f(n,k) + f(n,k"-"1)`

On dévoile la relation de récurrence sur les ensembles :

`ccP_k(E"+"{e}) = ccP_k(E) + {F "+" {e}" / " F "∈" ccP_(k"-"1)(E)}`
`ccP_k(E"+"{e}) = ccP_k(E) + sum_( F in ccP_(k"-"1)(E)) {F "+" {e}}`
`|ccP_k(E"+"{e})| = |ccP_k(E)| + |ccP_(k"-"1)(E)|`
`f(n"+"1,k) = f(n,k) + f(n,k"-"1)`
 
`ccP_0(E) = {Ø}`
`|ccP_0(E)| = |{Ø}|`
`f(n,0)=1`
 
`ccP_n(E) = {E}`
`|ccP_n(E)| = |{E}|`
`f(n,n)=1`

Conclusion :

`f(n"+"1,k) = f(n,k) + f(n,k"-"1)`
`f(n,0)=1`
`f(n,n)=1`

Cela correspond à la règle de Pascal pour calculer le coefficient binomial. `f(n,k) =((n),(k))`

Notez que sa forme récurcive représentée par la règle de Pascal est de complexité plus faible que sa forme itérative. Définir une fonction par des règles de récurences permettant de la calculer est aussi pertinent que de définir la fonction par un calcul itératif. C'est pourquoi on se satisfait de ce résultat.

13.4) Calcul du nombre de sous-ensembles d'au plus `k` éléments `|ccP_(<=k)(E)|`

On note :

`n = |E|`
`f(n,k) = |ccP_(<=k)(E)|`

`f(n,k)` désigne le nombre de parties d'au plus `k` éléments d'un ensemble de `n` éléments.

En bref : Si nous ajoutons un nouvel élément `e`, l'ensemble des parties de `E"+"{e}` d'au plus `k` éléments comprend les parties ne contenant pas `e`, c'est à dire les parties de `E` d'au plus `k` éléments, et comprend les parties contenant `e`, c'est à dire les parties de `E` d'au plus `k-1` éléments chacune complétée avec l'élément `e`. Cela se traduit par la relation de récurrence suivante : `f(n"+"1,k) = f(n,k) + f(n,k"-"1)`

On dévoile la relation de récurrence sur les ensembles :

`ccP_(<=k)(E"+"{e}) = ccP_(<=k)(E) + {F "+" {e}" / " F "∈" ccP_(<=k"-"1)(E)}`
`ccP_(<=k)(E"+"{e}) = ccP_(<=k)(E) + sum_(F in ccP_(<=k"-"1)(E)){F "+" {e}}`
`|ccP_(<=k)(E"+"{e})| = |ccP_(<=k)(E)| + |ccP_(<=k"-"1)(E)|`
`f(n"+"1,k) = f(n,k) + f(n,k"-"1)`
 
`ccP_(<=0)(E) = ccP_0(E) = {Ø}`
`|ccP_(<=0)(E)| = |{Ø}|`
`f(n,0)=1`
 
`ccP_(<=n)(E) = ccP(E)`
`|ccP_(<=n)(E)| = |ccP(E)|`
`f(n,n)=2^n`

Conclusion :

`f(n"+"1,k) = f(n,k) + f(n,k"-"1)`
`f(n,0)=1`
`f(n,n)=2^n`

Vous pourrez vérifier que cela définit bien `f(n,k) =k!((n),(k))= (n!)/((n-k)!)`

14) Ensemble d'ensembles

La construction de listes d'ensembles peut se programmer itérativement. On peut répéter une duplication d'un ensemble pour produire une liste d'ensembles. Par exemple voici une liste `bbbU_k` de `k` nouveaux ensembles :

`bbbU_k = (A_k)_(k=1)^k`

`bbbU_k = (A_1,A_2,...,A_k)`

La seul chose qui change est le type de l'objet dupliqué qui est un ensemble.

De même pour les sacs d'ensembles, voici un sac `bbbS_k` de `k` nouveaux ensembles :

`bbbS_k = ⦃A_k⦄_(k=1)^k`

`bbbS_k = ⦃A_1,A_2,...,A_k⦄`

La différence entre le sac et la liste est que dans un sac, l'ordre n'a pas d'importance.

De même pour les ensembles d'ensembles, voici un ensemble `bbbF_k` de `k` nouveaux ensembles :

`bbbF_k = {A_k}_(k=1)^k`

`bbbF_k = {A_1,A_2,...,A_k}`

Notez alors que l'énumération étant entre accolades `{}`, cela signifie en plus que :

`AA i "∈"{1..k}  AA j "∈"{1..k}"\"{i},   A_i!=A_j`

L'union disjointe d'ensembles peut s'itérer et forme alors une sommation présidée par l'itérateur `sum`.

Cette sommation permet de programmer l'énumération d'un ensemble d'ensembles à partir de sa définition. Ainsi par exemple :

`bbbF_k = {A_k}_(k=1)^k  =  sum_(k=1)^k {A_k}`

Le produit d'ensembles peut s'itérer et forme alors un produit présidée par l'itérateur `prod`. Ainsi par exemple :

`prod_(k=1)^k A_k = A_1×A_2×...×A_k`

15) Partitionnement

Etant donné un ensemble `E` de `n` éléments. Un partitionnement est une subdivision de l'ensemble `E` en `k` parties non vides, disjointes deux à deux, et dont la somme est égale à `E`. Le nombre de parties `k` étant compris entre `0` et `|E|`. Un partitionnement est constitué de l'ensemble de ces `k` parties.

L'ensemble de tous les partitionnements possibles de `E` se note `bbbP(E)`

`bbbP(E) = {{A_k}_(k=1)^k" / " sum_(k=1)^k A_k = E ,  prod_(k=1)^k A_k!=Ø ,   k"∈"{0..|E|}}`

L'ensemble de tous les partitionnements en `k` parties de `E` se note `bbbP_k(E)`

`bbbP_k(E) = {{A_k}_(k=1)^k" / " sum_(k=1)^k A_k = E ,  prod_(k=1)^k A_k!=Ø}`

L'ensemble des partionnements de `E` en un nombre de parties comprises entre `a` et `b` et où chaque partie possède entre `u` et `v` éléments, se note par :

`bbbP_(in{a..b})^(in{u..v})(E)`

Le nombre de Stirling de seconde espèce `S(n,k)` correspond au nombre de partitionnements possibles en `k` parties d'un ensemble de `n` élements.

15.1) Les familles et les cliques

Un ensemble d'ensembles s'appel une famille ou de façon redondante une famille d'ensembles. Les éléments d'une famille sont donc des ensembles et s'appellent les membres de la famille.

Un ensemble de familles s'appel une clique.

Considérons une famille d'ensembles quelconques telle que par exemple `bbbF = {A,B,C}`, et considérons un élément quelconque `e` n'appartenant à aucun membre de cette famille.

Pour désigner la famille d'ensembles obtenue en ajoutant à chacun des membres l'élément `e`, on procède par une définition d'ensemble utilisant une variable `X` qui va parcourir tous les membres de la famille :

`{A"+"{e},B"+"{e},C"+"{e}}   =   {X"+"{e}" / "X"∈" bbbF}`

Cette expression peut être mis sous forme itérative :

`{A"+"{e},B"+"{e},C"+"{e}}   =   sum_(X in bbbF){X"+"{e}}`

Pour désigner la clique de toutes les familles d'ensembles que l'on peut obtenir en ajoutant l'élément `e` à un seul membre de la famille `bbbF` à la fois, on procède par une définition d'ensemble utilisant une variable `X` qui va parcourir tous les membres de la famille :

`{{A"+"{e},B,C},{A,B"+"{e},C},{A,B,C"+"{e}}} = {bbbF-{X}+{X"+"{e}}" / "X "∈" bbbF}`

Cette expression peut être mis sous forme itérative :

`{{A"+"{e},B,C},{A,B"+"{e},C},{A,B,C"+"{e}}} = sum_(X in bbbF){bbbF-{X}+{X"+"{e}}}`

15.2) Calcul du nombre de partitionnement en `k` parties `|bbbP_k(E)|`

On note :

`n = |E|`
`S(n,k) = |bbbP_k(E)|`

`S(n,k)` désigne le nombre de partitionnements en `k` parties d'un ensemble de `n` éléments. Il est appellé nombre de Stirling de seconde espèce.

On pose `n>=1`.

En bref : Si nous ajoutons un nouvel élément `e`, l'ensemble des partionnements de `E"+"{e}` en `k` parties comprend les partitionnements où `e` est dans une partie singleton `{e}` et comprend les partitionnements où `e` n'est pas dans une partie singleton. Autrement dit, l'ensemble des partionnements de `E"+"{e}` en `k` parties comprend les partitionnements de `E` en `k"-"1` parties dans lesquels on ajoute la partie singleton `{e}`, et comprend les partitionnements de `E` en `k` parties dans lesquels on ajoute l'élément `e` dans une quelconque des `k` parties, et il y a exactement `k` façons distinctes d'ajouter cet élément. Cela se traduit par la relation de récurrence suivante :

`S(n"+"1,k) = S(n,k"-"1) + kS(n,k)`

On dévoile la relation de récurrence sur les ensembles :

`bbbP_k(E"+"{e}) = {bbbF"+"{{e}}" / "bbbF "∈" bbbP_(k"-"1)(E)}  + {bbbF-{X}+{X"+"{e}}}" / "X"∈" bbbF, bbbF "∈" bbbP_k(E)}`
`bbbP_k(E"+"{e}) = sum_(bbbF in bbbP_(k"-"1)(E)) {bbbF"+"{{e}}}  + sum_(bbbF in bbbP_k(E)) {bbbF-{X}+{X"+"{e}}" / "X"∈" bbbF}`
`bbbP_k(E"+"{e}) = sum_(bbbF in bbbP_(k"-"1)(E)) {bbbF"+"{{e}}}  + sum_(bbbF in bbbP_k(E)) sum_(X"∈" bbbF){bbbF-{X}+{X"+"{e}}}`
`|bbbP_k(E"+"{e})| = |bbbP_(k"-"1)(E)| + |bbbP_k(E)||bbbF|`
`S(n"+"1,k) = S(n,k"-"1) + kS(n,k)`
 
`bbbP_0(E) = Ø`
`|bbbP_0(E)| = |Ø|`
`S(n,0)=0`
 
`bbbP_n(Ø) = Ø`
`|bbbP_n(Ø)| = |Ø|`
`S(0,n)=0`
 
`bbbP_0(Ø) = {Ø}`
`|bbbP_0(Ø)| = |{Ø}|`
`S(0,0)=1`

Conclusion :

`S(n"+"1,k) = S(n,k"-"1) + kS(n,k)`
`S(n,0)=0`
`S(0,n)=0`
`S(0,0)=1`

Notez que `n>=1`

Cela définit le nombre de Stirling de seconde espèce `S(n,k)`


Dominique Mabboux-Stromberg