UNE BIJECTION EXPLICATIVE DE

PLUSIEURS PROPRIÉTÉS DES PONTS

Germain Kreweras

Nous avons établi en 1970, par des dénombrements appropriés, que les ponts de portée n possédent notamment les propriétés suivantes [1].

(α) ceux qui ont k arches sont aussi nombreux que ceux qui commencent par k

étapes ascendantes. (β) ceux qui ont k paliers sont aussi nombreux que ceux qui ont n − k + 1 paliers. (γ) ceux de degré k sont aussi nombreux que ceux de hauteur k. J. Vaillé vient de définir sur l’ensemble P_{n} des ponts de portée n une bijection

assez simple ω qui fait correspondre à tout pont P ayant α arches, β paliers, et pour degré γ un pont ω(P) commençant par α étapes ascendantes, ayant n − β + 1 paliers et pour hauteur γ.

L’outil central consiste à coder P par une suite de n entiers dont le h-ième est la distance (verticale) à la diagonale, soit c_{h}, du point de départ de la h-ième étape horizontale. La bijection inverse ω^{−1} peut alors se décrire comme suit:

(1*) partir du code c_{1}c_{2} … c_{n} de ω(P), où l’entier λ apparaît i_{λ} fois.

(2*) construire un pont S (dit “pur”), de portée n, dont la λ-ième arche est formée de i_{λ} étapes descendantes, et appeler A_{λ} l’extrémité de la première étape horizontale de cette arche de S.

(3*) joindre A_{λ} à A_{λ+1}, en faisant correspondre une étape horizontale à chaque λ

et une étape verticale à chaque λ + 1. La mise bout à bout de ces chemins, complétée par les i_{1} + 1 premières étapes de

S et un prolongement jusqu’au point final (n, n), fournit le pont P.

La bijection ω fait en outre correspondre à l’opération appelée dérivation l’opération (introduite par Y. Poupard [2]) appelée compression.

References

[1] KREWERAS G., Sur les éventails de segments, Cahiers du BURO 15 (1970), 3–41.

[2] POUPARD Y., Sur les quasi-ponts, Cahiers du BURO 32 (1979), 3–20.

[3] VAILLÉ J., communication personelle.

Université Pierre et Marie Curie (Paris VI)