3.4 Modélisations par des structures arborescentes
99
lorsque k tend vers l’infini, la même proportion des expressions. En d’autres termes,
asymptotiquement lorsque le nombre de variables booléennes tend vers l’infini,
presque toute tautologie classique est une tautologie intuitionniste ; cf. [107]. Par
contre, Genitrini et Kozik [117] ont montré que ceci cesse d’être vrai lorsque les
connecteurs ∧ et ∨ ainsi que la constante FAUX sont autorisés, ce qui revient
à travailler sur des arbres dont les ensembles d’étiquettes, respectivement pour
les nœuds internes et pour les feuilles, sont d’une part {∨, ∧, →}, d’autre part
l’ensemble des variables booléennes auquel est ajoutée la constante FAUX. Dans
ce cas et toujours asymptotiquement par rapport à la taille des expressions, seules
62% des tautologies classiques sont aussi des tautologies intuitionistes.
3.4.2 Arbres de génération
Des arbres infinis apparaissent dans la méthode ECO (Enumerating Combinatorial
Objects), qui a pour but d’engendrer des objets combinatoires de taille donnée n,
à partir de ceux de taille n − 1. Nous présentons ces arbres, appelés arbres de
génération, sur un exemple de permutations à motif exclu, et renvoyons pour plus
de détails aux nombreux articles sur le sujet, par exemple Barcucci et al. [16, 17].
Soit donc une permutation sur n entiers, évitant le motif 123 : il s’agit d’un
élément σ ∈ S n tel qu’il n’existe pas de triplet i < j < k vérifiant σ (i) < σ (j) <
σ (k). Par exemple, σ 1 = (2413) évite le motif 123, mais non σ 2 = (2134).
Pour n = 1, la seule permutation est (1), et pour n = 2, ce sont les permutations
(21) et (12), obtenues à partir de la permutation σ = (1) en ajoutant l’entier 2 aux
deux places possibles, avant et après 1. Passons à n = 3 : nous insérons l’entier
3 dans la permutation (21) aux trois places possibles sans former le motif 123,
mais il n’y a que deux possibilités d’extension par 3 pour la permutation (12) : si
nous insérons 3 en fin, nous obtenons précisément le motif interdit 123. Il y a donc
seulement 5 nœuds, et non 6 = 3!, au niveau 3. 21 Si nous regardons maintenant
ce que donnent chacune de ces permutations au niveau suivant, qui correspond à
n = 4, la permutation (321) donne 4 permutations : quelle que soit la place où nous
insérons 4, nous n’obtiendrons jamais le motif 123. Par contre, les permutations
(213) et (312) ne donnent que trois permutations de taille 4, et les permutations
(231) et (132) seulement deux. Il y a donc 14 permutations de taille 4 évitant le
motif 123.
La figure 3.26 donne les permutations évitant 123 jusqu’à n = 4 ; lorsqu’une
permutation σ marque un nœud au niveau n ≥ 2, et que nous effaçons n, nous
retrouvons la permutation marquant son parent. Plus généralement, en prenant la
première génération à la racine, qui correspond à l’objet de taille 1 (sur notre
exemple, à la permutation (1)), les objets de taille n sont à la n-ième génération.
21 Dans cette section, le niveau d’un nœud est décalé de 1 ; avec cette convention les permutations
de S n sont alors au niveau n.
99
lorsque k tend vers l’infini, la même proportion des expressions. En d’autres termes,
asymptotiquement lorsque le nombre de variables booléennes tend vers l’infini,
presque toute tautologie classique est une tautologie intuitionniste ; cf. [107]. Par
contre, Genitrini et Kozik [117] ont montré que ceci cesse d’être vrai lorsque les
connecteurs ∧ et ∨ ainsi que la constante FAUX sont autorisés, ce qui revient
à travailler sur des arbres dont les ensembles d’étiquettes, respectivement pour
les nœuds internes et pour les feuilles, sont d’une part {∨, ∧, →}, d’autre part
l’ensemble des variables booléennes auquel est ajoutée la constante FAUX. Dans
ce cas et toujours asymptotiquement par rapport à la taille des expressions, seules
62% des tautologies classiques sont aussi des tautologies intuitionistes.
3.4.2 Arbres de génération
Des arbres infinis apparaissent dans la méthode ECO (Enumerating Combinatorial
Objects), qui a pour but d’engendrer des objets combinatoires de taille donnée n,
à partir de ceux de taille n − 1. Nous présentons ces arbres, appelés arbres de
génération, sur un exemple de permutations à motif exclu, et renvoyons pour plus
de détails aux nombreux articles sur le sujet, par exemple Barcucci et al. [16, 17].
Soit donc une permutation sur n entiers, évitant le motif 123 : il s’agit d’un
élément σ ∈ S n tel qu’il n’existe pas de triplet i < j < k vérifiant σ (i) < σ (j) <
σ (k). Par exemple, σ 1 = (2413) évite le motif 123, mais non σ 2 = (2134).
Pour n = 1, la seule permutation est (1), et pour n = 2, ce sont les permutations
(21) et (12), obtenues à partir de la permutation σ = (1) en ajoutant l’entier 2 aux
deux places possibles, avant et après 1. Passons à n = 3 : nous insérons l’entier
3 dans la permutation (21) aux trois places possibles sans former le motif 123,
mais il n’y a que deux possibilités d’extension par 3 pour la permutation (12) : si
nous insérons 3 en fin, nous obtenons précisément le motif interdit 123. Il y a donc
seulement 5 nœuds, et non 6 = 3!, au niveau 3. 21 Si nous regardons maintenant
ce que donnent chacune de ces permutations au niveau suivant, qui correspond à
n = 4, la permutation (321) donne 4 permutations : quelle que soit la place où nous
insérons 4, nous n’obtiendrons jamais le motif 123. Par contre, les permutations
(213) et (312) ne donnent que trois permutations de taille 4, et les permutations
(231) et (132) seulement deux. Il y a donc 14 permutations de taille 4 évitant le
motif 123.
La figure 3.26 donne les permutations évitant 123 jusqu’à n = 4 ; lorsqu’une
permutation σ marque un nœud au niveau n ≥ 2, et que nous effaçons n, nous
retrouvons la permutation marquant son parent. Plus généralement, en prenant la
première génération à la racine, qui correspond à l’objet de taille 1 (sur notre
exemple, à la permutation (1)), les objets de taille n sont à la n-ième génération.
21 Dans cette section, le niveau d’un nœud est décalé de 1 ; avec cette convention les permutations
de S n sont alors au niveau n.