Conjecture de Singmaster

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La conjecture de Singmaster, nommée ainsi en l'honneur de David Singmaster, affirme qu'il y a un majorant fini des multiplicités des termes du triangle de Pascal (autres que 1 qui apparaît un nombre infini de fois), à savoir le nombre de fois où un terme apparait dans le triangle. Il est clair que le seul nombre qui apparait une infinité de fois dans le triangle de Pascal est 1 car tout autre nombre x ne peut apparaître que dans les x + 1 premières lignes du triangle. Paul Erdős a dit que la conjecture de Singmaster était probablement vraie mais qu'elle serait très difficile à démontrer.

Soit N(a) le nombre de fois où le nombre a > 1 apparaît dans le triangle de Pascal. En notation « grand O de », la conjecture affirme que :

N(a) = O(1).\,

Résultats connus[modifier | modifier le code]

Singmaster a montré[1] que

N(a) = O(\log a).\,

Abbot, Erdős, et Hanson[2] affinèrent l'estimation. La meilleure limite actuelle est

N(a) = O\left(\frac{(\log a)(\log \log \log a)}{(\log \log a)^3}\right),\,

et est due à Daniel Kane[3].

Singmaster a montré[4] que l'équation Diophantienne

{n+1 \choose k+1} = {n \choose k+2},

a une infinité de solutions pour les deux variables n, k. Il s'ensuit qu'il y a une infinité de terme de multiplicité au moins 6. Les solutions sont données par

n = F_{2i+2} F_{2i+3} - 1,\,
k = F_{2i} F_{2i+3} - 1,\,

Fn est le nème nombre de Fibonacci (indicé selon la convention suivante : F1 = F2 = 1).

Exemples numériques[modifier | modifier le code]

La calcul informatique permet d'affirmer que

  • 2 apparaît une seule fois ; Tout nombre plus grand apparaît plus d'une fois
  • 3, 4, 5 apparaissent 2 fois ;
  • 6 apparaît 3 fois ;
  • Beaucoup de nombres apparaissent 4 fois.
  • Les nombres suivants apparaissent 6 fois :
{120 \choose 1} = {16 \choose 2} = {10 \choose 3}


{210 \choose 1} = {21 \choose 2} = {10 \choose 4}


{1540 \choose 1} = {56 \choose 2} = {22 \choose 3}


{7140 \choose 1} = {120 \choose 2} = {36 \choose 3}


{11628 \choose 1} = {153 \choose 2} = {19 \choose 5}


{24310 \choose 1} = {221 \choose 2} = {17 \choose 8}
  • Le plus petit nombre apparaissant 8 fois est 3003, qui est aussi le premier nombre de la famille infinie des nombres de Singmaster ayant une multiplicité au moins égale à 6 :
{3003 \choose 1} = {78 \choose 2} = {15 \choose 5} = {14 \choose 6}

Le nombre suivant de la famille infinie des nombres de Singmaster, et aussi le plus petit nombre suivant apparaissant 6 fois ou plus est 61 218 182 743 304 701 891 431 482 520.

  • Personne ne sait aujourd'hui si les équations N(a) = 5 et N(a) = 7 possèdent une ou plusieurs solutions.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Singmaster's conjecture » (voir la liste des auteurs)

  1. (en) D. Singmaster, « Research Problems: How often does an integer occur as a binomial coefficient? », Amer. Math. Monthly, vol. 78, no 4,‎ 1971, p. 385–386
  2. (en) H. L. Abbott, Paul Erdős et D. Hanson, « On the number of times an integer occurs as a binomial coefficient », Amer. Math. Monthly, vol. 81, no 3,‎ 1974, p. 256–261 (DOI 10.2307/2319526)
  3. (en) Daniel M. Kane, « Improved bounds on the number of ways of expressing t as a binomial coefficient », Integers: Electronic Journal of Combinatorial Number Theory, vol. 7,‎ 2007, #A53 (lire en ligne)
  4. (en) D. Singmaster, « Repeated binomial coefficients and Fibonacci numbers », Fibonacci Quarterly, vol. 13, no 4,‎ 1975, p. 295–298 (lire en ligne)