Permutations uniques de sous-ensembles

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
CMYaCEWGnj
Messages: 1
Enregistré le: 07 Juil 2022, 12:28

Permutations uniques de sous-ensembles

par CMYaCEWGnj » 07 Juil 2022, 12:57

Bonjour à tous,

Je fais appel à votre savoir pour un problème sur lequel je n'arrive pas à aboutir.

Voici la problématique : Comment trouver le nombre de permutations uniques de sous-ensembles C de cardinalité P d’un multiensemble S de cardinalité N ?

J'ai trouvé un post sur un autre site qui en parle : https://math.stackexchange.com/questions/114654/permutations-of-subsets-of-a-multiset. C'est globalement ce que je veux, mais j'aimerais savoir s'il y avait un moyen de simplifier encore plus la formule trouvée.

Voici un exemple qui permettra sûrement d'éclaircir mes propos :
  • Imaginons que je possède 3 éléments
  • Je souhaite trouver combien il existe de façon de prendre 2 éléments parmi ces éléments
  • Cependant, je ne souhaite pas compter les doublons : comme on a deux et par exemple, est équivalent à
  • Sachant cela, les solutions possibles sont donc . On en compte 3

D'après le lien donné plus haut, une méthode pour compter cela est la suivante :
  • On construit une liste qui, à chaque élément unique des éléments de base, associe le nombre de fois qu'il apparaît. On aurait donc ici
  • Ensuite, on détermine les partitions de taille 2 dont la somme des éléments donnent 2 :
  • Finalement, en appliquant la formule donnée, le nombre total de solutions serait . On retrouve bien ce qu'on avait déterminé à la main

Est-il possible de simplifier le processus ? L'idée est par la suite d'écrire un programme pour le faire. Je l'ai déjà fait, mais il est malheureusement lent pour des grosses entrées. C'est pour cela que je souhaite réduire au maximum les calculs à effectuer.

J'espère avoir été clair, n'hésitez pas à poser des questions.



GaBuZoMeu
Habitué(e)
Messages: 5387
Enregistré le: 05 Mai 2019, 11:07

Re: Permutations uniques de sous-ensembles

par GaBuZoMeu » 07 Juil 2022, 15:41

Bonjour,

j'aimerais savoir s'il y avait un moyen de simplifier encore plus la formule trouvée.

Je ne pense pas.
Ce forum est pourri par le spam. Il vaut mieux en utiliser un autre.

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 32 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite