icone-challenge-math-OS

Solution pour le challenge 44

Soient b,N,S des entiers tels que b\geqslant2 et N\geqslant1.

Notons A_{b,N,s} le nombre de N-uplets \left(i_{1},\cdots,i_{N}\right) d’entiers compris (au sens large) entre 0 et b-1, tels que i_{1}+\cdots+i_{N}=S.

En symboles :
\displaystyle{A_{b,N,s}=\text{card}\left\{\left(i_{1},\cdots,i_{N}\right)\in\llbracket0,b-1\rrbracket^{N};\,\sum_{k=1}^{N}i_{k}=S\right\}}

L’énoncé demande le calcul de A_{10,10,50}.

Le cœur de ce qui va suivre réside dans l’observation-clef suivante :

A_{b,N,S} est le coefficient de X^S dans le développement du polynôme :

    \[P=\left(\sum_{i=0}^{b-1}\,X^{i}\right)^{N}\]

Transformons maintenant l’écriture de P, en passant par une série formelle :

    \[P=\left(\frac{1-X^{b}}{1-X}\right)^{N}\]

En dérivant N fois la relation :

    \[\frac{1}{1-X}=\sum_{k=0}^{+\infty}X^{k}\]

il vient :

    \begin{eqnarray*}& &\frac{\left(N-1\right)!}{\left(1-X\right)^{N}}\\& = & \left(\frac{1}{1-X}\right)^{(N-1)}\\& = & \sum_{k=N-1}^{+\infty}\frac{k!}{\left(k-N+1\right)!}X^{k-N+1}\\& = & \sum_{k=0}^{+\infty}\frac{\left(k+N-1\right)!}{k!}X^{k} \end{eqnarray*}

et par conséquent :
\displaystyle{P=\left(1-X^{b}\right)^{N}\,\sum_{k=0}^{+\infty}\frac{\left(k+N-1\right)!}{k!\left(N-1\right)!}X^{k}}

c’est-à-dire, via la formule du binôme :
\displaystyle{P=\left(\sum_{j=0}^{N}\binom{N}{j}\left(-1\right)^{j}X^{jb}\right)\left(\sum_{k=0}^{+\infty}\binom{k+N-1}{N-1}\,X^{k}\right)}

Le coefficient de X^{S} dans l’expression développée de P est donc :
\displaystyle{\boxed{A_{b,N,s}=\sum_{j=0}^{\left\lfloor S/b\right\rfloor }\left(-1\right)^{j}\binom{N}{j}\binom{s-jb+N-1}{N-1}}}

En particulier, et pour revenir au cas qui nous intéresse :
\displaystyle{A_{10,10,50}=\sum_{j=0}^{5}\left(-1\right)^{j}\binom{10}{j}\binom{59-10j}{9}}

Soit, après calcul sur machine : A_{10,10,50}=374\,894\,389.

Tiens! C’est un nombre premier 🙂

Pour consulter l’énoncé, c’est ici

Partager cet article
    

Laisser un commentaire