Nombre de n-uplet dont la somme fait N

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

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

$$ \left\{ \begin{pmatrix}0 \\ 100\end{pmatrix} ; \begin{pmatrix}1 \\ 99\end{pmatrix} ; ... ; \begin{pmatrix}100 \\ 00\end{pmatrix} \right\}.$$

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

$$ \left\{ \begin{pmatrix}0 \\ 100 \\ 0\end{pmatrix} ; \begin{pmatrix}1 \\ 99 \\ 0\end{pmatrix} ; ... ; \begin{pmatrix}100 \\ 0 \\ 0\end{pmatrix} ; \begin{pmatrix} 0 \\ 99 \\ 1\end{pmatrix} ; \begin{pmatrix} 1 \\ 98 \\ 1\end{pmatrix} ; ... ; \begin{pmatrix} 99 \\ 00 \\ 1\end{pmatrix}; ... ;\begin{pmatrix} 0 \\ 1 \\ 99 \end{pmatrix} ; \begin{pmatrix} 1 \\ 0 \\ 99 \end{pmatrix} ; \begin{pmatrix} 0 \\ 0 \\ 100 \end{pmatrix} \right\}.$$

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}$$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 :P .

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$ :

$$ \left\{ \begin{pmatrix}0 \\ 100 \\ 0 \\0 \end{pmatrix} ; ... ; \begin{pmatrix}100 \\ 0 \\ 0 \\0\end{pmatrix} ; \begin{pmatrix} 0 \\ 99 \\ 1 \\0\end{pmatrix} ; ... ; \begin{pmatrix} 99 \\ 00 \\ 1 \\0\end{pmatrix}; ... ;\begin{pmatrix} 0 \\ 1 \\ 99 \\0 \end{pmatrix} ; \begin{pmatrix} 1 \\ 0 \\ 99 \\0\end{pmatrix} ; \begin{pmatrix} 0 \\ 0 \\ 100 \\0\end{pmatrix} \right\}$$
pour $d=1$
$$ \left\{ \begin{pmatrix}0 \\ 99 \\ 0 \\ 1 \end{pmatrix} ; ... ; \begin{pmatrix}99 \\ 0 \\ 0 \\1\end{pmatrix} ; \begin{pmatrix} 0 \\ 98 \\ 1 \\1\end{pmatrix} ; ... ; \begin{pmatrix} 98 \\ 00 \\ 1 \\1\end{pmatrix}; ... ;\begin{pmatrix} 0 \\ 1 \\ 98 \\1 \end{pmatrix} ; \begin{pmatrix} 1 \\ 0 \\ 98 \\1\end{pmatrix} ; \begin{pmatrix} 0 \\ 0 \\ 99 \\1\end{pmatrix} \right\}$$

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

$$\text{nombre de n-uplet }= \sum_{d=0}^{N} \sum_1^{N+1-d} k. $$

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$ ?

Édité par Gwend@l

+0 -0
Staff

Cette réponse a aidé l'auteur du sujet

En fait c'est un problème de partionnement assez simple. Je te donne un cas très similaire (auquel tu pourras te ramener) :

On cherche le nombre de $k$-uplets $(n_1,\ldots,n_k)$ tels que $1\leq n_i \leq n$ et

$$n_1+ n_2+\ldots +n_k = n. $$

On remarque que

$$ n= 1 +1 + \ldots + 1 $$

et donc une solution $(n_1,\ldots,n_k)$ est univoquement définie par le choix de $k-1$ signes $+$ dans le membre de droite (puisqu'alors on regroupe les $k$ termes délimités). On doit alors choisir $k-1$ signes $+$ parmi $n-1$, il y a donc

$$ \binom{n-1}{k-1} $$

solutions.


Dans ton cas de figure, tu peux déjà ajouter $1$ à chaque élément de tes $n$-uplets pour obtenir une partition de $2n$. Après tu revient au cas que je viens de te faire.

Édité par Holosmos

Ce n’est pas en répétant « Hom, Hom », qu’on démontre des théorèmes sérieux - Siegel Mon Twitter

+0 -0

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.

+0 -0
Auteur du sujet

@ 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

$$ \begin{pmatrix}N+k-1 \\ k-1 \end{pmatrix}$$
$k$-uplet possible.

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 ? :D 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…

Édité par Gwend@l

+0 -0

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

Gwend@l

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.

Édité par Lucas-84

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.

Édité par Karnaj

Je fais un carnage si ce car nage car je nage, moi, Karnaj ! - Tutoriels LaTeX - Contribuez à un tutoriel Ruby

+1 -0
Auteur du sujet

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

Pour comprendre rien ne vaut un schéma.

Représentation des coefficients

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

Édité par Gwend@l

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte