154
4 Approche combinatoire
Nous donnons ci-dessous quelques propriétés des fonctions P et R
(cf. [138]). Rappelons que L = =log 2 n
Proposition 4.15
1. La fonction R(n) est oscillante (cf. la figure 4.9) et bornée :
1 ≤ R(n) ≤ e
−
j≥1 2 −j log(1−2 −j ) = 1,553544445 . . .
2. La fonction P peut alternativement être définie par
P (log 2 n) = 2
V (n)−{log 2 n}−ω(n)/ log 2 ,
où les fonctions V et ω sont données par
V (n) =
0≤j ≤L
n
2 j ;
ω(n) =
0≤j ≤L log(1 +
n
2 j
).
La fonction V (n) est le nombre de 1 dans la représentation binaire de n
(cf. la figure 4.10) ; la fonction ω(n) varie de manière analogue à V (n) et
est bornée par un terme d’ordre log n ; sa variation est représentée dans
la figure 4.11.
3. (Bornes sur P ) P (log 2 n) atteint sa valeur maximale lorsque n est une
puissance de 2, et vaut alors 2.
Dans le cas général,
P (log 2 n) ≥ 2
−{log 2 n}+dν(n)
avec d = 1 −
1
log 2
j ≥1 log 2 (1 + 2 −j ) = −0,253524036 . . . Cf. la
figure 4.12.
Fig. 4.9 La fonction R(n)