Problème de combinaisons

[invite62cc566e]

Bonjour à tous !

J'ai un problème qui relève du défi, du moins pour moi. Pour tout arranger, je ne suis pas sure de comment l'exprimer.
Soit un ensemble fini E et N sous-ensembles quelconques de E (donc pas nécessairement disjoint). Je recherche combien de combinaisons on peut former en prenant un élément dans chaque sous-ensemble sans répétition. L'ordre n'ayant pas d'importance, il va sans dire qu'il ne faut pas compter plusieurs fois la même combinaison...

J'ai pour le moment résolu le problème (que je précise être informatique mais peu importe) en utilisant une fonction récursive plus un crible pour repérer les combinaisons identiques. Mais on comprendra aisément que plus le cardinal de E est grand, plus le temps de calcul risque d'être long. Ce n'est donc pas très satisfaisant.

Si quelqu'un à une idée...
-----

[Amanuensis]

Juste pour clarifier la demande : soit E= {a}, N=3 et les sous-ensembles sont E, E et E. Quelle est le nombre de combinaisons ? 1 ? Ou 0 parce qu'on ne peut pas prendre 3 éléments différents, un dans chaque ?

Et si E={a,b}, N=2 avec {a,b} et {a}. Réponse 1 (seule possibilité b pris dans le premier et a dans le second}, ou 2 ( a pris à la fois dans le premier et le second) ou autre ?

[invite62cc566e]

Je savais bien que je n'étais pas très préci

Effectivement, on considère un ensemble E suffisamment grand. Ou plutôt, on oubli les cas où l'on a plus de sous-ensemble que d'élément dans E.

C'est plus simple avec quelques exemples :
Soit E={a, b, c} et prenons n=2 avec {a, b} et {b, c}, les couples que je recherche sont (a,b) et (b,c). Je ne doit pas répéter d'éléments.

Autre exemple : E={a,b,c,d} et toujours avec n=2 et les sous-ensemble {a,b,c} et {b,c}, ici, je veux trouver 3 couples : (a,b), (a,c) et (b,c) car je ne tiens pas compte de l'ordre (b,c)=(c,b).

[Amanuensis]

C'est plus simple avec quelques exemples :
Soit E={a, b, c} et prenons n=2 avec {a, b} et {b, c}, les couples que je recherche sont (a,b) et (b,c). Je ne doit pas répéter d'éléments.

Pourquoi pas (a, c) ?

[A voir en vidéo sur Futura]

[invite62cc566e]

Pourquoi pas (a, c) ?

Oups... parce que j'ai oublié... Vraiment désolé. Si bien sûre qu'il faut (a,c)

Je suis en vacance ce soir... mais je crois que mon cerveau est déjà parti

[invite62cc566e]

Je reviens à la charge pour donner quelques idées. Je noterais les sous-ensembles de E. Je recherche le nombre de combinaisons d'éléments pris un à un dans chaque ensemble, soit le cardinal de l'ensemble de ces combinaisons. Je noterais cette valeur pour 2 sous-ensemble à pour N sous-ensemble.

Dans le cas où l'ordre importe, pour 2 rangs, on a :


Pour 3 sous-ensembles :


Ce qui donne après développement :


etc. jusqu'à 5 sous-ensembles. Après, j'ai arrêté car le nombre d'éléments augmente très vite ! Malgré tous, il doit y avoir une piste pour trouver une formule pour limiter le temps de calcul.

Maintenant, dans le cas ou l'on ne doit pas tenir compte de l'ordre, je ne sais plus trop comment m'y prendre.