Un petit calcul

Dd Kg · April 2020

Bonjour
Soit $N\geq 2$ un entier. Je cherche à calculer cette quantité : $$\sum_{i<j}\min(|i-j|,N-|i-j|),$$ où la somme porte sur les $i,j$ entiers de $[1,N]$ avec $i<j$ (ou sans cette condition, de toute façon, une fois qu'on a l'une, on a l'autre, étant donnée la symétrie et le fait que les coefficients "diagonaux" sont nuls).
En gros, il faut additionner tous les éléments d'une matrice, avec une diagonale de 0, une sur-diagonale de 1, une sur sur diagonale de 2, etc. mais au bout d'un moment (la partie entière de $N/2$) les diagonales "redescendent".

Peut-on dire avoir une réponse explicite à ce calcul ?

Philippe Malot · April 2020

Bonsoir Dd Kg,
Voici ce que j'ai trouvé :
$$\begin{aligned}
\sum_{1\leqslant i<j\leqslant N}\min\left(\left|i-j\right|,N-\left|i-j\right|\right)
&=\sum_{1\leqslant i\leqslant j\leqslant N}\min\left(j-i,N-(j-i))\right) \\
&=\sum_{j=1}^N\sum_{i=1}^j\dfrac 12\left(N-\left|N-2\left(j-i\right)\right|\right) \\
&=\sum_{j=1}^N\sum_{k=0}^{j-1}\dfrac 12\left(N-\left|N-2k\right|\right) \\
&=\sum_{k=0}^{N-1}\sum_{j=k+1}^{N}\dfrac 12\left(N-\left|N-2k\right|\right) \\
&=\sum_{k=0}^{N-1}\dfrac 12\left(N-k\right)\left(N-\left|N-2k\right|\right) \\
&=\sum_{k=0}^{\lfloor N/2\rfloor}k(N-k)+\sum_{k=\lfloor N/2\rfloor+1}^{N-1}(N-k)^2 \\
&=\sum_{k=1}^{\lfloor N/2\rfloor}k(N-k)+\sum_{k=1}^{\lceil N/2\rceil-1}k^2 \\
&=N\sum_{k=1}^{\lceil N/2\rceil-1}k+\left(\dfrac N2\right)^2[2|N] \\
&=\dfrac N2\left\lceil\dfrac N2\right\rceil\left(\left\lceil\dfrac N2\right\rceil-1\right)+\left(\dfrac N2\right)^2[2|N]
\end{aligned}$$

où $[2|N]=1$ si $N$ est pair, $0$ sinon.

On trouve donc $\dfrac{N(N^2-1)}8$ si $N$ est impair et $\dfrac {N^3}8$ sinon.

Pour revenir à une formule condensée :
$$\boxed{\displaystyle\sum_{1\leqslant i<j\leqslant N}\min\left(\left|i-j\right|,N-\left|i-j\right|\right) = \dfrac{N(2N^2-1+(-1)^N)}{16}}$$

Un petit calcul

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 25