On peut difficilement se représenter mentalement un hypercube en dimension $d,$ mais on peut déterminer le nombre de sommets de ses intersections avec un hyperplan de dimension $d – 1$ glissant perpendiculairement le long de sa diagonale principale.
Hypercube unitaire
La figure ci-contre contient des illustrations d’objets de dimension 0, 1, 2 et 3 respectivement. Pour nous dont les sens perçoivent trois (et seulement trois) dimensions, l’illustration du bas peut s’interpréter comme représentant un cube.
Un être ne percevant que deux dimensions qui observerait un cube ne verrait qu’un carré, que l’on peut interpréter comme la projection du cube sur l’une de ses faces. C’est l’objet de dimension maximale qu’il peut percevoir. Pour cet être, le carré serait l’équivalent du « cube » pour nous, et le cube serait l’équivalent de ce qu’on pourrait appeler un « hypercube ».
De façon analogue, en regardant un carré, l’être ne percevant qu’une dimension verrait un segment de droite, soit la projection du carré sur une droite parallèle à un de ses côtés. Pour cet être, le segment de droite serait l’équivalent de notre cube et le carré serait l’équivalent de notre « hypercube ».
Dans la suite du texte, on appelle hypercube $d$-dimensionnel, (aussi appelé d-cube) l’analogue de dimension d d’un cube (pour $d = 3$) et d’un carré (pour $d = 2$). Le 3-cube est donc le cube géométrique usuel. En projetant un $d$–cube selon l’une de ses dimensions, on obtient un hyperplan qui est de dimension $d-1$. Un hypercube dont les arêtes sont de longueur 1 est dit unitaire.
Les sommets d’un hypercube unitaire de dimension $d$ peuvent se représenter dans un système d’axes à d dimensions par un $d$-tuplet dont les composantes sont exclusivement des 0 et des 1. Ainsi, les coordonnées des sommets d’un carré unitaire dans un système d’axes en 2D sont (0, 0), (0, 1), (1, 0) et (1, 1). Celles des sommets d’un cube unitaire dans un système d’axes en 3D sont (0,0,0), (1,0,0), (0 ,1, 0), (0, 0,1), (1, 1, 0), (1 ,0, 1), (0, 1,1) et (1, 1,1).
Un d-cube a 2d/2= 2d –1 diagonales, chacune de longueur d. Nous appellerons diagonale principale celle joignant le sommet de coordonnées (0,0,0,…,0) au sommet de coordonnées (1,1,1,…,1).
Hyperplan glissant perpendiculairement sur la diagonale principale du $d$-cube
Considérons quelques cas. Étant donné un carré (2-cube), supposons une droite (hyperplan de dimension 1) se déplaçant perpendiculairement à la diagonale du carré et prenons une photo de l’intersection du carré et de cette droite à chaque fois qu’elle passe par au
moins un sommet du carré. On obtient les trois photos du tableau ci-contre.
On peut refaire le même exercice à partir du 3-cube en considérant un plan (hyperplan de dimension 2) qui glisse perpendiculairement à la diagonale principale du carré. On prend une photo de l’intersection de ce plan et du cube à chaque fois que le plan passe par au moins un sommet du cube. Les photos obtenues sont celles du tableau suivant.
De la même façon, l’hypercube de dimension 1 est un segment de droite unitaire. L’hyperplan correspondant est un point. En faisant glisser le point sur la droite et en prenant les photos des intersections lorsque le point passe par un sommet du segment de droite, on obtient deux photos de points.
Lorsque $d = 0$, on a un cas dégénéré où le 0-cube est simplement le point. Il n’y a alors pas d’hyperplan en jeu.
Le tableau ci-dessous résume les différents cas rencontrés.
On remarque que les nombres de sommets des objets géométriques figurant dans les diverses photos sont des nombres du triangle de Pascal (voir encadré Le triangle de Pascal). Pourquoi en est-il ainsi?
Puisque les hypercubes sont unitaires, les coordonnées des sommets de chacune des photos sont obtenues en dé- terminant le nombre de $d$-tuplets dont le nombre de 1 est p, pour p variant de 0 jusqu’à $n$. Ce nombre de $d$–tuplets est un nombre de combinaisons. Ainsi, pour $d=3$, le nombre de 1 dans les coordonnées d’un sommet peut être 0, 1, 2 ou 3, mais ce nombre est le même pour tous les sommets d’une photo particulière de l’intersection de l’hyperplan et de l’hypercube. Le tableau suivant donne le nombre de sommets des inter- sections du plan glissant perpendiculairement sur la diagonale principale d’un cube unitaire, ainsi que les coordonnées de ces sommets (On y utilise la notation des coefficients binomiaux – voir encadré Le triangle de Pascal).
Le triangle de Pascal nous permet de déterminer les sommets des intersections d’un hyperplan glissant perpendiculairement sur la diagonale principale d’un hypercube de dimension 4.
Le triangle de Pascal
Le triangle de Pascal est un tableau triangulaire donnant le nombre de combinaisons de $k$ objets choisis parmi $n$ objets distincts, noté $\begin{pmatrix}n \\ k \end{pmatrix}$1. L’illustration ci-haut représente les premières lignes du triangle arithmétique de Pascal.
Qu’entend-on par « combinaison » de $k$ objets choisis parmi $n$ objets distincts?
Considérons la forme d’un quintuplet
(_, _, _, _, _).
Combien de quintuplets comportant deux $a$ et trois $b$ peut-on écrire?
La façon longue de répondre à la question est l’énumération; on obtient:
\[(a, a, b, b, b), (a, b, a, b, b), (a, b, b, a, b), \\(a, b, b, b, a), (b, a, a, b, b), (b, a, b, a, b),\\ (b, a, b, b, a), (b, b, a, a, b), (b, a, b, b, a),\\ (b, b, b, a, a).\]
Il y a donc 10 quintuplets comportant deux $a$ et trois $b.$ En fait, on a choisi les positions occupées par les $a$ et on a inscrit $b$ dans les positions restantes. Il y a donc 10 combinaisons de 2 positions choisies parmi 5 pour placer les $a.$
En pratique, le nombre de combinaisons de $k$ objets choisis parmi n objets distincts est donné par
\[\displaystyle \begin{pmatrix}n \\ k \end{pmatrix}=\frac{n!}{(n-k)!k!’}\]
où
\[n! = n(n – 1)(n – 2)\times \ldots \times 3\times2\times1\]
et
\[0!=1.\]
Dans notre exemple, cela donne
\[\displaystyle \begin{pmatrix}5 \\ 2 \end{pmatrix}= \frac{5!}{(5−2)!2!}=\frac{5×4×3!}{3! ×2!}=\frac{5×4}{2×1}=10.\]
Il n’est pas nécessaire de calculer ces nombres un par un. Par exemple, on obtient facilement que
\[\begin{pmatrix}n \\ 0 \end{pmatrix}=\begin{pmatrix}n \\ 1 \end{pmatrix}=1.\]
Cela signifie que le nombre à chacune des deux extrémités de chaque ligne est 1. On peut aussi montrer que
\[\begin{pmatrix}n \\ 1 \end{pmatrix}=\begin{pmatrix}n \\ n-1 \end{pmatrix}=n.\]
Cela signifie que le second nombre à partir des extrémités de chaque ligne est le numéro de la ligne (en les numérotant à partir de 0).
La propriété de ces nombres la plus importante pour la construction du triangle est
\[\begin{pmatrix}n-1 \\ k-1 \end{pmatrix}+\begin{pmatrix}n-1 \\ k \end{pmatrix}=\begin{pmatrix}n \\ k \end{pmatrix},\]
ce qui signifie qu’un nombre sur la ligne $n$ (outre les 1 aux deux extrémités) est toujours la somme des nombres immédiatement à sa gauche et à sa droite sur la ligne précédente.
Prouvons la formule. On veut compter le nombre de sous-ensembles de $k$ objets parmi $n$.
Distinguons un élément arbitraire parmi les $n$ éléments. Les sous-ensembles sont alors de deux types:
- Ceux qui contiennent l’élément distingué, en nombre $\begin{pmatrix}n-1 \\ k-1 \end{pmatrix}$ car il faut choisir les autres éléments parmi les éléments non distingués.
- Ceux qui ne contiennent pas l’élément distingué, en nombre $\begin{pmatrix}n-1 \\ k \end{pmatrix}$ car il faut choisir les $k$ autres éléments parmi $n–1$ éléments non distingués.
On remarque facilement la symétrie du triangle: sur une ligne donnée, les mêmes valeurs apparaissent dans le même ordre à partir de la gauche et à partir de la droite. Ce que l’on décrit par
\[\begin{pmatrix}n \\ k \end{pmatrix}=\begin{pmatrix}n \\ n-k \end{pmatrix}\]
Cela vient du fait que choisir un sous-ensemble de $k$ objets parmi $n$, c’est la même chose que de choisir les $n–k$ objets qui ne sont pas dans le sous-ensemble. On note aussi que la somme $n$ des nombres sur la ligne $n$ est égale à $2^n.$
Du nombre de sommets à la forme de l’intersection
On a déterminé le nombre de sommets de l’intersection d’un hypercube avec un hyperplan glissant perpendiculairement à la diagonale principale. Mais quelle est la forme de cet objet? Un nombre de sommets ne détermine pas forcément une forme géométrique particulière. Ainsi, en 3D, on peut imaginer des formes géométriques fort différentes ayant six sommets (voir ci-contre).
Le triangle de Pascal peut encore venir à notre rescousse. Un nombre d’une ligne du triangle est la somme des deux nombres à sa gauche et à sa droite sur la ligne précédente. Ainsi, sur la ligne pour $n = 3$, le deuxième nombre est 3: c’est la somme du nombre 1 et du nombre 2 de la ligne précédente. Le nombre 1 représente un point et le nombre 2 un segment de droite. L’enveloppe convexe de ces deux objets est un triangle (voir encadré Enveloppe convexe).
Enveloppe convexe
L’enveloppe convexe d’un objet ou d’un regroupement d’objets géométriques est le plus petit ensemble convexe contenant ces objets. Un ensemble convexe est un ensemble de points dans lequel il n’y a pas de « creux », de parties « rentrantes ».
Dans un plan, l’enveloppe convexe d’un regroupement d’objets peut être comparée à la région limitée par un élastique, englobant tous les objets, et qu’on relâche jusqu’à ce qu’il se contracte au maximum.
Par exemple, si les objets dont on veut déterminer l’enveloppe convexe sont un segment de droite et un point, on imagine un élastique englobant ces deux objets. En relâchant l’élastique, la figure obtenue est un triangle; c’est l’enveloppe convexe d’un segment de droite et d’un point dans le plan. Il s’agit du contour de l’intersection de trois demi-plans, chacun déterminé par la droite passant par 2 des 3 points et contenant le troisième point.
L’idée est la même dans l’espace avec un ballon qui contient les objets (points, segments de droites et surfaces planes) dont on veut déterminer l’enveloppe convexe. En laissant se dégonfler le ballon jusqu’à ce qu’il soit en contact avec tous les sommets de ces objets, on obtient l’enveloppe convexe; c’est la surface de l’intersection de tous les demi-espaces contenant ces objets. Ainsi, soit un triangle et un point pris hors du plan contenant ce triangle. Chaque côté du triangle pris avec ce point définit trois des faces du tétraèdre, la quatrième face étant le triangle lui-même.
De manière générale, la notion d’enveloppe convexe fournit une interprétation géométrique des entrées du triangle de Pascal. Ainsi, considérons la ligne numérotée 4. Le premier nombre est 1; l’intersection qu’il représente est un point. Le second nombre est 4 et il est la somme des deux nombres à sa gauche et à sa droite sur le ligne précédente, soit 1 et 3 qui représentent respectivement un point et un triangle. L’enveloppe convexe de ces deux objets est donc un tétraèdre, un solide à quatre sommets. Le cas du troisième nombre de cette même ligne, 6, est illustré ci-dessous.
Grâce au triangle de Pascal, on peut déterminer le nombre de sommets des photos d’intersection d’un hyperplan glissant perpendiculairement sur la diagonale principale d’un hypercube en dimension 6 ou en dimension 8, par exemple, et déterminer de quels objets géométriques ils sont l’enveloppe convexe. Pour ce qui est de se représenter visuellement cette enveloppe convexe, c’est une tout autre histoire.
- L’entrée $\displaystyle \begin{pmatrix}n \\ k \end{pmatrix}$ du triangle de Pascal s’appelle coefficient binomial en raison du lien entre ce triangle de nombres et le développement du binôme de Newton (voir William Verreault p. 19). ↩
