Place de marché de troc

[ochaussavoine]

Soit une place de marché de troc contenant des ordres formulés de la manière suivante:
'Je voudrais céder telle valeur pour obtenir telle autre en échange.'
Une valeur est décrite par un nom (une qualité) et une quantité. Sans se préoccuper de la quantité, on considère que deux ordres coïncident si le nom de la valeur fournie par le premier est identique au nom de la valeur fournie par le deuxième. Les noms des valeurs fournies et reçues sont toujours distincts.
On recherche dans un livre qui contient N ordres les cycles d'échanges les plus courts formés par les coïncidences, en supposant que ces ordres utilisent n noms, et que tous les noms sont utilisés avec la même fréquence.
La question est la suivante:
Peut on quantifier le nombre de coincidences non réalisées en arrêtant la recherche quand on atteint une longueur de cycle L?

Intuitivement, on ne rate pas grand chose pour L très inférieur à n, et on en rate encore moins lorsque la répartition d'usage des noms est inégale.

Je pose cette question de combinatoire à laquelle je ne sais pas répondre dans le cadre d'un projet de place de marché de troc - un logiciel libre nommé openbarter - qui vise à déconnecter l'économie de la finance. Ca vous intéresse?