Nombre de n-uplet dont la somme fait N

Bonjour à tous,

Je coince sur un problème de dénombrement, ce n'est pas un exo de cours ni rien, mais je me pose la question .

Énoncé

Soit $\Omega$ l'ensemble $[[0, N]]$, combien existe-t-il de n-uplet de $\Omega$ tel que la somme des n-uplets soit égal à $N$ ?

Exemples

-N=100, n-uplet = couple de $[[0, N]]^2$

Prenons N=100 et des couples $(a,b) \in [[0, N]]^2$, alors l'ensemble des couples $(a,b)$ qui satisfont l'énoncé sont

Il y a $N+1$ couples.

-N=100, n-uplet = triplet de $[[0, N]]^3$

Prenons N=100 et des triplets $(a,b,c) \in [[0, N]]^3$, alors l'ensemble des triplets $(a,b,c)$ qui satisfont l'énoncé sont

Il y a $N+1$ couple $(a,b)$ pour $c=0$, $N$ pour $c=1$, … , 2 pour $c=99$, 1 pour $c=100$. Il y a donc $\sum_1^{N+1} k$ triplets, soit $\frac{(N+2)(N+1)}{2}$ triplet $(a,b,c)$.

Problème

J'ai "l'impression" que tout ceci est lié à la somme des $N$ entiers consécutif de $k^{n-2}$ où $n$ est le "$n$ du n-uplet". En effet ca marche pour les 2-uplets ($\sum_i^{N+1}k^0$) et 3-uplets ($\sum_i^{N+1} k^1$).

Étant beaucoup plus visuel dans ma manière d'avoir envisagé la chose, je me perd quasi-systématiquement quand j’entame les 4-uplets et ma feuille devient très vite pleine de ratures .

Aussi, étant assez mauvais en dénombrement, je fait appel à vous afin de m'aider à mettre un certain formalisme dans tout ca.

Mes éléments de réponse

-Pour $(a,b,c,d) \in [[0,N]]^4$

On a pour $d=0$ :

soit

• pour $d=0$, $\sum_1^{N+1} k$ 4-uplet,
• pour $d=1$, $\sum_1^{N} k$ 4-uplet,
• etc.

Donc au total on aurait

Seulement c'est pas du tout une preuve. Est-ce que c'est vrai déjà, et comment généraliser à n'importe quel $n$ ?

Tu peux aussi raisonner par récurrence.

Ainsi, pour trouver le nombre de quadruplets dont la somme donne 100, tu as 101 possibilités pour le chiffre n°4, et tu te ramènes donc à 101 exercices de recherche de triplets. Et dans un raisonnement par récurrence où tu as une idée correcte de la forme générale, tu dois arriver à le démontrer.

@ Holosmos

Merci pour ta réponse élégante et rapide !

Pour voir si j'ai compris, je mets ce que j'ai fais.

On cherche le nombre de $k$-uplet $(n_1, ..., n_k)$ tels que $0 \leq n_i \leq N$ et $n_1+...+n_k=N$.

En posant $m_i = n_i+1$ on a $1 \leq m_i \leq N+1$ et $m_1+...+m_k=N+k$.

Il y a donc

Je n'ai pas compris le coup de la partition de $2n$, je suppose que tu voulais dire $N+k$ ?

@ Elegance

Ainsi, pour trouver le nombre de quadruplets dont la somme donne 100, tu as 101 possibilités pour le chiffre n°4, et tu te ramènes donc à 101 exercices de recherche de triplets. Et dans un raisonnement par récurrence où tu as une idée correcte de la forme générale, tu dois arriver à le démontrer.

En effet c'est 101 exercices de recherche de triplets, mais à chaque fois leur somme doit être décrémenté de 1. Mon problème c'est de réussir à généralisé aux $k$-uplet, et là je n'ai pas d'idée sur la récurrence par contre.

Question subsidiaire : comment tous les trouver algorithmiquement ? Pour l'instant je fais un truc bien bourrin pour $k=3$.

1
2
3
4
5
6

pour c = 0 à N
  pour b = 0 à N-c
    a = N-c-b
    stocker (a,b,c)
  fin
fin

C'est bourrin. Mais ca passe. Pour généraliser il faut rajouter des boucles.

1
2
3
4
5
6
7
8

pour d = 0 à N
  pour c = 0 à N-d
    pour b = 0 à N-c-d
      a = N-d-c-b
      stocker (a,b,c,d)
    fin
  fin
fin

PS : vous connaissez des languages qui donnent les bonnes valeurs des factorielles quand on monte dans les grands nombres ? Faut forcément aller voir du côté de Haskell je suppose…

Oui petite erreur de lecture

Ta réponse est bonne de ce que je vois

C'est pas très pratique comme généralisation si $k$ est lui-même un paramètre de ton algo. C'est un bon exo que de chercher comment le faire pour $k$ quelconque. Tu peux essayer de procéder récursivement.

D'ailleurs, algorithmiquement parlant, il est plus intéressant de calculer les coefficients binomiaux en utilisant la formulation récursive (formule de Pascal) que les factorielles. Pour que ce soit vraiment efficace, il faut cependant mémoriser les résultats (ce qui revient à faire de la programmation dynamique sans le dire).

Même sans parler de complexité, $n!$ peut-être très grand sans que $\binom{n}{k}$ ne le soit. Par exemple, à $k$ fixé, $\binom{n}{k}$ se comporte comme $\frac{n^k}{k!}$ quand $n$ tend vers l'infini.

D'ailleurs, algorithmiquement parlant, il est plus intéressant de calculer les coefficients binomiaux en utilisant la formulation récursive (formule de Pascal) que les factorielles. Pour que ce soit vraiment efficace, il faut cependant mémoriser les résultats (ce qui revient à faire de la programmation dynamique sans le dire).

Je rajouterais qu’on peut aussi passer par la formule $\binom{n}{k} = \frac{n}{k}\binom{n - 1}{k - 1}$ (valable pour $n geq 1$ et $k \geq 1$. On peut alors faire une fonction récursive qui retranscrit ça. Et on peut même faire une fonction récursive terminale.

Ouch ! J'ai réussi à trouver un truc qui marche pour $N$ et $k$ quelconque (entier…) !

Pour comprendre rien ne vaut un schéma.

On remarque que pour la dernière ligne on a :

• $\begin{pmatrix} N-1+(k-1) \\ (k-1)-1\end{pmatrix}$ fois le nombre 0,
• $\begin{pmatrix} N-1-1+(k-1) \\ (k-1)-1\end{pmatrix}$ fois le nombre 1,
• et de manière plus générale on a $\begin{pmatrix} N-x-1+(k-1) \\ (k-1)-1\end{pmatrix}$ fois le nombre $x$.

On range tout par ordre croissant et on a notre k-ème ligne de coefficient.

Pour la $(k-1)$ème, on remarque que le problème est le même que pour la $k$ème ligne, à ceci près que le total n'est pas toujours $N$ mais $N, N-1, ...,1 ,0$ et qu'il n'y a plus cette fois-ci que $k-1-1$-uplet. On suit donc le même procédé que pour la $k$ème ligne, et ainsi de suite.

Pour la 1ère ligne, il suffit de faire $N-\sum\text{autres lignes}$.

En matlab/Octave ca donne ca :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

function [a]=AllCoeff(N, K)
  
% nb=round(factorial(N+K-1)/(factorial(K-1)*factorial(N)))
  nb=nchoosek(N+K-1,K-1)
  a=zeros(K,nb);

  
  if K>1
      % k=K
      a(K,:)=triKparmisN(N,K);
      
      % k=K-2 à 2
      for k=K-1:-1:2
          
          for x=0:N
              % trouve les endroits possible s pour les valeurs '0 à N-x'
              idFind=find(sum(a(k+1:end,:),1)==x);
              
              % trouve le nombre de valeurs possible pour '0 à N-x'
              v=triKparmisN(N-x,k);
              
              % stock les valeurs
              a(k,idFind)=repmat(v,1,length(idFind)/length(v));
          end
          
      end
      
      % k=1
      % N-somme des autres coeffs
      a(1,:)=repmat(N,1,nb)-sum(a,1);
  else
      a(1,:)=N;
  end

endfunction


function v=triKparmisN(N,k)
% nb=round(factorial(N+k-1)/(factorial(k-1)*factorial(N)));
  nb=nchoosek(N+k-1,k-1);
  v=zeros(1,nb);
  id=1;
  for x=0:N
%     nb=round(factorial(N-x+k-2)/(factorial(k-2)*factorial(N-x)));
      nb=nchoosek(N-x+k-2,k-2);
      v(id:id+nb-1)=x;
      id=id+nb;
  end

endfunction

Le problème c'est de calculer les coefficients binomiaux pour les grandes valeurs de N, la factorielle rame pas mal… Du coup votre idée Lucas-84 et Karnaj m'intéresse. Je vais m'y pencher .

Ps : faudrait un markdown pour le matlab…

EDIT : Implémentation de la méthode multiplicative pour les coefficients binomiaux.

C'est beaucoup plus rapide avec cette méthode ! Et en plus les coeff' sont correct.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

function [a]=AllCoeff(N, K)
  
% nb=round(factorial(N+K-1)/(factorial(K-1)*factorial(N)))
% nb=nchoosek(N+K-1,K-1);
  nb=Multiplicativ(N+K-1,K-1);
  a=zeros(K,nb);

  
  if K>1
      % k=K
      a(K,:)=triKparmisN(N,K);
      
      % k=K-2 à 2
      for k=K-1:-1:2
          
          for x=0:N
              % trouve les endroits possible s pour les valeurs '0 à N-x'
              idFind=find(sum(a(k+1:end,:),1)==x);
              
              % trouve le nombre de valeurs possible pour '0 à N-x'
              v=triKparmisN(N-x,k);
              
              % stock les valeurs
              a(k,idFind)=repmat(v,1,length(idFind)/length(v));
          end
          
      end
      
      % k=1
      % N-somme des autres coeffs
      a(1,:)=repmat(N,1,nb)-sum(a,1);
  else
      a(1,:)=N;
  end

endfunction


function v=triKparmisN(N,k)
% nb=round(factorial(N+k-1)/(factorial(k-1)*factorial(N)));
% nb=nchoosek(N+k-1,k-1);
  nb=Multiplicativ(N+k-1,k-1);
  v=zeros(1,nb);
  id=1;
  for x=0:N
%     nb=round(factorial(N-x+k-2)/(factorial(k-2)*factorial(N-x)));
%     nb=nchoosek(N-x+k-2,k-2);
      nb=Multiplicativ(N-x+k-2,k-2);
      v(id:id+nb-1)=x;
      id=id+nb;
  end

endfunction

function a=Multiplicativ(N,k)
  a=1;
  for i=1:k
      a=a*(N+1-i)/i;
  end
endfunction