Précédent
 
Suivant
De l'algèbre
et du dénombrement
(3ème partie)

 

I) Dénombrement de listes, d'arrangements, de sacs, d'ensembles, et d'objets composites plus généraux par union, concaténation, et disjonction.

On doit également considérer les couples à permutation près {(x,y) " / " (x in A, y in B)" ou "(x in B, y in A}}, ainsi que les doublons {{x,y}" / " x in A, y in B, x!=y}

2.1) p-ensemble

Un `p`-ensemble est un sac où toutes les multiplicités sont inférieurs ou égale à `p`.

Un élément `a` est dit être une constante d'une suite infinie d'éléments si et seulement si elle est présente dans la suite une infinité de fois.

à faire

1-2) Multiensemble

Un multiensemble (ou sac) est une énumération fini d'éléments ou bien une suite infinie calculable d'éléments dans laquelle on fait abstraction de l'ordre d'énumération. Et les éléments peuvent y apparaitres plusieurs fois, voir une infinité de fois. On nomme la multiplicité d'un élément le nombre de fois qu'il apparait dans la suite. Le cardinal d'un multiensemble est égale à la somme des multiplicités.

On note entre accolades doubles `"{{"..."}}"` les éléments d'un sac (multiensemble) sachant qu'ils peuvent se répéter.

Les éléments de même noms se comportent comme des éléments indiscernables.

La base d'un multiensemble et l'ensemble des éléments présents au moins une fois. La multiplicité d'un élément est le nombre de fois qu'il s'y trouve. Un multiensemble est exactement défini par sa base et par une application de la base sur `NN^**uu{oo}`.

Le support d'un multiensemble est un ensemble qui comprend la base. Un multiensemble est déterminé par un support et par une application de ce support sur `NNuu{oo}`.

On note `ccS(E)` l'ensemble des sacs de support `E`.

On note `ccS^((p))(E)` l'ensemble des sacs de support `E` où les éléments ne peuvent être répétés qu'au plus `p` fois.

`|ccS^((p))(E)| = |E->{0,1,2,3...,p}| = |{0,1,2,3...,p}^E| = (p+1)^|E|`

On note `|ccS_q^((p))(E)|` l'ensemble des sacs de support `E` de cardinalité `q` et où les éléments ne peuvent être répétés qu'au plus `p` fois.

`|ccS_q^((p))(E)| =` Nombre de `|E|`-uplet d'éléments de `{0,1,2,3...,p}` dont la somme est égale à `q`.

Et on note `ccS_(<=q)^((p))(E)` l'ensemble des sacs de support `E` comprenant au plus `q` éléments et où les éléments ne peuvent être répétés qu'au plus `p` fois.

`|ccS_q^((p))(E)| =` Nombre de `|E|`-uplet d'éléments de `{0,1,2,3...,p}` dont la somme est inférieur ou égale à `q`.

 

II) Constructions itératives des 8 ensembles de relations binaires.

à faire

 

Etant donné une fonction f sur E et un élément a in E, la cloture est l'ensemble de toutes les compositions closes qu'il est possible de faire. Par exemple `<a,f"(.)"> = {: a,f(a),f(f(a)), f(f(f(a))), ... :}`

1) Bijection et permutation

La cloture d'une énumération d'éléments et de fonctions est l'ensemble de toutes les compositions closes qu'il est possible de faire avec. On la représente en mettant entre crochet l'énumération des éléments et fonctions générateurs. Par exemple considérons une fonction `f` sur `E` et un élément `a` appartenant à `E`, la cloture est l'ensemble de toutes les compositions closes qu'il est possible de faire avec :

`<a,f"(.)"> = `Base`( a,f(a),f(f(a)), f(f(f(a))), ... )`

Une permutation `f` est une bijection d'un ensemble fini `E` sur lui-même. Soit `|E|=N`. On numérote les éléments de `E` de tel sorte que nous avons : `E={1,2,3...,N}`.

La correspondance classique associe à chaque permutation `f`, l'arrangement `(:f(1),f(2),f(3)...,f(N):)` des `N` entiers tirés de `{1,2,3...,N}`.

Un cycle `c` est une permutation circulaire d'une partie `A sube E` de `n` éléments. C'est à dire vérifiant :

`AA x in A, "<"x,c"(.)>" = A`
`AA x!inA,   c(x)=x`

On représente le cycle par la suite des `n` éléments successifs `(x, f^1(x), f^2(x)..., f^(n-1)(x))`. Et il y a donc `n` représentations possibles d'un cycle de longueur `n`.

L'ordre d'un élément `x` est le plus petit entier `k` tel que `f^k(x)=x` et se note `o(x)` ou de manière explicite `o_f \(x)`.

L'orbite d'un élément `x` est l'ensemble des éléments `{x, f(x), f^2(x)..., f^(o(x)-1)(x)}` et se note `O(x)` ou de manière explicite `O_f \(x)`.

`|O_f \(x)| = o_f \(x)`

Toute permutation `f` partitionne `E` en `k` orbites. Les orbites de `1` éléments correspondent au points fixes. La sommes des cardinaux des orbites est égale au cardinal de `E`

La correspondance de Foata associe chaque permutation `f` à la liste des cycles disjoints `(c_1,c_2,c_3...c_k)` correspondant à chaque orbite. La rerprésentation est unique si on commence chaque cycle par l'entier le plus petit du cycle, et si on ordonne les cycles selon la valeur de ce premier entier.

Le nombre de Stirling de première espèce non signé `c(n,k)` correspond au nombre de permutations possibles, dans un ensemble de `n` élements, ayant exactement `k` cycles disjoints.

Si nous ajoutons un nouvelle élément `e` à l'ensemble, et que nous numérotons `n+1`, il peut être ajouté comme point fixe (un cycle à lui tout seul) à toute permutation dans un ensemble de `n` élements, et ayant `k-1` cycles, pour produire une permutation du genre `(...)(...)....(e)`. Et il peut être ajouté dans toute permutation dans un ensemble de `n` élements, et ayant `k` cycles, dans un de ses cycles. Dans ce cas, si le cycle est de `m` éléments, il y a exactement `m` façons distinctes d'ajouter cet élément. Exemple : pour le cycle `(a,b,c)`, il y a `(a,e,b,c)`, `(a,b,e,c)`, `(a,b,c,e)`. Et donc, en ajoutant toutes les façons dans chaque cycles, il y a exactement `n` façons d'ajouter l'élément `e`. Cela se traduit par la relation de récurrence suivante :

`c(n+1,k) = c(n,k-1) + n c(n,k)`
`c(n,0)=0`
`c(0,n)=0`
`c(0,0)=1`

Cette relation de récurrence donne un algorithme de calcul efficace de ces nombres.

 

2) les relation d'équivalence

1-3) Relation d'équivalence

Une relation `R` de `G` sur `G` est une relation d'équivalence ssi :

`AA(x,y,z)inG^3,`

Réflexive : `xRx`
Symétrique : `xRy => yRx`
Transitive : `xRy" et "yRz => xRz`

Une relation d'équivalence partitionne `G` en classes d'équivalence, et réciproquement toutes partition de `G` défini une relation d'équivalence. Le nombre de relations d'équivalence distinctes sur `G` est égal au nombre de partitionnements de `G`. Ce nombre est appellé le `n`-ième nombre de Bell où `n=|G|`.

 

Le quotient `G"/"R` est l'ensemble des classes d'équivalence.

Soit une application `f` de `A` vers `B`. L'application `f` induit une relation d'équivalence sur `A`. On dira que `x` et `y` sont `f`-équivalent ssi `f(x)=f(y)`.

3) Le nombres de Bell `B(n)` correspondent aux nombres de partitionnements possibles d'un ensemble de `n` éléments ou, ce qui revient au même, au nombre de relations d'équivalence sur un ensemble de `n` éléments.

`B(n) = sum_(k=1)^n S(n,k)`

 

4) Bijection de Joyal

5) Nombre harmonique

6) Nombre de Catalan

 

 

6) L'inférence de type

De même qu'en programmation, l'inférence de type va permettre de déterminer le type par défaut des variables utilisées.

Par exemple si nous posons une relation R de A vers B, alors l'expression xRy est équivalente à l'expression suivante : `xRy` et `x in A` et `y in B`.

 

D'autre part, un ensemble `E` peut être interprété comme une propriété ; vrai si `E` est non vide, et fausse si `E` est l'ensemble vide.

 

Dénombrement des arbres, des graphes (multi-ensemble)

Langage régulier (succession, réunion, intercection) - via les compositions de relations.

 

17) Algorithme de réfutation

Etant donné une propriété, il existe 2 problèmes, celui du dénombrement et celui de l'algorithme efficace pour réfuter la propriété.

En étudiant la théorie de la bijection, on trouve 4 axiomes que sont les qualités d'être partout définie, d'être déterministe, d'être surjectif et d'être injectif. (L'inverse d'une relation surjective est une relation partout définie. L'inverse d'une relation injective est une relation déterministe). Il y a donc 4 axiomes pertinents, pouvant être affirmé ou réfuté, ce qui donne `2^4 = 81` propriétés pertinentes possibles. Et pour chacune de ces propriétés nous savons dénombrer grâce à la table du chapitre II-13. Il faut maintenant établir un algorithme efficace de réfutation. L'algorithme est un programme et il se base sur le graphe que représente la relation. On étudie le cas générale de relations définies sur `E`.

Partout défini

Pour réfuté le partout défini il faut trouver un élément qui ne possède pas d'arcs partant. On part d'un premier élément et on suit une heuristique pour parcourir le graphe à le recheche du contre exemple. Les opérations que l'on peut faire son ls suivants :

  1. appliquer un programe à chaque élément de e jusqu'à une condition.
  2. calculer le nombre de successeurs.
  3. calculer le nombre de predecesseurs.
  4. choisire le premier successeur.
  5. choisir le premier prédécesseur.
  6. appliquer un programe à chaque successeur de e jusqu'à une condition.
  7. appliquer un programe à chaque prédecesseur de e jusqu'à une condition.

Seul la non-surjection et le non-partout-défini ont la propriétée de se conserver par composition, c'est à dire si `R` et `S` vérifie cet axiome alors `RS` vérifie encore cet axiome. Le non-déterminisme et la non-injectivité ne se conservent pas par composition.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Si on reprend la théorie la bijection, en procédant à la négation de la théorie, on obtient la théorie de la non bijection. Et cette théorie se subdivise canoniquement en 9 axiomes comme suit :

`(A "==" B) = { R"∈"ccP(A×B)" / "`
        `AAxEEy,  xRy,`    
        `AAxAAyAAz,  xRy` et `xRz  =>  y"="z`  
        `AAxEEy,  yRx`
        `AAxAAyAAz,  xRz` et `yRz  =>  x"="y`
`}`

Mise en forme ET-OU

`(A "==" B) = { R"∈"ccP(A×B)" / "ET`
        `AAxEEy,  xRy,`    
        `AAxAAyAAz,  ¬ xRy` ou `¬ xRz` ou `y"="z`
        `AAxEEy,  yRx`
        `AAxAAyAAz,   ¬ xRz` ou `¬ yRz` ou `x"="y`
`}`

La négation s'obtient en inversant les quantificateurs "AA" avec les "EE", les "et" avec les "ou", et en inversant chaque littéraux.

`(A ¬ "==" B) = { R"∈"ccP(A×B)" / "OU `
        `EExAAy,  ¬ xRy,`    
        `EExEEyEEz,  xRy` et `xRz` et `¬ y"="z`
        `EExAAy,  ¬ yRx`
        `EExEEyEEz,   xRz` et `yRz` et `¬ x"="y`
`}`

Regroupement des EE

`(A ¬ "==" B) = { R"∈"ccP(A×B)" / "EE(a,b,c,d,e,f,g,h), OU`
        `AAy,  ¬ aRy,`    
        `bRc` et `bRd` et `¬ c"="d`
        `AAy,  ¬ yRe`
        `fRh` et `gRh` et `¬ f"="g`
`}`

Regroupement des AA

`(A ¬ "==" B) = { R"∈"ccP(A×B)" / " EE(a,b,c,d,e,f,g,h)AA(x,y), OU`
        `¬ aRy,`    
        `bRc` et `bRd` et `¬ c"="d`
        `¬ yRe`
        `fRh` et `gRh` et `f"="g`
`}`

Distribution des OU sur les ET

`(A ¬ "==" B) = { R"∈"ccP(A×B)" / " EE(a,b,c,d,e,f,g,h)AAx`
        `¬ aRx,` ou `bRc` ou `¬ xRe` ou `fRh`
        `¬ aRx,` ou `bRc` ou `¬ xRe` ou `gRh`
        `¬ aRx,` ou `bRc` ou `¬ xRe` ou `¬ f"="g`
        `¬ aRx,` ou `bRd` ou `¬ xRe` ou `fRh`
        `¬ aRx,` ou `bRd` ou `¬ xRe` ou `gRh`
        `¬ aRx,` ou `bRd` ou `¬ xRe` ou `¬ f"="g`
        `¬ aRx,` ou `¬ c"="d` ou `¬ xRe` ou `fRh`
        `¬ aRx,` ou `¬ c"="d` ou `¬ xRe` ou `gRh`
        `¬ aRx,` ou `¬ c"="d` ou `¬ xRe` ou `¬ f"="g`
`}`

La propriété de non bijection se décompose donc en 9 axiomes :

`(A ¬ "==" B) = { R"∈"ccP(A×B)" / " EE(a,b,c,d,e,f,g,h)`
        `AAx,  ¬ aRx,` ou `bRc` ou `¬ xRe` ou `fRh`
        `AAx,  ¬ aRx,` ou `bRc` ou `¬ xRe` ou `gRh`
        `AAx,  ¬ aRx,` ou `bRc` ou `¬ xRe` ou `¬ f"="g`
        `AAx,  ¬ aRx,` ou `bRd` ou `¬ xRe` ou `fRh`
        `AAx,  ¬ aRx,` ou `bRd` ou `¬ xRe` ou `gRh`
        `AAx,  ¬ aRx,` ou `bRd` ou `¬ xRe` ou `¬ f"="g`
        `AAx,  ¬ aRx,` ou `¬ c"="d` ou `¬ xRe` ou `fRh`
        `AAx,  ¬ aRx,` ou `¬ c"="d` ou `¬ xRe` ou `gRh`
        `AAx,  ¬ aRx,` ou `¬ c"="d` ou `¬ xRe` ou `¬ f"="g`
`}`

 

 

 

 


Dominique Mabboux-Stromberg

 

<script type="text/javascript"
src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=AM_HTMLorMML-full">
</script>