Dans une équipe de basket comptant 12 joueurs, la mésentente règne. Chaque joueur déteste le ou les joueurs qui ont un numéro adjacent au sien au point de refuser de jouer avec. Ainsi, l’entraîneur ne peut pas faire jouer en même temps le joueur n°1 et le joueur n°2. Une équipe de 5 joueurs valide, sera, par exemple, l’équipe composée des joueurs 1-3-5-7-9.

Combien ce pauvre entraîneur a-t-il de possibilités pour composer son équipe ?

Rappels sur les combinaisons

Pour compter le nombre d’équipes de 5 joueurs que l’on pourrait constituer si les joueurs s’entendaient tous, on peut utiliser les combinaisons.

Avec n! la factorielle de n:

n! = n.(n-1).(n-2). … .3.2.1

Dans notre cas, pour k=5 joueurs sélectionnés parmi les n=12 on a:

C₁₂⁵ = 12!/(5! x 7!) = 792

En effet, il existe 12 façons de choisir le premier joueur, puis 11 de choisir le second, etc … jusqu’au cinquième. Il y a donc 12!/7! = 95 040 façons (appelés arrangements) de choisir 5 joueurs parmi les 12 en tenant compte de l’ordre.

Mais pour composer une équipe, l’ordre n’a pas d’importance. Ainsi, dans nos 95 040 arrangements, il y aura aussi bien 1-2-3-4-5 que 5-4-3-2-1 (et bien d’autres), qui en pratique, correspondent à la même équipe.

Combien de fois est présente chaque équipe (ou combinaison) dans nos 95 040 arrangements ? Pour une équipe donnée, pour construire une version ordonnée, il y a 5 choix pour le premier élément de l’équipe, puis 4 pour le suivant, etc … jusqu’au dernier. Il y a donc 5! = 120 permutations possibles pour une liste de 5 joueurs donnée. Chaque équipe sera donc présente 120 fois dans nos 95 040 arrangements. C’est pourquoi le nombre de combinaisons est 95 040 / 120 = 792.

Léger détour: le triangle de Pascal

Les combinaisons apparaissent dans un être mathématique légendaire: le triangle de Pascal. En voici les premières lignes:

Ce triangle à de nombreuses propriétés passionnantes, reliées directement aux propriétés des combinaisons. Chaque ligne du triangle correspond aux combinaisons. La première ligne est C₀⁰. La seconde ligne est constituée de C₁⁰ et C₁¹. La troisième ligne contient C₂⁰, C₂¹ et C₂² etc …

Le triangle peut être construit par récurrence. Le premier et le dernier élément de chaque ligne sont des 1. Les autres éléments sont la somme des deux éléments au dessus de lui.

La somme des éléments d’une ligne est égal à 2ⁿ. En mettant en valeur les éléments pairs du triangle de Pascal, on fait apparaître un triangle de  Sierpiński.

De retour à nos ballons

Les combinaisons ne peuvent pas résoudre notre problème n’est-ce pas ? Nous voudrions éliminer des combinaisons celles contenant deux joueurs ayant des numéros adjacents. Cela paraît bien compliqué.

Abordons le problème différemment. Construire une équipe valide, c’est soit choisir les 5 joueurs qui participent, soit choisir les 7 joueurs qui n’en feront pas partie. Partons du principe que nous avons nos 7 joueurs exclus, mais que nous ne connaissons pas leur numéro. Représentons les par des E. Les 5 joueurs participant sont forcément à 5 des endroits marqués par des x:

x E x E x E x E x E x E x E x

Construire une équipe convenant, c’est donc choisir 5 x parmi les 8 présents. Il y a donc C₈⁵ = 56 équipes possibles.

On notera cette « combinaison avec contrainte » en faisant précéder le C d’un indice correspondant à l’écart minimum que l’on impose. Ainsi, nous venons de trouver:

Il est possible d’aborder le problème différemment, en définissant la combinaison avec contrainte par récurrence. Lorsqu’on ajoute un joueur, passant de n-1 à n, le nombre de combinaisons de p joueurs respectant la contrainte est égal au nombre de combinaisons de p joueurs parmi n-1 auquel on ajoute le nombre de combinaisons contenant le joueur rajouté. Une telle combinaison convient si elle ne contient pas le joueur n-1 et qu’elle est valable dans la sous équipe composée des n-1 (ou n-2 puisque n-1 n’en fait pas partie) premiers joueurs. D’où la formule suivante:

Afin de calculer pour n’importe quelle valeur de n et de p, on peut utiliser la formule ci-dessus en conjonction avec les valeurs suivantes:

et pour n > 1:

Généralisation

Les deux réflexions ci-dessus peuvent facilement être généralisées à un écart quelconque.

Commençons par la première. Si l’on veut choisir des joueurs en garantissant qu’il n’y a pas, dans l’équipe constituée, deux joueurs dont l’écart est inférieur ou égal à 2, on peut considérer qu’il faut choisir 5 emplacements x pour insérer les joueurs choisis, avec comme contrainte qu’il ne faut pas que deux x se suivent !

x E x E x E x E x E x E x E x

On a donc:

Et de même pour les écarts plus grands:

Il en est de même de la définition par récurrence qui peut être généralisée:

Programme

Voici un programme en python permettant de calculer simplement les combinaisons contraintes (ou non contraintes en fournissant 0 comme paramètre). Utiliser python2 pour l’exécuter. Lancer le programme sans paramètre permet d’obtenir l’aide.

On observera le temps important que prend le calcul de combinaisons d’ordre relativement peu élevé. Voici par exemple ce que j’obtiens pour ₂C₄₀¹⁰.

$ time python2 CombinaisonsContraintes.py 2 40 10
C_22_10 = 646646
2_C_40_10 = 646646
real    0m8.261s
user    0m8.143s
sys     0m0.027s

L’impact est encore plus important lorsque l’on veut afficher un triangle de Pascal.

Voici exactement le même programme en python, mais utilisant un dictionnaire pour mémoriser les combinaisons déjà calculées. Cela permet de calculer aisément des combinaisons pour des valeurs beaucoup plus élevées. On appelle cette technique la mémoïsation.

Cependant, pour des valeurs très élevées, le programme consommera beaucoup de mémoire. Il est alors intéressant de se demander comment obtenir les meilleurs performances, pour un « profil d’utilisation » donné et une consommation mémoire limitée.

Triangles généralisés

En utilisant le programme ci-dessus, on constate facilement que les triangles obtenus avec les combinaisons contraintes correspondent au triangle de Pascal à une différence près, les colonnes, à partir de la troisième, sont décalées vers le bas.

Pour aller plus loin

Concernant les combinaisons:
http://fr.wikipedia.org/wiki/Combinaison_(mathématiques)
http://fr.wikipedia.org/wiki/Coefficient_binomial
http://fr.wikipedia.org/wiki/Triangle_de_Pascal

Concernant la mémoïsation:
http://fr.wikipedia.org/wiki/Mémoïsation
http://sametmax.com/memoization-dune-fonction-python/