Pour 10, je décide de décomposer toujours de la même manière : pour i allant de 1 à 10, je cherche les décompositions à i nombres. Comme je cherche les décompositions sous la forme [latex]a_1 + a_2 + \dots + a_i[/latex] avec [latex]a_1 \geq a_2 \geq \dots \geq a_i[/latex], [latex]a_1[/latex] sera au plus égal à [latex]11-i[/latex], donc je peux poser les diverses valeurs possibles de [latex]a_1[/latex] (dans l'ordre décroissant), et je cherche comment décomposer le reste, soit [latex]10-a_1[/latex], en [latex]i-1[/latex] entiers tous inférieurs ou égaux à [latex]a_1[/latex]. On sent débarquer comme une récursivité, par ici Passage à la pratique :

- une décomposition à un seul entier :
10

- cinq décompositions à deux entiers :
9 + 1
8 + 2
7 + 3
6 + 4
5 + 5

- huit décompositions à trois entiers :
8 + 1 + 1
7 + 2 + 1
6 + 3 + 1
6 + 2 + 2
5 + 4 + 1
5 + 3 + 2
4 + 4 + 2
4 + 3 + 3

- sept décompositions à quatre entiers :
7 + 1 + 1 + 1
6 + 2 + 1 + 1
5 + 3 + 1 + 1
5 + 2 + 2 + 1
4 + 4 + 1 + 1
4 + 3 + 2 + 1
4 + 2 + 2 + 2
3 + 3 + 3 + 1
3 + 3 + 2 + 2 (edit : les deux que j'avais oubliées...)

- sept décompositions à cinq entiers :
6 + 1 + 1 + 1 + 1
5 + 2 + 1 + 1 + 1
4 + 3 + 1 + 1 + 1
4 + 2 + 2 + 1 + 1
3 + 3 + 2 + 1 + 1
3 + 2 + 2 + 2 + 1
2 + 2 + 2 + 2 + 2

- cinq décompositions à six entiers :
5 + 1 + 1 + 1 + 1 + 1
4 + 2 + 1 + 1 + 1 + 1
3 + 3 + 1 + 1 + 1 + 1
3 + 2 + 2 + 1 + 1 + 1
2 + 2 + 2 + 2 + 1 + 1

- trois décompositions à sept entiers :
4 + 1 + 1 + 1 + 1 + 1 + 1
3 + 2 + 1 + 1 + 1 + 1 + 1
2 + 2 + 2 + 1 + 1 + 1 + 1

- deux décompositions à huit entiers :
3 + 1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 2 + 1 + 1 + 1 + 1 + 1 + 1

- une décomposition à neuf entiers :
2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

- une décomposition à dix entiers :
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

J'ai donc 42 décompositions de 10.



Je reviens plus tard pour plancher sur la mise en place d'un algorithme récursif de dénombrement



Je suis de retour, et je vais essayer de poser quelques briques supplémentaires.

Appelons [latex]E_k^n[/latex] le nombre de façons différentes d'exprimer [latex]n[/latex] comme une somme de [latex]k[/latex] nombres entiers. On peut déjà poser des bornes inférieures et supérieures : [latex]E_n^n = E_1^n = 1[/latex] et [latex]E_k^n = 0[/latex] pour tout [latex]k \notin \left\{ 1 ; 2 ; \dots ; n \right\}[/latex].

En suivant la logique ci-dessus, on souhaite décomposer le nombre n en une somme ordonnée [latex]n = \sum_{i=1}^k a_i[/latex] avec [latex]a_1 \geq a_2 \geq \dots \geq a_k > 0[/latex]. On peut donc "diminuer k" en choisissant d'office un [latex]a_1[/latex] et en précisant que les nombres suivants doivent être inférieurs à [latex]a_1[/latex] ; pour cela, je note [latex]E_k^n(j)[/latex] le nombre [latex]E_k^n[/latex], avec cette fois-ci la contrainte "aucun nombre de la décomposition ne peut être strictement supérieur à j". Alors, a priori :
[TeX]E_k^n = \sum_{j=1}^n E_{k-1}^{n-j}(j)[/TeX]
De la même façon :
[TeX]E_k^n(j) = \sum_{jbis=1}^j E_{k-1}^{n-jbis}(jbis)[/TeX]
La récursivité étant exposée, reste à plancher sur les arrêts. Le plus simple, vu que [latex]k[/latex] va de toute façon inéluctablement décroître, c'est de considérer le cas [latex]k=1[/latex] :
[TeX]E_1^n(j) = \left\{1 \text{ si } j \geq n \\ 0 \text{ si } j < n \right.[/TeX]
D'où le pseudo-code suivant :

decompo(n)
   ndec = 0
!!! On traite tous les cas séparément : n peut être décomposé en des sommes de 1 à n éléments, et le plus grand élément d'une somme sera toujours inférieur ou égal à n.
   do i=1,n
      ndec = ndec + decompo_contrainte(n,i,n)
   end do
end decompo

decompo_contrainte(n,k,j)
   ndec_cont = 0
!!! On s'arrête quand il faut décomposer le nombre en une somme d'un entier.
   if(k=1) then
      if(j<=n) then ndec_cont = ndec_cont + 1
!!! Dans les autres cas, on segmente le problème en choisissant un entier entre 1 et j, et il nous reste k-1 entiers à choisir
   else
      do jbis = 1, j
         ndec_cont = ndec_cont + decompo_contrainte(n-jbis,k-1,jbis)
      end do
   end if
end decompo_contrainte

(A relire pour vérifier que je ne me suis pas gouré.)

Ceci dit, on a intérêt à limiter autant que possible l'explosion combinatoire en réduisant le nombre d'appels à la procédure decompo_contrainte, en limitant mieux nos indices... Je pense qu'en codant le truc tel quel, je vais considérer comme valides des cas horribles.

Restreignons donc les valeurs de jbis ; s'il est trop petit, il n'existe pas de décomposition pour ce qui reste (i.e. si [latex](k-1) \times jbis < n-jbis[/latex]), idem s'il est trop grand (i.e. [latex]n-jbis < k-1[/latex]).

On veut donc [latex]\frac{n}{k} \leq jbis \leq n-k+1[/latex]. Comme n et k sont déclarés comme des entiers, "n/k" va me renvoyer la partie entière de [latex]\frac{n}{k}[/latex]. Je "ruse" donc en écrivant "(n-1)/k + 1" qui sera le plus petit entier supérieur ou égal à [latex]\frac{n}{k}[/latex]. Comme la condition [latex]n-jbis < k-1[/latex] peut n'être respectée par aucun jbis possible, on devra considérer "le plus grand jbis possible" comme étant "min(j,n-k+1)".

Voici donc mon code :

      program decompo

         implicit none
         integer :: n, i, ndec, decompo_cont

!!! Parametre : n est le nombre a decomposer
         n = 10
         ndec = 0

!!! On traite tous les cas séparément : n peut être décomposé en des sommes de 1 à n éléments,
!!! et le plus grand élément d'une somme sera toujours inférieur ou égal à n.

         do i=1,n
            ndec = ndec + decompo_cont(n,i,n)
         end do

         print*, 'Le nombre ', n, ' peut etre decompose de ', ndec, &
                 'facons différentes.'
      end program



      integer recursive function decompo_cont(n,k,j) result(ndec_cont)

         implicit none
         integer, intent(in) :: n, k, j
         integer :: jbis

         ndec_cont = 0
!!! On s'arrête quand il faut décomposer le nombre en une somme d'un entier.
         if(k==1) then
            if(j>=n) ndec_cont = 1
!!! Dans les autres cas, on segmente le problème en choisissant un entier entre 1 et j,
!!! et il nous reste k-1 entiers à choisir
         else
            do jbis = (n-1)/k + 1, min(j,n-k+1)
               ndec_cont = ndec_cont + decompo_cont(n-jbis,k-1,jbis)
            end do
         end if

      end function decompo_cont

Il me donne 42 pour n=10, ce qui est, à en croire l'ami Nicouj, ce que je suis supposé trouver. Pour n=100, j'obtiens (après 50 secondes de calcul) 190569292 combinaisons différentes.

Pour n=1000, je risque d'y passer des heures, tout ça pour me taper un gros dépassement de capacité et me retrouver avec un nombre négatif de possibilités... Sans moi



J'ai rajouté un calcul "à la main" du nombre de combinaisons différentes pour le cas k=2 : max(min(n/2,n/2+j+1-n),0) ("n/2" est la partie entière de la "véritable" moitié de n, ensuite j'ai distingué les cas "j plus grand que n" --> on a n/2 combinaisons, "j plus grand que la moitié de n mais plus petit que n" --> on a entre n et n/2-1 combinaisons, "j plus petit que n/2" --> pas de combinaison). La partie :

         if(k==1) then
            if(j>=n) ndec_cont = 1
         else
            do jbis = (n-1)/k + 1, min(j,n-k+1)
               ndec_cont = ndec_cont + decompo_cont(n-jbis,k-1,jbis)
            end do
         end if

est du coup devenue :

         select case(k)
            case(1)
               if(j>=n) ndec_cont = 1
            case(2)
               ndec_cont=max(min(n/2,n/2+j+1-n),0)
            case default
               do jbis = (n-1)/k + 1, min(j,n-k+1)
                  ndec_cont = ndec_cont + decompo_cont(n-jbis,k-1,jbis)
               end do
         end select

Sur n=100, je gagne 6 secondes, soit 12% de temps de calcul. Ca m'incite à essayer de faire pareil sur k=3, voire même 4 (mais ça risque d'être galère). En tout cas, j'ai sans doute mis moins de temps à rédiger et coder cette ligne de calcul que ce que je vais gagner sur le run n=1000

Bravo 2 bonnes réponses de MthS-MlndN et luthin actuellement pour n = 10 et n = 100.
En revanche pour calculer n = 1000 le procédé que vous utilisez n'aboutira surement pas de votre vivant.
Il faut donc trouver une façon plus rapide de calculer

A la main pour le premier 10 il y en a 42 si je ne me suis pas trompé ça fait beaucoup quand même j'ai mis 40 minutes pour voir si je n'en n'avais pas oublié ^^
pour 100 je ne sais pas trop comment m'y prendre et 1000 n'en parlons pas

La réponse pour 10 est 42, 100 : 190569292, 1000: pas fait jusque là excel m'a lâché

Il s'agit de faire un algorithme :

la somme des combinaisons de rang n est égale à

celle des combinaisons de rang n-1 ( il suffit de rajouter +1 à la fin )

plus celle des combinaisons de rang n-1 pour les quelles on peut ajouter 1 au dernier chiffre de la séquence, autrement dit dont les deux derniers termes sont différents.

Pour les sommes à deux termes, cela arrive une fois sur deux
pour celles à 3 termes, une fois sur 3
...

On peut donc retrouver le même nombre de combinaisons de ce type une fois  2 pour les sommes à deux termes, soit au rang n-2
De même au rang n-3 pour les solutions à 3 termes...

Partant de 1, il faut donc faire un arbre donc les valeurs sont le nombre de solutions à x termes

1
11
111
1211 ou 2 = 1+1 ( combinaisons à 2 termes au rang 4 = C2,4=C1,3+C2,4-2)

...

Et est-il possible de répondre à la question suivante :

Quel est le nombre dont la partition est 156425659958412585487958695821002215004?

Sachant que le nombre de partitions d'un entier est toujours supérieur au nombre de partitions de l'entier précédent (ça se prouve facilement, vu que reprendre une partition de [latex]n-1[/latex] et rajouter [latex]+1[/latex] à la fin donne une partition de [latex]n[/latex]), à coups de bissections, tu trouveras vite.

Tu te dém*rdes

La partition d'un nombre n c'est le nombre de manières dont tu peux écrire ce nombre en faisant la somme d'autres nombres.
Par exemple la partition de 10 est 42 car on peut écrire 10 de 42 façons différentes avec des additions comme montré dans le deuxième post

Ensuite le signe [latex]\sum[/latex] représente une somme.
Au lieu d'écrire 1+2+3+4+5+6+7+8+9+10+11+12+13 on écrit [latex]\sum_{k=1}^{13}k[/latex] qui se lis "la somme des 13 premiers nombres entiers." En fait quand tu vois se signes, dans mon exemple k prends les valeurs de 1 à 13 et on somme toutes ces valeurs ainsi on a [latex]\sum_{k=1}^{13} k=1+2+3+4+5+6+7+8+9+10+11+12+13[/latex]

Je te donne un deuxième exemple si c'était : [latex]\sum_{k=1}^{50} \frac{k+1}{k+2}[/latex] et bien ça serai très long à écrire mais ça commencerai par (1+1)/(1+2)+(2+1)/(2+2)+(3+1)/(3+2)+...+(50+1)/(50+2)

Ensuite le gogolplexe c'est un nombre gigantesque tu trouveras pleins d'informations sur le net ou ici : http://fr.wikipedia.org/wiki/Gogolplex ce nombre est [latex]10^{{10}^{100}}[/latex]

Et le factoriel (la plus précisément) est une fonction définit comme ceci :
[latex]0!=1[/latex] et [latex]n!=n*(n-1)*...*2*1[/latex] le "!" ce lit factoriel.
Par exemple 7!=7*6*5*4*3*2*1=5040

Shadock

PS : Pour la culture, 5040 est le plus petit nombre entier divisible par tous les entiers inférieurs à 10.

J presque tout pigé : le gogolplex (et le gogol 10 puissance 100), la factorielle(je connaissais déjà mais bon), sigma et un tout petit peu du raisonnement de Mths-MlndN (pas facile à taper) mais ça m'ira .
Merci beaucoup shadock et Mths-MlndN (copier-coller ) pour avoir pris du temps pour m'expliquer .

shadock a écrit:

PS : Pour la culture, 5040 est le plus petit nombre entier divisible par tous les entiers inférieurs à 10.

2520 est très déçu de savoir qu'on passe bêtement à côté de lui sans le remarquer...

Quant à www.dcode.fr qui permet entre autres le calcul des PPCM et PGCD, quelle consternation...

SHTF47 a écrit:

shadock a écrit:

PS : Pour la culture, 5040 est le plus petit nombre entier divisible par tous les entiers inférieurs à 10.

2520 est très déçu de savoir qu'on passe bêtement à côté de lui sans le remarquer...

Quant à www.dcode.fr qui permet entre autres le calcul des PPCM et PGCD, quelle consternation...

Je l'avais lu dans un livre que j'ai gagné au concours kangourou...

J'ai jamais dit que la factorielle donnait le PPCM des n premiers entiers, j'ai juste donné un exemple d'un nombre...
Pour le livre c'est une brochure qu'ils donnent à tout ceux qui font le concours.
Pour le reste je l'ai bien aidé le bambin c'était juste du plus, je reconnais mon tort j'aurai du vérifier mais ce n'est pas la peine de dire "Mônssieur Shadock blablabla..." Andrew Wiles il lui à fallut une deuxième fois pour démontrer le théorème de Fermat, comme quoi même les plus grands peuvent dire des âneries... ^^