icone-challenge-math-OS

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 :

    \[A_{b,N,s}=\text{card}\left\{\left(i_{1},\cdots,i_{N}\right)\in\left\{0,1,\cdots,b-1\right\} ^{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 :

    \[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 :

    \[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 :

    \[\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, dans le cas qui nous intéresse :

    \[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.

NB : c’est un nombre premier 🙂

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

Partager cet article
  •  
  •  
  •  
  •  

Laisser un commentaire