Ecriture d'un entier comme la somme d'une suite d'entiers ordonnés

Bonjour,

dans le cas d'un calcul de probas, je suis amené à résoudre le problème suivant :

Soit m un entier positif. Je cherche à déterminer l'ensemble de n-uplets qui permettent d'écrire m sous la forme :

$m = p_1 + p_2 + ... + p_n$

avec la contrainte $m≥p1≥p2≥...≥pn≥0.m\ge p_1\ge p_2\ge ...\ge p_n\ge 0.$

Par exemple, pour $m = 5$ et $n = 3$ , on trouve 5 triplets :

(5,0,0)
(4,1,0)
(3,2,0)
(3,1,1)
(2,2,1)

Mes questions sont les suivantes :

1/ Est-ce un problème connu en mathématiques ? Si oui, pouvez-vous svp m'indiquer un lien traitant de ce problème.

2/ Quel est le cardinal de l'ensemble des n-uplets, $∀m,n\forall m,n$ ?

3/ Y a t'il un moyen simple de générer cet ensemble ? J'ai écrit un programme qui génère cet ensemble, mais je le trouve compliqué (plein de if, while, ...)... Il y a peut-être moyen de faire plus simple.

Merci d'avance pour vos réponses.

Moniksdad.

Salut.

Aucune idée. :frowning2:
J'aurais tendance à dire qu'il est infini : pour tout n il existe au minimum une solution qui est (m;0;0;...;0) avec n-1 zéros. Donc le cardinal de ton ensemble est supérieur à celui des entiers naturels qui lui est infini.
Si on aime faire griller son ordinateur on teste toutes les solutions une par une. Le problème est qu'il faudrait alors envisager n parmi m+1 n-uplets, et ça c'est pas cool parce que ça fait beaucoup très rapidement.

Sinon on réfléchit 2 secondes à comment générer l'ensemble sans jamais passer par les n-uplets qui ne conviennent pas : on ne construit que ceux qui marchent. C'est peut-être comme ça que tu as fait.

Bon moi j'ai une idée, mais ça utilise ce que l'on appelle une fonction récursive. Ne connaissant pas ton niveau en programmation, je vais t'expliquer rapidement ce que c'est.

Une fonction récursive est une fonction qui s'appelle elle-même. Pour que ce soit clair, écrivons une fonction appelée "factorielle" qui prend comme argument un nombre n, et qui retourne n!.

factorielle(n)
{
if (n == 1) return 1;
else return n*factorielle(n-1);
}

Si on exécute factorielle(3); la fonction va renvoyer la valeur 6.

En fait au début n=3, alors la fonction va calculer 3factorielle(2).
Puis comme n=2, la fonction va calculer 2factorielle(1).
Enfin, comme n=1, la fonction ne renvoie que 1.

Je ne sais pas si tu as compris, mais si tu ne connaissais pas cette façon de coder, et bien sache que c'est super pratique vu que l'on n'a plus besoin d'en écrire des tonnes.

Par exemple si elle n'était pas récursive on aurait pu l'écrire autrement :

factorielle(n)
{
total = n;

while (n-- > 1) total *= n;

return total;
}

Et on a gagné une boucle while !

Pour ne pas utiliser la fonction factorielle à l'infini, on a utilisé ce que l'on appelle un critère d'arrêt : if (n == 1); qui permet d'empêcher la fonction de s'appeler elle-même.

Le rapport avec ton problème ? Et bien je ne sais pas trop comme l'expliquer sans l'écrire en fait. On exploite le fait que les nombres soient en ordre décroissant.

Par exemple décomposons m=10 dans des n-uplets de taille n=4.

(10;0;0;0)
(9;1;0;0)
(8;2;0;0)
(8;1;1;0)
(7;3;0;0)
(7;2;1;0)
(7;1;1;1)
(6;4;0;0)
(6;3;1;0)
(6;2;2;0)
(6;2;1;1)
(5;5;0;0)
etc.

Regarde par les n-uplets de la forme (6;...). On a, à droite, si on enlève le 6, les groupes :

(4;0;0)
(3;1;0)
(2;2;0)
(2;1;1)

Et ça c'est la résolution du problème pour m=4 et n=3 !
Continuons en regardant à droite des 2 :

(2;0)
(1;1)

C'est la résolution du problème pour m=2 et n=2 ! Tu commences à comprendre ?

Jusqu'à ce que n=1 ou m=0 (les critères d'arrêts), par exemple à côté du "4" et du "3;1" c'était le cas, tu appelles la fonction récursive qui te génèrerait des ensembles de plus en plus petits.

Je m'arrête là pour le moment, dis-moi si tu as compris ou non ce que j'ai raconté. Et autre chose importante : tu codes en quel langage ? Parce que selon le langage la valeur renvoyée par la fonction ne serait pas forcément la même, voire on ferait sans (en C par exemple ce serait le cas vu que je prévoyais de renvoyer des tableaux alors que là il faudrait s'amuser avec des pointeurs).

@+