Combinatoire
Répondre à la discussion
Affichage des résultats 1 à 22 sur 22

Combinatoire



  1. #1
    invite3c81b085

    Combinatoire


    ------

    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...

    -----

  2. #2
    invitebb921944

    Re : Combinatoire

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

  3. #3
    invite6de5f0ac

    Re : Combinatoire

    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

  4. #4
    Anthonaille

    Re : Combinatoire

    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
    Dernière modification par Anthonaille ; 26/02/2006 à 17h10.

  5. A voir en vidéo sur Futura
  6. #5
    invite6de5f0ac

    Re : Combinatoire

    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

  7. #6
    invitebb921944

    Re : Combinatoire

    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!]

  8. #7
    invite3c81b085

    Re : Combinatoire

    Citation Envoyé par 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.

    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...

  9. #8
    invitebb921944

    Re : Combinatoire

    Merci de lire les réponses

  10. #9
    invite3c81b085

    Re : Combinatoire

    Citation Envoyé par Ganash
    Merci de lire les réponses
    désolé :S...

  11. #10
    invite3c81b085

    Re : Combinatoire

    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?

  12. #11
    invite6de5f0ac

    Re : Combinatoire

    Citation Envoyé par Herbiti
    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

  13. #12
    invite3c81b085

    Re : Combinatoire

    merci beaucoup

  14. #13
    invitebb921944

    Re : Combinatoire

    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.

  15. #14
    invite6de5f0ac

    Re : Combinatoire

    Citation Envoyé par Ganash
    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

  16. #15
    invitebb921944

    Re : Combinatoire

    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

  17. #16
    invite3c81b085

    Re : Combinatoire

    J'aimerai un algo récurssif pour afficher toutes les permutations ci-dessus.

    Est-ce possible que vous me donniez l'algo ou je vais voir dans le forum informatique...

    Merci

  18. #17
    invite6de5f0ac

    Re : Combinatoire

    Citation Envoyé par Herbiti
    J'aimerai un algo récurssif pour afficher toutes les permutations ci-dessus.

    Est-ce possible que vous me donniez l'algo ou je vais voir dans le forum informatique...

    Merci
    Je dois avoir ça dans mes archives, probablement pas pour ce problème-là précisément, mais facilement adaptable...

    Je dirais qu'étant donnée une "permutation" pour (L,C) donnés, soit un tableau de L*C entiers compris entre 1 et L, le jeu est d'insérer la "couleur" (L+1) partout où c'est possible, ce qui peut se faire par une simple boucle (pas besoin de rendre récursive la boucle interne, c'est ce qu'on appelle une "tail-recursion").

    On peut (on doit!) créer un tableau de L*C+C éléments, et pour i=0 à LC+1, insérer soit l'élément du tableau original, soit la "couleur" L+1; quand on a inséré C fois la valeur (L+1), le reste s'en déduit. On peut déduire ça de la représentation binaire de i...

    Ahem... à mettre en forme! Je te tiens au courant.

    -- françois

    P.S. - Si j'ai ça dans mes tuyaux, ça sera sûrement en C. Ca te va, ou tu préfères du pseudocode style Pascal?

  19. #18
    invite3c81b085

    Re : Combinatoire

    du C, c parfait

    J'aimerai cet algo en c++, puisque je programme en c++ mais si tu l'as en c, c super

  20. #19
    invite6de5f0ac

    Re : Combinatoire

    Bonjour,

    Voilà un algorithme récursif pour ton problème d'énumération. C'est du C++ (je n'utilise pratiquement plus C tout court), mais il est tellement simple qu'on ne voit pas la différence (à part les commentaires en //...).

    Pour l'affichage j'ai préféré utiliser le bon vieux printf() plutôt que les iostreams, mais c'est sans importance.

    Quelques explications: la fonction colorier(N,P,C,K,m) fait tout le boulot!
    C[j] indique combien de fois la couleur j est encore disponible ;
    K[i] est la couleur de l'objet i ;
    N est le nombre d'objets, P le nombre de couleurs (attention, par rapport à tes notations! c'est bien N, et non N*P, le nombre d'objets).
    m est le premier objet à colorier (pour ne pas saloper ce qui a déjà été fait!) Quand m = N, la récurrence se termine.

    Initialement C[j] = N/P si toutes les couleurs doivent être utilisées le même nombre de fois (comme dans ton problème), mais ce n'est pas obligé.

    L'idée est d'attribuer à l'objet K[m] toutes les couleurs encore utilisables, et ensuite de récurser sur les objets restants (à partir du (m+1)-ème).

    Si tu as besoin de plus d'explications, n'hésite pas -- j'ai pondu ça au débotté hier soir, d'où l'absence de commentaires...

    -- françois

    Le code:

    void imprimer (int N, int *K)
    {
    for (int j = 0 ; j < N ; j++) printf ("[%d]", K[j]) ;
    getchar () ; // printf ("\n") ;
    }

    void colorier (int N, int P, int *C, int *K, int m)
    {
    if (m < N) {
    for (int j = 0 ; j < P ; j++)
    if (C[j] > 0) {
    K[m] = j ; C[j]-- ;
    colorier (N, P, C, K, m + 1) ;
    C[j]++ ;
    }
    }
    else imprimer (N, K) ;
    }

    int main (int argc, char *argv[], char *envp[])
    {
    const int N = 6 ;
    const int P = 3 ;
    int K[N] ;
    int C[P] ;
    for (int j = 0 ; j < P ; j++) C[j] = N / P ;
    colorier (N, P, C, K, 0) ;
    return EXIT_SUCCESS ;
    }

  21. #20
    invite6de5f0ac

    Re : Combinatoire

    Pfff... les indentations sont complètement bousillées! Heureusement que ce n'est pas trop alambiqué...

  22. #21
    invite3c81b085

    Re : Combinatoire

    c génial

    Merci beaucoup

  23. #22
    invite6de5f0ac

    Re : Combinatoire

    Bonjour,

    Voilà ce que j'ai trouvé par hasard, en cherchant tout à fait autre chose. Attention les yeux, la référence fait pro: Bourbaki, Algèbre, Chapitre 1: Structures algébriques, §5, n°1, rectification à la page 58 (p.165):

    Lorsque la multiplication est commutative, pour m et n entiers > 0, et pour toute famille , on a:

    la somme étant étendue à toutes les suites de m entiers 0 tels que et

    étant le nombre d'applications de [1,n] sur [1,m] prenant fois la valeur k.
    Ouf. C'est bien ton problème, avec n = LC, m = L, et p_1 = ... = p_m = C.

    Donc ma formule était correcte! Ça fait plaisir de se voir confirmer par le Maître!

    -- françois

    P.S. - C'est la dernière fois que je recopie du Bourbaki en TeX.

Discussions similaires

  1. combinatoire
    Par invitecc2a5165 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 10/10/2007, 17h10
  2. Combinatoire
    Par invitecc2a5165 dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 29/09/2007, 18h53
  3. analyse combinatoire
    Par invited7555812 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 06/04/2007, 15h49
  4. Combinatoire
    Par invite3c81b085 dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 25/01/2006, 08h21
  5. Combinatoire
    Par invite7d0c5dcc dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 18/09/2005, 12h21