Combinatoire

[Herbiti]

J'ai une petite question:

Imaginons un nombre L, appellé Lignes et un nombre C, appelé Colonnes.

Je prend C éléments que je prends L fois.

J'aimerai une formule pour calculer le nombre de permutations des ces objets.

Exemple:
L=2 et C=2

Je prends 2 éléments 2 fois:
[1][1][2][2]

Les permutations sont:
1) [1][1][2][2]
2) [1][2][1][2]
3) [1][2][2][1]
4) [2][2][1][1]
5) [2][1][2][1]
6) [2][1][1][2]

Merci de m'aider...

[invite43219988]

Bonjour.
Cherche dans les "k parmi n"
Ici, je dirai 2 parmi 4 qui vaut :
4!/[(4-2)!2!]=6

[fderwelt]

Bonjour,

Voilà l'approche que j’ai eu l'idée d’utiliser ; ça vaut ce que ça vaut, mais je pense que c'est un bon début...

Le problème est de partir d'un ensemble X avec N = LC éléments, et d'affecter à chaque élément un nombre de 1 à L, de sorte qu'il n'y ait jamais plus de C éléments affectés du même nombre. (On pourrait dire "couleur" au lieu de "nombre" pour être plus "parlant").

Il y a Comb(N,C) = N! / ((N-C)!C!) manières de choisir C éléments dans X, auxquels on affectera la "couleur" 1. Il reste alors (N-C) = (L-1)C éléments, à colorier avec (L-1) couleurs. On a donc la récurrence
U(L,C) = Comb(LC,C) x U(L-1,C)
où U(L,C) est le nombre de manières de colorier LC éléments avec L couleurs, avec exactement C éléments de chaque couleur. Comme clairement U(1,C) = 1 pour tout C, on trouve, si je ne m'ai pas trop gouré (les factorielles se simplifient pas mal):


Mais ce n'est pas fini, car on a choisi un ordre particulier pour les couleurs: là encore, si je ne m'ai pas vautré grossièrement, il faut diviser par L!, d'où pour le nombre de solutions à ton problème:
nombre de solutions = U(L,C) / L! =

Tout ça est à vérifier et à revérifier de très près...

-- françois

[Anthonaille]

ton exemple n'est vraiment pas clair du tout Herbiti (mais vraiment alors pas du tout) neanmoins je crois avoir une idée de ce que tu cherches.

Je vais prendre une exemple beaucoup plus clair : plusieurs interrupteurs electriques branchés en parrallèle. Un interrupteur peut avoir 2 état : ouvert ou fermé.

Dans ce cas le nombre de combinaison possible est 2^n
(n designant le nombre d'interrupteurs et 2 car chaque interrupteur peut prendre 2 etat)

Le nombre de combinaison possible est :
le nombre d'etat que peut prendre la variable ^le nombre de variable

Voila j'espere avoir repondu a ta question

[fderwelt]

Rebonjour,

Au vu des autres posts, je m'ai effectivement vautré -- mais pas grossièrement, enfin pas tant que ça...

C'est vrai que prendre L = C = 2 comme exemple, ce n'est pas très clair... Mais ma formule donne 4! / (2!^2 x 2!) = 3 dans ce cas, donc il y a plantage...
Je crois que c'est la division par L! à la fon qui est foireuse.

Mais après tout, il faut bien en laisser un peu aux autres

-- françois

[invite43219988]

Anthonaille, ce que tu dis est tout à fait juste mais je ne pense pas que cela puisse s'appliquer à un exemple du type de celui d'Herbiti.

Je peux me tromper mais on a ici :
C "objets" qu'on veut arranger parmi C*L éléments.

Une formule serait donc C parmi CL, ce qui vaut :
(CL)!/[(CL-C)!C!]

[Herbiti]

ton exemple n'est vraiment pas clair du tout Herbiti (mais vraiment alors pas du tout) neanmoins je crois avoir une idée de ce que tu cherches.

Voila j'espere avoir repondu a ta question

Bon un autre exemple:
L=3 et C=3
Je prends 3 éléments 3 fois:
[1][1][1][2][2][2][3][3][3]
Je veux le nombre de toutes les permutations de cet ensemble.

L=3 et C=2
Je prends 2 éléments 3 fois:
[1][1][1][2][2][2]

L=2 et C=3
Je prends 3 éléments 2 fois:
[1][1][2][2][3][3]

Et j'aimerai une formule pour un C et un L quelconque




Merci de m'aider...

[invite43219988]

Merci de lire les réponses

[Herbiti]

Merci de lire les réponses

désolé :S...

[Herbiti]

j'ai calculé avec L=3 et C=2 que ça valait 16 et la formule me donne 15, ais-je compté une permutation en trop ou ta formule est fausse?

[fderwelt]

Bon un autre exemple:
[...]
L=2 et C=3
Je prends 3 éléments 2 fois:
[1][1][2][2][3][3]
[...]
Merci de m'aider...

Je pense que mon résultat est OK si on vire la divison finale par factorielle (L). Autrement dit, il n'est pas OK si on ne le corrige pas

Pour L=2 et C=3, on a les 15 arrangements suivants:
33xxxx x33xxx xx33xx xxx33x xxxx33
3x3xxx x3x3xx xx3x3x xxx3x3
3xx3xx x3xx3x xx3xx3
3xxx3x x3xxx3
3xxxx3

où chaque suite [xxxx] est l'une des 6 obtenues pour L=2 et C=2. D'où 90 solutions, ce qui colle bien à mon résultat "rectifié".

Le schéma de dénombrement illustré ci-dessus donne probablement une manière plus simple de raisonner que mon calcul usine à gaz (et un peu bourrin?)

-- françois

[Herbiti]

merci beaucoup

[invite43219988]

Décidément je suis une quiche en proba, statistiques, dénombrement etc...
Si quelqu'un pouvait m'expliquer pourquoi mon raisonnement est faux, j'en serais très heureux.

[fderwelt]

Décidément je suis une quiche en proba, statistiques, dénombrement etc...
Si quelqu'un pouvait m'expliquer pourquoi mon raisonnement est faux, j'en serais très heureux.

Ton raisonnement est OK! Il s'agit bien de prendre C objets parmi L*C. Mais on ne peut pas s'arrêter là, il t'en reste alors L*C-C = (L-1)*C, parmi lesquels il faut encore en prendre C, et ainsi de suite...

Cela dit, je suis pas mal une quiche aussi, j'ai un peu tendance à tout diviser par une factorielle bien choisie dès que les nombres deviennent un peu grands...

-- françois

[invite43219988]

Merci !

Cela dit, je suis pas mal une quiche aussi, j'ai un peu tendance à tout diviser par une factorielle bien choisie dès que les nombres deviennent un peu grands...

Tant que ça simplifie faut pas se gêner