Courrier des Lecteurs

par Bruno Boumard

 

   ÓÔÒÂÚÈ_ÇÈ_ÕÁÚÝÍÝÍÔÓÛ_Ç'ÞÓ_ÈÓÛÈÒÂÐÈ             

                                                             

                    1._ÍÓÝÚÔÇÞÃÝÍÔÓ                          

 Les n éléments de l'ensemble donné E peuvent se répartir en p "classes" (1ˆpˆn), dans chacune desquelles les  éléments  sont supposés équivalents. Chaque classe peut contenir  1  à  n-p+1 éléments pris de façon quelconque parmi les n.           

 Chaque répartition ainsi obtenue, appelée  "partition"  de E, correspond à une relation d'équivalence  (déterminée  par  le nombre de classes, par le nombre d'éléments par classe et par l'identité de ces éléments).                           

 Le nombre de partitions (ou de relations d'équivalence)  possibles croit rapidement avec n,  mais moins rapidement  que le nombre de permutations de n   (voir plus loin).             

                                                             

             2._ÇÈÓÔÒÂÚÈÒÈÓÝ_ÇÈÛ_ÕÁÚÝÍÝÍÔÓÛ                  

 Appelons respectivement  Tn  et  Pn (=!n) le nombre de partitions et le nombre de permutations pour n éléments. On calcule (ou on pose) directement les 1ers résultats (ou conventions):

      T0=P0=T1=P1=1       T2=P2=2       T3=5      P3=6       

 Pour continuer le calcul des Tn ,  on a  3  méthodes:       

                                                             

  1°)ÛÈÚÍÈ_ÇÈ_ÇÞÂÍÓÛÏÍ:       Tn  =  Somme, de k=1 à l'infini, du terme général (1÷e)×(k*n)÷!k    (V.bibliogr.), d'ou la fonction "nq" suivante:                              

                                                             

     ’ r„nq n;e;i                                            

[1]   ©   nq n:  nB PARTIT n<155 ELEM    PAR SERIE DUBINSKI  

[2]    i r e„0 0 2.718281828459      ©  INITIALISE i r  ET  e

[3]   Á:…0 si 99<i„i+1               ©  99 = RG MAX  /  SERIE

[4]    r„r+÷e÷(i*n)÷!i ª …Á          ©  SOMME DE 99 TERMES   

     ’                                                       

                                                              

  2°)ÇÍÊÊÈÚÈÓÃÈÛ_ÛÞÃÃÈÛÛÍãÈÛ: On calcule T(n+1) par récurrence

en rajoutant les différences successives  à  partir de la der-

nière valeur calculée T(n),  d'ou la fonction "nr" suivante: 

                                                              

     ’ r„nr n;a;i;j;v;w                                      

[1]   ©   nr n:  nB pARTIT n<100 ELEM    PAR  DIFF SUCCESSIVES

[2]    v„99½1 ª w r i j„v 1 0 2      ©  INITIALIS r,i,j ET v=w

[3]   Á:…0 si(n-1)<i„i+1             ©  n-1   =  VAL MAXI DE i

[4]    w[1]„w[j-1]                   ©  w[1]„DERN ELEM /w PREC

[4]    w[1]„w[j-1]                   ©  w[1]„DERN  DU w PRECED

[6]   Â:…Ã si(i+1)<j„j+1             ©  j VARIE  DE  2  à  i+1

[7]    w[j]„w[j-1]+v[j-1] ª …       ©  w[j]„ELEM j-1  /  v  w

[8]   Ã:v„w                          ©  v „ w   (à RECALCULER)

[9]    r„w[j-1] ª …Á                 ©  r„ELEM  j-1    DE    w

     ’                                                       

                    

 

  3°)ÈÒÕÐÔÍ_ÇÞ_ÝÚÍÁÓËÐÈ_ÇÈ_ÕÁÛÃÁÐ dont la ligne n contient les combinaisons de  n ,  p à p ,  avec p¹[0 1 2...n]:           

  Cn0 ,  Cn1 ,  Cn2 ,  ...  Cnp.    On peut alors écrire:    

   Tn+1  =  Tn +  prod scal (T0 T1 T2..Tn).(Cn0 Cn1 Cn2..Cnn) d'où la fonction "np" suivante:                              

                   

                                         

     ’ r„np n;a;i;s                                          

[1]   ©   np n:  NB pARTIT n<219 ELEM    PAR TRIANGL DE PASCAL

[2]    …0 si(n>218)Ÿ(1<½,n)              ©  n   ENTIER   < 219

[3]    r„s„i„,1                          ©  r,s,i  RECOIVENT 1

[4]    …0 si n=1                         ©  SI n=1:   np 1 … 1

[5]   Á:…0 si n<i„i+1                    ©  i   ¹   [2...n]  

[6]    r„¯1†s„s,s[a]+s+.×(¯1+¼a)!¯1+a„½s ©  PROD SCAL ×LGN a..

[7]    …Á  ©..TRIANG PASCAL  (a„½s)    +   s[a] … DERN TERME r

     ’                                                       

                                                             

                 ÈðÈÒÕÐÈÛ_ÓÞÒÈÚÍÙÞÈÛ                          

                                                             

     Œpp„13  ª  ,†np¨v„3 5 9 19 25 99  ª  nq¨v  ª  nr¨v      

5 52 21147 5832742205057 4.63859033223E18 1.618706027446E114 

5 52 21147 5832742205057 4.63859033223E18 1.618706027446E114 

5 52 21147 5832742205057 4.63859033223E18 1.618706027446E114 

                                                             

   ÚÈÒÁÚÙÞÈ: Les fonctions "np" et "nq" ne contiennent chacune

qu'une boucle (au lieu de 2 boucles imbriquées pour"nr").    

 Les temps de calcul pour"np","nq","nr" sont dans les rapports

5, 1, 48; mais on dépasse la capacité (1.7E308) respectivement

pour n=219, 155, 100. La fction"np", assez rapide, est gardée.

                                                              

             ÃÔÒÕÁÚÁÍÛÔÓ_ÇÈ_Ýn_ÈÝ_ÇÈ_Õn                      

 La table comparative fournie par la fonction "nz"  et l'exem-

ple donnés ci-dessous montrent que, pour n éléments, le nombre

Tn des partitions croit rapidement avec n,    mais   cependant

moins vite que le nombre Pn des permutations :               

                         

                                   

     ’ r„nz v;a;b;c                                          

[1]   ©   nz v:  NB pARTIT & PERMUT/ELEM¹[a..b]  b<171  v„a b

[2]    a b„v                                  © VAL NBRES a b

[3]    r„(3,½c)½(a+¼½c),(np¨c),!¨c„a+¼b-a„a-1 © TABL COMPARAT

     ’                                                       

                                                             

                                                              

      Œpp„14 ª nz 13 16                                      

        13           14             15              16       

  27644437    190899322     1382958545     10480142147       

6227020800  87178291200  1307674368000  20922789888000       

                                                             

 De n=13 à 16, Tn passe de 27E6 à 10E9,  mais  Pn passe de

   

6E9 à 20E12, le rapport  Tn÷Pn  passant de  225 à 2000