Théorème de l'étoile de David

Coefficients binomiaux intervenant dans le théorème de l'étoile de David (les lignes du triangle de Pascal sont représentées ici verticalement).

Le théorème de l'étoile de David est un résultat mathématique donnant deux identités concernant les coefficients binomiaux, disposés dans le triangle de Pascal en forme de deux triangles imbriqués.

Première identité

Énoncé

Les PGCD des coefficients binomiaux situés aux sommets de deux triangles d'une étoile de David dans le triangle de Pascal sont égaux :

${\displaystyle {\begin{aligned}&{\text{PGCD}}{\biggl (}{\binom {n-1}{k-1}},{\binom {n}{k+1}},{\binom {n+1}{k}}{\biggr )}\\[8pt]={}&{\text{PGCD}}{\biggl (}{\binom {n-1}{k}},{\binom {n}{k-1}},{\binom {n+1}{k+1}}{\biggr )}\end{aligned}}}$

Historique

Cette identité a été conjecturée par Henry W. Gould en 1971[1], démontrée par Hoggatt et Hillman en 1972[2], puis par Singmaster en 1973[3], et par Hitotumatu et Sato en 1975[4].

Exemples

Pour n = 9, k = 3 ou n = 9, k = 6, le nombre 84 est entouré successivement par les nombres 28, 56, 126, 210, 120, 36. En prenant un terme sur deux, on obtient : PGCD (28, 126, 120) = 2 = PGCD (56, 210, 36) (voir ci-contre).

De même, le terme précédent 36 est entouré par les éléments 8, 28, 84, 120, 45, 9, et en prenant un terme sur deux, on obtient : PGCD (8, 84, 45)= 1 = PGCD (28, 120, 9).

Démonstration de Hitotumatu et Sato

La formule :

${\displaystyle {\begin{bmatrix}{\binom {n-1}{k-1}}\\{\binom {n}{k+1}}\\{\binom {n+1}{k}}\end{bmatrix}}={\begin{bmatrix}k+1&k-n-1&-n-1\\-k&n-k+1&n\\k+1&k-n&-n\end{bmatrix}}{\begin{bmatrix}{\binom {n+1}{k+1}}\\{\binom {n}{k-1}}\\{\binom {n-1}{k}}\end{bmatrix}}}$

et la formule inverse :

${\displaystyle {\begin{bmatrix}{\binom {n+1}{k+1}}\\{\binom {n}{k-1}}\\{\binom {n-1}{k}}\end{bmatrix}}={\begin{bmatrix}-n&-k&n-k+1\\n&k+1&k-n\\-n-1&-k-1&n-k+1\end{bmatrix}}{\begin{bmatrix}{\binom {n-1}{k-1}}\\{\binom {n}{k+1}}\\{\binom {n+1}{k}}\end{bmatrix}}}$

montrent que chaque élément d'un triangle est combinaison linéaire entière des éléments de l'autre triangle, ce qui implique que les diviseurs communs aux élément d'un triangle, sont des diviseurs communs aux éléments de l'autre triangle et vice versa. Ceci prouve l'égalité des PGCD.

Généralisations

Singmaster [3] a complété cette identité en montrant que les PGCD ci-dessus sont également égaux à ${\displaystyle {\text{PGCD}}{\biggl (}{n-1 \choose k-2},{n-1 \choose k-1},{n-1 \choose k},{n-1 \choose k+1}{\biggr )}}$ .

Ainsi, dans l'exemple ci-dessus pour l'élément 84, on a également PGCD {8, 28, 56, 70} = 2.

Ces égalités persistent aussi pour des étoiles plus grandes[5]. Par exemple,

${\displaystyle {\begin{aligned}&{\text{PGCD}}{\biggl (}{\binom {n-2}{k-2}},{\binom {n-1}{k}},{\binom {n}{k+2}},{\binom {n+1}{k+1}},{\binom {n+2}{k}},{\binom {n}{k-1}}{\biggr )}\\[8pt]={}&{\text{PGCD}}{\biggl (}{\binom {n-2}{k}},{\binom {n-1}{k-1}},{\binom {n}{k-2}},{\binom {n+1}{k}},{\binom {n+2}{k+2}},{\binom {n}{k+1}}{\biggr )}.\end{aligned}}}$

Deuxième identité

Énoncé

Hoggatt et Hansell ont remarqué en 1971 que les deux ensembles de trois nombres de l'étoile de David ont des produits égaux [6] :

${\displaystyle {\binom {n-1}{k-1}}{\binom {n}{k+1}}{\binom {n+1}{k}}={\binom {n-1}{k}}{\binom {n}{k-1}}{\binom {n+1}{k+1}}}$.

Par exemple, en observant à nouveau que l'élément 84 est entouré successivement par les éléments 28, 56, 126, 210, 120, 36, et en prenant un terme sur deux, on a : 28 × 126 × 120 = 2^6 × 3^3 × 5 × 7^2 = 56 × 210 × 36.

Ce résultat se démontre facilement en écrivant chaque coefficient binomial sous forme factorielle :${\displaystyle {n \choose k}={\frac {n!}{(n-k)!k!}}}$.

Il en existe cependant une démonstration combinatoire, moins simple :

Démonstration

Soient a, b, c, x, y, z six entiers naturels vérifiant x, y, z ≤ min(a, b, c) et (b-a, c-b, a-c) = (y-z, z-x, x-y).

Comptons le nombre de façons de partitionner un ensemble de taille a + b + c en six parties :

• A, de taille x, B, de taille y, C, de taille z
• A', de taille a - x, B', de taille b - y, C', de taille c - z.

On commence par partitionner l'ensemble en trois parties, de tailles respectives a, b et c. Il y a un certain nombre N de façons de le faire.

Méthode 1

• on coupe la partie de taille a en ${\displaystyle A\sqcup A'}$ : ${\displaystyle {\binom {a}{x}}}$ façons.
• on coupe la partie de taille b en ${\displaystyle B\sqcup B'}$ : ${\displaystyle {\binom {b}{y}}}$ façons.
• on coupe la partie de taille c en ${\displaystyle C\sqcup C'}$ : ${\displaystyle {\binom {c}{z}}}$ façons.

Total : ${\displaystyle N\times {\binom {a}{x}}{\binom {b}{y}}{\binom {c}{z}}}$ façons.

Méthode 2

• on coupe la partie de taille a en ${\displaystyle C\sqcup B'}$ (car ${\displaystyle z+b-y=a}$) : ${\displaystyle {\binom {a}{z}}}$ façons.
• on coupe la partie de taille b en ${\displaystyle A\sqcup C'}$ (car ${\displaystyle x+c-z=b}$) : ${\displaystyle {\binom {b}{x}}}$ façons.
• on coupe la partie de taille c en ${\displaystyle B\sqcup A'}$ (car ${\displaystyle y+a-x=c}$)  : ${\displaystyle {\binom {c}{y}}}$ façons

Total : ${\displaystyle N\times {\binom {a}{z}}{\binom {b}{x}}{\binom {y}{z}}}$ façons.

On obtient ${\displaystyle {\binom {a}{x}}{\binom {b}{y}}{\binom {c}{z}}={\binom {a}{z}}{\binom {b}{x}}{\binom {c}{y}}}$.

Posant maintenant (a, b, c) = (n-1, n, n+1) et (x, y, z) = (k-1, k+1, k), on vérifie que (b-a, c-b, a-c) = (1, 1, -2) = (y-z, z-x, x-y).

On en déduit l'identité de l'étoile de David : ${\displaystyle {\binom {n-1}{k-1}}{\binom {n}{k+1}}{\binom {n+1}{k}}={\binom {n-1}{k}}{\binom {n}{k-1}}{\binom {n+1}{k+1}}}$.

Cette démonstration est une traduction/adaptation de celle publiée sur ce site.

Généralisation

On peut remplacer ${\displaystyle {n \choose k}}$ par ${\displaystyle {\binom {n}{k}}_{(a_{n})}={\frac {f(n)}{f(n-k)f(k)}}}$, où ${\displaystyle f(n)=\coprod _{k=1}^{n}a_{k}}$, ${\displaystyle (a_{n})}$ étant une suite de réels non nuls.

En particulier, si ${\displaystyle (a_{n})}$ est la suite de Fibonacci ${\displaystyle (F_{n})}$, ${\displaystyle {\binom {n}{k}}_{(a_{n})}}$ est le coefficient fibonomial ${\displaystyle {\binom {n}{k}}_{F}}$ ; le deuxième théorème de l'étoile de David est donc valable dans le triangle fibonomial.[5]

Si ${\displaystyle (a_{n})}$ est le q-analogue de n : ${\displaystyle [n]_{q}=1+q+...+q^{n-1}}$, ${\displaystyle {\binom {n}{k}}_{(a_{n})}}$ est le coefficient binomial de Gauss ${\displaystyle {\binom {n}{k}}_{q}}$ ; le deuxième théorème de l'étoile de David est donc valable dans le triangle q-binomial.

On peut généraliser au cas où ${\displaystyle (a_{n})}$ est une suite quelconque dans un groupe commutatif noté multiplicativement. Par exemple, dans le groupe ${\displaystyle (\mathbb {Z} ,+)}$, ${\displaystyle {\binom {n}{k}}_{(n)}=k(n-k)}$, voir la suite A004247 de l'OEIS.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Star of David theorem » (voir la liste des auteurs).

1. (en) Henry W. Gould,, « A New Greatest Common Divisor Property of The Binomial Coefficients », Fibonacci Quarterly, vol. 10,‎ 1972, p. 579-584 (lire en ligne).
2. (en) A. P. Hillman et V. E. Hoggatt, Jr., « A Proof of Gould's Pascal Hexagon Conjecture », The Fibonacci Quarterly, vol. 10, n^o 6,‎ 1972, p. 565-568, 598 (lire en ligne).
3. (en) David Singmaster, « Notes on Binomial Coefficients: IV—Proof of a Conjecture of Gould on the G.C.D.'s of Two Triples of Binomial Coefficients », The Fibonacci Quarterly, vol. 11, n^o 3,‎ 1973, p. 282-284.
4. (en) Sin Hitotumatu et Daihachiro Sato, « Star of David theorem », Fibonacci Quarterly, vol. 13,‎ 1975, p. 70.
5. Weisstein, Eric W. "Star of David Theorem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/StarofDavidTheorem.html
6. (en) V. E. HOGGATT et W. HANSELL, « THE HIDDEN HEXAGON SQUARES », Fibonacci quarterly vol. 9 n°2,‎ 1971, p. 120,133 (lire en ligne)

Lien externe

• Visualisation du second théorème de l'étoile de David.