Ordres
et ensembles
blackiens.
Contexte
Les ordres de Black interviennent dans des domaines très
variés, aussi bien en matière de psychologie que
de statistiques ou encore de partitions planes. De nombreuses
représentations de ces ordres sont connues.
L'algorithme des pyramides leur est spécialement
dédié. Le problème
d'énumération auquel nous nous
intéressons ici a des applications immédiates en
théorie du choix social, mais sa résolution est
d'ordre purement combinatoire.
Définitions de base
1: Ordres et permutations
Fixons un ensemble de m objets, numérotés
1, 2,..., m.
On peut coder un ordre (total) sur ces objets par
une permutation p
de l'ensemble {1,...,m}.
Exemple:
Pour m
= 4,
l'ordre p
= 4213
est celui où l'objet numéro
4 est
classé en 1ere
position, 2 en 2e,
1 en 3e
et 3 en dernier.
2: Ordre blackien par rapport
à un ordre
donné
Un ordre p
est dit blackien par rapport à un
ordre de référence r
s'il existe k
dans {1,..., m}
tel que
rk,
rk-1,...,
r1
et rk,
rk+1,...,
rm
soient des sous-ordres de p.
Ceci revient à "replier" r
autour de rk.
On doit en particulier avoir p1
= rk.
Exemple:
Si m
= 4
et r =
1234,
les ordres blackiens par rapport à r
sont 1234, 2134, 2314, 2341, 3214, 3241, 3421, 4321 (pour k
= 1,2,2,2,3,3,3,4).
3: Ensembles blackiens
Un ensemble de n
ordres est dit blackien si chacun d'eux est blackien par rapport
à un ordre de référence commun.
Exemple:
Prenons encore m=4.
L'ensemble {1234, 2134, 2314} est blackien, pour l'ordre de
référence 1234 mais aussi pour 3214.
Objectif ultime
Trouver le nombre B(m)
des ensembles blackiens pour m
donné.
On compte facilement que B(2)
= 3, et à la main on
peut trouver B(3)
= 36.
En programmant un peu on obtient B(4)
= 2790. Après,
cela devient trop long.
On voudrait avoir une formule pour B(m).
Méthodes (et
objectifs intermédiaires)
Se ramener à l'énumération d'ensembles
plus
simples.
Programmer et observer.
Trouver diverses représentations des ordres et ensembles
blackiens.