Une base peut ne pas être constante : la base des factorielles

/ Christian Nguembou Tagne

Deux cent mille secondes font deux jours, sept heures, trente-trois minutes et vingt secondes. Personne ne s’étonne de ce calcul, et pourtant il écrit un nombre dans un système dont la base change d’un rang à l’autre : soixante, puis soixante, puis vingt-quatre. On peut pousser l’idée jusqu’au bout et prendre pour poids successifs 1, 2, 6, 24, 120, 720, chacun égal au précédent multiplié par l’entier suivant. Ce sont les factorielles. Tout entier naturel non nul s’y écrit d’une seule façon, et la démonstration est celle de la base dix, presque mot pour mot. C’est ce qui la rend instructive : elle montre ce dont le théorème de numération avait réellement besoin.

Cet article est le onzième de la série Écrire un nombre, tirée de Mathématiques en terminales scientifiques (Tome 2). Il reprend pas à pas la démonstration de « Dix doigts, et un théorème », paru le 8 octobre, et la méthode de « Du décimal au binaire, et pourquoi l’algorithme s’arrête », paru le 10 octobre. Il fait suite à « Corrigé, et pourquoi la clé se calcule modulo 11 et non modulo 10 », paru le 26 octobre. Le principe du bon ordre, qui intervient une fois, est présenté avec les axiomes de Peano.

1. Des secondes aux jours

Pour convertir 200\,000 secondes, on divise par 60, puis le quotient par 60, puis le nouveau quotient par 24 :

\begin{array}{rcl} 200\,000 & = & 60\times 3\,333+\mathbf{20} \\ 3\,333 & = & 60\times 55+\mathbf{33} \\ 55 & = & 24\times\mathbf{2}+\mathbf{7} \end{array}

En remontant les égalités, on obtient

\displaystyle 200\,000=2\times 86\,400+7\times 3\,600+33\times 60+20\times 1.

Les poids 1, 60, 3\,600, 86\,400 sont obtenus chacun en multipliant le précédent par la base de son rang, et chaque « chiffre » est strictement inférieur à cette base : les secondes et les minutes vont de 0 à 59, les heures de 0 à 23. C’est exactement la condition que le théorème de l’article du 8 octobre imposait aux chiffres en base a. Elle ne demande nulle part que la base soit la même à chaque rang.

2. L’énoncé du Tome 2

La base des factorielles prend pour poids 1!, 2!, 3!, … Comme (i+1)!=(i+1)\times i!, la base du rang i vaut i+1, et le chiffre qui multiplie i! va de 0 à i.

Théorème. Pour tout entier naturel non nul x, il existe un unique entier naturel non nul n et des entiers naturels uniques a_{1}, …, a_{n} tels que

\displaystyle x=a_{1}\cdot 1!+a_{2}\cdot 2!+\cdots+a_{n}\cdot n!,\qquad 1\leq a_{n}\leq n,\qquad 0\leq a_{i}\leq i\ \text{pour}\ i<n.

Par exemple,

\displaystyle 2026=2\cdot 6!+4\cdot 5!+4\cdot 4!+1\cdot 3!+2\cdot 2!+0\cdot 1!=1440+480+96+6+4+0.

Chaque chiffre respecte sa borne : 4\leq 5 au rang de 5!, 4\leq 4 au rang de 4!, 2\leq 2 au rang de 2!. Le chiffre des unités, celui de 1!, ne vaut jamais que 0 ou 1. La suite de ce texte suit l’exercice du Tome 2, qui découpe la démonstration en quatre questions ; on y retrouve, rang pour rang, les étapes de la base dix.

3. La même inégalité

Lemme. Pour tout entier naturel non nul n, on a 1\cdot 1!+2\cdot 2!+\cdots+n\cdot n!=(n+1)!-1.

Le Tome 2 le démontre par récurrence. On peut aussi remarquer que i\cdot i!=(i+1)\cdot i!-i!=(i+1)!-i!, de sorte que la somme se télescope :

\displaystyle \sum_{i=1}^{n}i\cdot i!=\sum_{i=1}^{n}\bigl((i+1)!-i!\bigr)=(n+1)!-1.\quad\Box

C’est le lemme de l’article du 8 octobre, où l’on écrivait (a-1)a^{j}=a^{j+1}-a^{j}. Dans les deux cas, le plus grand chiffre d’un rang, multiplié par le poids de ce rang, est l’écart entre ce poids et le suivant. Tout ce que l’on écrit avec les rangs 1 à n pèse donc au plus (n+1)!-1, moins qu’une unité du rang n+1 — l’analogue exact de 999<1000.

Première conséquence : si x=a_{1}\cdot 1!+\cdots+a_{n}\cdot n! avec des chiffres admissibles et a_{n}\geq 1, alors n!\leq x\leq(n+1)!-1. Le nombre de chiffres est donc imposé par x : c’est l’unique n tel que n!\leq x<(n+1)!. Le Tome 2 en établit l’existence comme pour les puissances : l’ensemble des entiers m tels que x<m! contient x+1, il a donc un plus petit élément par le principe du bon ordre, et ce plus petit élément vaut au moins 2, puisque 0!=1!=1\leq x. Pour x=2026, on a 6!=720\leq 2026<5040=7!, d’où six chiffres.

4. Une seule écriture

Supposons que x ait deux écritures admissibles. Elles ont le même nombre n de chiffres, et l’on peut écrire

\displaystyle x=a_{n}\cdot n!+R=a^{\prime}_{n}\cdot n!+R^{\prime},\qquad R=\sum_{i=1}^{n-1}a_{i}\cdot i!,\qquad R^{\prime}=\sum_{i=1}^{n-1}a^{\prime}_{i}\cdot i!.

D’après le lemme, 0\leq R\leq n!-1 et 0\leq R^{\prime}\leq n!-1. Les deux égalités sont donc deux divisions euclidiennes de x par n!, et l’unicité de la division donne a_{n}=a^{\prime}_{n} et R=R^{\prime}. On recommence avec R, en divisant par (n-1)!, et ainsi de suite jusqu’au rang 1. Le Tome 2 présente le même argument sous forme de récurrence sur une application définie sur les suites de chiffres, en autorisant un chiffre de tête nul.

Un chiffre trop grand casse l’argument au même endroit qu’en base dix. On a aussi

\displaystyle 2026=2\cdot 6!+4\cdot 5!+3\cdot 4!+5\cdot 3!+2\cdot 2!,

mais le chiffre 5 dépasse la borne 3 de son rang, et le reste 5\cdot 3!+2\cdot 2!=34 n’est plus inférieur à 4!=24. Ce n’est plus une division euclidienne par 4!, et rien n’oblige les deux écritures à coïncider.

5. L’existence, en comptant encore

Fixons n. Les écritures admissibles à n chiffres sont les suites (a_{1},\dots,a_{n}) où a_{i} prend i+1 valeurs pour i<n et a_{n} en prend n. Il y en a

\displaystyle 2\times 3\times\cdots\times n\times n=n\cdot n!.

Les entiers x tels que n!\leq x<(n+1)! sont au nombre de (n+1)!-n!=n\cdot n!. Les deux ensembles ont le même cardinal. L’application qui associe à chaque écriture sa valeur va du premier dans le second d’après la section 3, et elle est injective d’après la section 4 ; une application injective entre deux ensembles finis de même cardinal est surjective. Tout entier de l’intervalle a donc une écriture, et tout entier non nul tombe dans l’un de ces intervalles.

Pour n=3 : 2\times 3\times 3=18 écritures, et 18 entiers de 6 à 23. La coïncidence n’a rien d’heureux. Le nombre de valeurs permises au rang de tête, n, est le quotient (n+1)!/n! diminué de un, exactement comme le chiffre de tête en base a prend a-1 valeurs ; les autres rangs prennent chacun autant de valeurs que leur base. C’est la même démonstration que le 8 octobre, avec des bases qui changent.

6. Diviser par 2, puis par 3, puis par 4

La méthode qui suit ne figure pas dans le Tome 2, dont la démonstration d’existence, comme pour la base fixe, ne fournit aucun procédé. On divise x par 2, le quotient par 3, le nouveau quotient par 4, et ainsi de suite jusqu’à un quotient nul ; les restes successifs sont a_{1}, a_{2}, a_{3}, … Pour 2026 :

\begin{array}{rcl} 2026 & = & 2\times 1013+\mathbf{0} \\ 1013 & = & 3\times 337+\mathbf{2} \\ 337 & = & 4\times 84+\mathbf{1} \\ 84 & = & 5\times 16+\mathbf{4} \\ 16 & = & 6\times 2+\mathbf{4} \\ 2 & = & 7\times 0+\mathbf{2} \end{array}

On retrouve les chiffres 0, 2, 1, 4, 4, 2 de la section 2, lus de bas en haut. La justification est celle de l’article du 10 octobre. Si q_{k} désigne le k-ième quotient, on a x=2q_{1}+a_{1}, puis q_{1}=3q_{2}+a_{2}, d’où x=a_{1}\cdot 1!+a_{2}\cdot 2!+q_{2}\cdot 3!, et de proche en proche

\displaystyle x=a_{1}\cdot 1!+a_{2}\cdot 2!+\cdots+a_{k}\cdot k!+q_{k}\cdot(k+1)!.

Le reste a_{k} d’une division par k+1 vérifie 0\leq a_{k}\leq k : c’est la borne du rang. Les quotients décroissent strictement tant qu’ils ne sont pas nuls, donc le procédé s’arrête ; quand le quotient s’annule, l’égalité est une écriture admissible, et l’unicité de la section 4 garantit que c’est la bonne. Comme le diviseur augmente d’une unité à chaque étape, les quotients chutent de plus en plus vite : 2026 s’écrit avec six chiffres dans la base des factorielles, contre onze en base deux.

7. Ce que comptent les factorielles

Ce dernier point sort également du Tome 2. Le nombre n! compte les façons de ranger n objets, et la base des factorielles numérote ces rangements. Pour ranger les objets 1, 2, 3, 4, on choisit le premier parmi quatre, le deuxième parmi les trois restants, le troisième parmi les deux derniers ; le quatrième est imposé. Numérotons chaque choix à partir de 0 dans l’ordre croissant des objets disponibles. Les trois numéros vont respectivement de 0 à 3, de 0 à 2 et de 0 à 1 : ce sont exactement les chiffres admissibles des rangs 3!, 2! et 1!.

Prenons 13=2\cdot 3!+0\cdot 2!+1\cdot 1!. Le chiffre 2 désigne le troisième objet de \{1,2,3,4\}, soit 3 ; le chiffre 0 désigne le premier de \{1,2,4\}, soit 1 ; le chiffre 1 désigne le second de \{2,4\}, soit 4 ; il reste 2. Le rangement numéro 13 est donc (3,1,4,2), et c’est bien le quatorzième des vingt-quatre rangements classés comme dans un dictionnaire, en comptant le premier, (1,2,3,4), comme le numéro 0. Le dernier, (4,3,2,1), porte le numéro 3\cdot 3!+2\cdot 2!+1\cdot 1!=23=4!-1 : c’est le lemme de la section 3, tous chiffres maximaux. Cette correspondance a été publiée en 1888 par Charles-Ange Laisant, dans le Bulletin de la Société mathématique de France, sous le titre « Sur la numération factorielle, application aux permutations ».

Les secondes, les factorielles et la base dix sont trois cas d’un même énoncé. Pour toute suite de bases b_{1}, b_{2}, … au moins égales à 2, posons w_{0}=1 et w_{k}=b_{1}b_{2}\cdots b_{k}. Tout entier naturel s’écrit alors d’une seule façon \sum c_{k}w_{k} avec 0\leq c_{k}<b_{k+1}, et la démonstration n’utilise rien d’autre que l’égalité (b_{k+1}-1)w_{k}=w_{k+1}-w_{k} et la division euclidienne. Ce que le théorème de numération exigeait d’une base, c’était seulement cela. Le prochain article de la série, qui paraît le 30 octobre, revient à la base deux pour multiplier sans table.

Le théorème et sa démonstration — l’identité du lemme par récurrence, le nombre de chiffres par le principe du bon ordre, l’unicité par la division euclidienne, l’existence par dénombrement — sont ceux de l’exercice Représentation dans la base des factorielles, dans la section Divers des exercices d’approfondissement de Mathématiques en terminales scientifiques (Tome 2). L’exemple des secondes, la démonstration télescopique du lemme, la méthode des divisions successives, la numérotation des rangements et l’énoncé pour une suite de bases quelconque n’y figurent pas et sont ajoutés ici.

Votre commentaire

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.