Discussion :

[tROR411]

Bonjour je voudrais réaliser un algorithme récursif en fonctionnel qui calcule le nombre de manières de donner n objets à x personnes.(je suis restreint à une seule fonction)
Exemple: j'ai 3 personne(a,b,c) et 2 objets alors je peux distribuer ses objets ainsi

a b c
2 0 0
1 1 0
0 1 1
1 0 1
0 2 0
0 0 2

La fonction me retournerait donc 6.
Si quelqu'un a une idée... ça fait un bail que j'essai de résoudre ce problème(je suis novice).
Merci d'avance.

[foetus]

J'ai fait cela en Terminales S 98 ... je me suis planté

Sinon, cela s'appelle combinaison et arrangement (avec ou sans répétition, et il y aussi les permutations) (<- liens Wiki français)

Et apparemment, c'est un arrangement de 2 (k) éléments parmi 3 (n), donc n! / (n - k)!
Le point d'exclamation, c'est l'opérateur factoriel

[wiwaxia]

Bonjour,

La liste des distributions d'un nombre (X) donné d'objets entre (N) personnes s'obtient sans difficulté sur des exemples particuliers.
Cependant le programme comporte (X) boucles imbriquées, et l'on comprend que le dénombrement dans le cas général contraint d'employer un procédé récursif.

La comparaison des listes permet de remonter par induction à la filiation qui les relie, donc à la relation de récurrence qui débouche sur la récursivité.

Les listes ci-dessous, par exemple, correspondent à la répartition de 1, 2, 3 ou 4 objets entre 5 personnes; les nombres de distributions obtenues valent respectivement 5, 15, 35 et 70.



On a représenté en rouge les distributions particulières, pour lesquelles tous les objets sont attribués à la même personne.

Chaque liste L(5, X) peut se déduire de l'une des précédentes L(5, X - 1) par attribution d'un objet supplémentaire à partir du dernier terme non-nul, et en allant vers la droite (dans le sens de la liste). Voilà ce qui devrait ouvrir une piste, pour la mise au point du programme cherché.

La simple mise en ligne des valeurs obtenues (5, 15, 35, 70, 126, 210) livre une multitude d'informations, quant aux résultats cherchés.
Voir Wikipedia, et The On-Line Encyclopedia of Integer Sequences

[ERCO503]

Bonjour,

J'ai déjà eu à me poser cette question et j'ai vu une façon simple de se rappeler de la formule et de la visualiser.

Tu connais probablement le coefficient binomial :

https://fr.wikipedia.org/wiki/Coefficient_binomial
https://en.wikipedia.org/wiki/Combination

C'est le nombre de combinaisons possibles lorsqu'on prend k éléments parmi n éléments différents. Par exemple, si je prends k=2 éléments parmi un choix de n=4 éléments, alors les possibilités sont :

- Si j'énumère mes 4 choix de 1 à 4, alors on obtient les 6 possibilités :
(1,2),
(1,3),
(1,4),
(2,3),
(2,4),
(3,4)
[Autrement dit, je pourrais piger les éléments 1 et 2 ou je pourrais piger les éléments 1 et 3 ou je pourrais piger les éléments 1 et 4 ou je pourrais piger les éléments 2 et 3 ou je pourrais piger les éléments 2 et 4 ou je pourrais piger les éléments 3 et 4]

- Si on le visualise autrement, où on liste les 4 éléments et, en-dessous, on inscrit "1" si l'élément est pigé ou "0" si l'élément n'est pas pigé, alors :
(1,1,0,0), [Autrement dit, les éléments 1 et 2 ont été pigés, les éléments 3 et 4 n'ont pas été pigés]
(1,0,1,0), [Autrement dit, les éléments 1 et 3 ont été pigés, les éléments 2 et 4 n'ont pas été pigés]
(1,0,0,1), [Autrement dit, les éléments 1 et 4 ont été pigés, les éléments 2 et 3 n'ont pas été pigés]
(0,1,1,0), [Autrement dit, les éléments 2 et 3 ont été pigés, les éléments 1 et 4 n'ont pas été pigés]
(0,1,0,1), [Autrement dit, les éléments 2 et 4 ont été pigés, les éléments 1 et 3 n'ont pas été pigés]
(0,0,1,1), [Autrement dit, les éléments 3 et 4 ont été pigés, les éléments 1 et 2 n'ont pas été pigés]

Maintenant, où est-ce que tout ça nous mène par rapport à ton problème où tu veux plutôt répartir n éléments à k personnes?

Commençons avec une visualisation simple. Disons que tu veux répartir 6 livres à 3 personnes. Représentons les 6 livres par des "o" :

oooooo

Voilà 6 livres, donc 6 "o". Maintenant, puisque tu veux le répartir à 3 personnes, tu vas utiliser 2 délimiteurs. Représentons les 2 délimiteurs par des "|". Par exemple, si tu donnes 2 livres à chacune des 3 personnes, alors on aura :

oo|oo|oo

Voyons voir d'autres possibilités :

o|ooo|oo [1 livre à la 1ère personne, 3 livres à la 2e personne, 2 livres à la 3e personne]
ooo|oo|o [3 livres à la 1ère personne, 2 livres à la 2e personne, 1 livre à la 3e personne]
o|oooo|o [1 livre à la 1ère personne, 4 livres à la 2e personne, 1 livre à la 3e personne]
||oooooo [0 livre à la 1ère personne, 0 livre à la 2e personne, 6 livres à la 3e personne]
|oooooo| [0 livre à la 1ère personne, 6 livres à la 2e personne, 0 livre à la 3e personne]
oooooo|| [6 livres à la 1ère personne, 0 livre à la 2e personne, 0 livre à la 3e personne]

Voilà ce qui se passe :
- Ce qui est avant le 1er délimiteur "|" va à la 1ère personne
- Ce qui est entre le 1er et le 2e délimiteur va à la 2e personne
- Ce qui est après le 2e délimiteur va à la 3e personne

Ton problème consistait à répartir n objets à x personnes. Tu as donné un exemple avec 3 personnes et 2 objets. Voyons voir l'énumération des possibilités avec cette technique visuelle :

oo|| [Donc 2,0,0]
o|o| [Donc 1,1,0]
|o|o [Donc 0,1,1]
o||o [Donc 1,0,1]
|oo| [Donc 0,2,0]
||oo [Donc 0,0,2]

J'ai utilisé des objets "o" et des délimiteurs "|". Si je remplace les "o" par des "0" et les "|" par des "1", voyons voir :

(0,0,1,1)
(0,1,0,1)
(1,0,1,0)
(0,1,1,0)
(1,0,0,1)
(1,1,0,0)

Nous avons déjà vu ça, non? C'est l'énumération des possibilités pour le coefficient binomial "2 parmi 4", ce qui donne 6!

n!/(k!*(n-k)!) = 4!/(2!*(4-2)!) = 24/(2*2) = 24/4 = 6

Sauf que le problème n'était pas de trouver k=2 parmi n=4, c'était de distribuer n=2 objets à x=3 personnes! Eh bien, on a vu que pour diviser les objets "o" à x personnes, on a besoin de x-1 délimiteurs "|", donc dans ce cas 2 délimiteurs. En visualisant la division, j'utilisais donc 2 délimiteurs et les 2 objets à diviser, ce qui fait un total de 4 éléments, donc n+x-1.

La formule du coefficient binomial "k parmi n" = n!/(k!*(n-k)!) devient donc "x-1 parmi n+x-1" = (n+x-1)!/((x-1)!*((n+x-1)-(x-1))!) = (n+x-1)!/(n!*(x-1)!)

Dans ton exemple, on a n=2 et x=3 :

(n+x-1)!/(n!*(x-1)!) = (2+3-1)!/(2!*(3-1)!) = 4!/(2!*2!) = 24/(2*2) = 24/4 = 6, ça fonctionne!

Ok, ça fait beaucoup d'information et je n'ai pas nécessairement tout expliqué de la façon la plus claire, alors voici plusieurs exemples pour bien comprendre :

Exemple 1 : Distribuer 1 objet à 4 personnes
n=1
x=4

Visualisation avec 3 délimiteurs et 1 objet
o|||
|o||
||o|
|||o
Ça donne 4 possibilités

(n+x-1)!/(n!*(x-1)!) = (1+4-1)!/(1!*(4-1)!) = 4!/(1!*3!) = 24/(1*6) = 24/6 = 4, ça fonctionne!

Exemple 2 : Distribuer 4 objets à 4 personnes
n=4
x=4

Visualisation avec 3 délimiteurs et 4 objets
oooo|||
ooo|o||
ooo||o|
ooo|||o
oo|oo||
oo|o|o|
oo|o||o
oo||oo|
oo||o|o
oo|||oo
o|ooo||
o|oo|o|
o|oo||o
o|o|oo|
o|o|o|o
o|o||oo
o||ooo|
o||oo|o
o||o|oo
o|||ooo
|oooo||
|ooo|o|
|ooo||o
|oo|oo|
|oo|o|o
|oo||oo
|o|ooo|
|o|oo|o
|o|o|oo
|o||ooo
||oooo|
||ooo|o
||oo|oo
||o|ooo
|||oooo
Ça donne 35 possibilités

(n+x-1)!/(n!*(x-1)!) = (4+4-1)!/(4!*(4-1)!) = 7!/(4!*3!) = 5040/(24*6) = 5040/144 = 35, ça fonctionne!

Exemple 3 : Distribuer 2 objets à 5 personnes
n=2
x=5

Visualisation avec 4 délimiteurs et 2 objets
oo||||
o|o|||
o||o||
o|||o|
o||||o
|oo|||
|o|o||
|o||o|
|o|||o
||oo||
||o|o|
||o||o
|||oo|
|||o|o
||||oo
Ça donne 15 possibilités

(n+x-1)!/(n!*(x-1)!) = (2+5-1)!/(2!*(5-1)!) = 6!/(2!*4!) = 720/(2*24) = 720/48= 15, ça fonctionne!

Exemple 4 : Distribuer 4 objets à 2 personnes
n=4
x=2

Visualisation avec 1 délimiteur et 4 objets
oooo|
ooo|o
oo|oo
o|ooo
|oooo
Ça donne 5 possibilités

(n+x-1)!/(n!*(x-1)!) = (4+2-1)!/(4!*(2-1)!) = 5!/(4!*1!) = 120/(24*1) = 120/24= 5, ça fonctionne!

Pour plus de détails :
https://en.wikipedia.org/wiki/Combin...ith_repetition
https://en.wikipedia.org/wiki/Multis...ting_multisets
https://en.wikipedia.org/wiki/Stars_...combinatorics)

EDIT : Oups, la question était de fournir un algorithme récursif, ce à quoi je n'ai pas répondu! Désolé! Je me suis laissé emporté par la façon de calculer le nombre de possibilités. Par contre, ta question était tout de même d'obtenir une fonction qui retourne le nombre de possibilités. On voit donc qu'il n'est pas nécessaire d'effectuer un calcul récursif pour cela, mais simplement un calcul mathématique direct. Cependant, la formule mathématique implique le calcul d'une factorielle, ce qui peut être une fonction récursive.

[wiwaxia]

Toute répartition de (x) objets entre (n) personnes, dont (k) pour la dernière, implique la répartition préalable de (x - k) objets sur les (n - 1) personnes précédentes, ce qui doit se traduire par:
F(n, x) = F(n-1, x)_(k=0) + F(n-1, x-1)_(k=1) + F(n-1, x-2)_(k=2) ... + F(n-1, x-k)_{(k < x)} + ... + F(n-1, 0)_(k=x)

ou encore: F(n, x) = S_k=0^x(F(n-1, x-k)) = S_h=0^x(F(n-1, h)) (par changement de l'indice muet).

En ajoutant les résultats simples et évidents:
F(n, 0) = 1 ; F(n, 1) = n ; F(1, x) = 1 pour tout (n>0) et (x>=0) ,
l'écriture d'un algorithme récursif devient possible, puisque la régression des variables entières conduit à un nombre fini de calculs (~ n*x , au maximum).

Un petit programme non récursif, mais utilisant la précédente relation de récurrence, conduit au tableau de résultats suivant - pour (n) personnes (en colonne) et (x) objets (en ligne):



Chacun aura reconnu le coefficient binômial (C_n+x-1^x) .

[tROR411]

Oh merci vous avez trouvez une solution à mon problème il s'agissait bien de calculer la factorielle recursivement car je n'avais pas droit aux listes.Merci bien !