Bonjour,
Pour des travaux en informatique fondamentale je suis confronter à un sous problème combinatoire qui me prend littéralement la tête, aussi, je me suis dit que peut être que l'un d'entre vous saurait s'il existe un peu de littérature sur quelque chose de similaire (six semaines que je cherche sans trouver)
Le voici exposé de la manière la plus claire que j'ai pu:
rq: j'écris "truc_i" pour dire "truc" indicé par i.
Soit un ensemble de trois éléments S={#,0,1} partiellement ordonné par '=<' tel que:
# =< 0
# =< 1
0 =< 0
1 =< 1
Les éléments 0 et 1 ne sont pas comparables.
On définit le produit cartésien de façon classique, et on définit un ordre sur les n-uplets tel que:
(x_1....x_n) =< (y_1....y_n) si et seulement si pour tout i de 1 à n, x_i =< y_i
Problème: Pour un n quelconque, combien d'ensembles E_i inclus dans S^n satisfont les conditions suivantes:
1- Quelque soit i, les n-uples de E_i sont deux à deux incomparable par la relation =<
2- Quelque soit x le n-uple de S^n sans occurrence de #, il existe un élément y de E_i tel que y=<x
Si l'on définissait un ensemble B={0,1}, le problème reviendrait à demander le nombre de sous ensembles E de S^n couvrant B^n, tel que E ne contient pas d'éléments comparables (car dans ce cas là, la couverture serait considérée comme la même que celle qui ne prend que le plus petit élément du couple comparable).
La moindre piste où indication est la bienvenue.
-----