partitionnement, indistinction

Publié le par jö

Cette entrée fait suite à l'article sur le dénombrement.

On cherche d(j,s) :
On se munit de la séquence D_i des sommes des diviseurs des i<= j.
Soit g la fonction définie sur les entiers par g(r)=rs+r(r+1)/2.
On détermine r0 tel que g(r0)<=j<g(r0+1).
On construit le tableau des a_{i,r} pour 0<=r<=r0 et 0<=i<=j tel que
pour r=0
  • a_{0,0}=1 si i=0
  • a_{i,0}=sum( k=0, k=i-1, D_{i-k} a_{k,0} )/i si i!=0
et que
  • a_{i,r}=0 pour 0<=i<r
  • a_{i,r}=a_{i-r,r}+a_{i-1,r-1} pour 0<r<=i.
On a alors d(j,s)=sum( k=0, k=r0, (-1)^k a_{j-g(k)+k,k} )

Publié dans mathblog

Commenter cet article