Analyse combinatoire

Le but est de compter des possibilités sans les énumerer.

TODO: Principe de la multiplication ?? addition?

TODO: Principe des tiroirs de Dirichlet ??

Permutations

Le nombre de possibilités différentes de permuter une liste d'éléments. L'ordre compte évidemment.

• Avec éléments distincts: Chaque élément ne peut être qu'une seule fois au maximum, ou ne pas être pris.
  Ex: avec les permutations du mots ABC
  • ABC, ACB, BAC, BCA, CAB, CBA
  • Ces permutations sont des arrangements de parmi où ().
• Avec éléments non distincts: Certains éléments existent plus qu'une fois. Ex: permutations de lettres du mots ANANAS.
  • Le nombre de permutations de objets comptant objets de type 1, objets de type 2, ... objets de type r est
  • Pour ANANAS: permutations possibles

Par ex. combien de mots différents peut-on faire avec PAPA. On va prendre le nombre total de permutations et on va le diviser par les permutations internes ( pour les 2 A et les 2 P)

est

Arrangements

Dans un arrangement l'ordre compte, on prend éléments parmi dans un ordre spécifique.

• Sans répétition: Chaque élément ne peut être qu'une seule fois au maximum, ou ne pas être pris.
  Ex: arrangements de 2 lettres parmi l'ensemble {A, B, C}:
  • On prend 2 lettres parmi 3
  • AB, BA, AC, CA, BC et CB
• Avec répétition: Chaque élément peut être pris plusieurs fois. Ex: arrangements de 2 lettres parmi l'ensemble {A, B, C}:
  • On prend 2 lettres parmi 3
  • AA, BB, CC, AB, BA, AC, CA, BC, CB

Combinaisons

Dans une combinaison l'ordre ne compte pas, on prend éléments parmi pour en faire un ensemble non ordonné.

• Sans répétition: Chaque élément ne peut être qu'une seule fois au maximum, ou ne pas être pris.
  Ex: combinaisons de 2 lettres parmi l'ensemble {A, B, C}:
  • On prend 2 lettres parmi 3
  • AB, AC, BC
• Avec répétition: Chaque élément peut être pris plusieurs fois. Ex: combinaisons de 2 lettres parmi l'ensemble {A, B, C}:
  • On prend 2 lettres parmi 3
  • AA, BB, CC, AB, AC, BC

Tableau récapitulatif des symboles et formules Note: tiré de la slide 20 du cours M. Hêche.

Stratégies de résolutions de problèmes

Dans cette partie, je liste les différents problèmes types rencontrés parmi tous les exos, avec leur stratégie de résolution en fonction du contexte, ces stratégies ne sont pas décrites dans les supports de cours (une partie peut être compris des corrigés et développés de M. Hêche). J'aurai aimé avoir ce genre de référence avec exemple pour pouvoir apprendre plus facilement toutes les stratégies nécessaires à résoudre tous les exercices possibles proposés dans le recueil et les séries. Cette liste servira à se débloquer dans des exercices et à compléter son paquets de stratégies personnelles de résolution, voir découvrir d'autres stratégies (il y a parfois plusieurs manières de faire). C'est surtout avec la pratique que ces stratégies deviendront évidentes, il ne suffit pas juste des les lire tel quels.

Note: Il y a plein de problèmes avec des factoriels dans lesquels les résultats seront très grands, il est nécessaire de calculer jusqu'au bout si la valeur est inférieur à 1000. Dans le cas contraire, les calculs finaux suffisent.

TODO: changer les titres avec un nom général et ensuite ajouter des exemples concrets TODO: réecrire les exemples avec plus d'ensembles ?

Introduction à ces stratégies

Pour appliquer et comprendre des modèles mentaux derrières ces stratégies, il est vraiment important d'avoir bien compris le concept de permutations, d'arrangements et de combinaisons décrits au-dessus et de bien voir dans chaque cas comment cela peut s'appliquer dans la vraie vie (si les exemples avec ABC ne suffisent pas). Ensuite il faut connaître par coeur leurs formules (décrites dans le tableau au-dessus) et avoir compris leur construction.

Problèmes de permutations et d'anagrammes

Problème en "Combien existe-t-il de nombres à 5 chiffres contenant le chiffre 3 ?"

Dans ce cas, on peut tenter de chercher selon les positions du 3, mais on devrait compter avec un 3, puis deux 3, ... ce qui devient très long est compliqué et ce qui contiendra beaucoup de doublons. On essaie donc de formuler le problème inverse "Combien existe-t-il de nombres à 5 chiffres ne contenant pas le chiffre 3 ?", ce qui devient tout de suite beaucoup plus simple: . Ainsi la réponse est

Problème en "Trouver le nombre de multiple de 3 et 7 entre 1 et 1000".

1. Nombre total de valeur: 1000
2. Pour trouver le nombre de multiple de 3: (partie entière inférieure de 3 sur le total de valeur)
3. Idem pour le multiple de 7
4. Il reste ensuite à retirer toutes les valeurs qui sont multiples de 3 et de 7, c'est à dire multiple du PPMC de 3 et 7 (ici 21).
5. Au final: (C'est la formule d'inclusion-exclusion à 2 ensemble en soit).

Problème de somme d'inconnues

Permet de résoudre les problèmes qui se simplifie avec une équation du style où chaque peut prendre des valeurs entre 0 et 10.

Usages concrets:

• Le nombre de possibilité d'avoir une somme donnée lors de jets successifs de dés ? (3 dès à 6 faces devant atteindre une somme de 14, donnerait l'équation avec allant de 1 à 6).
• Tirage aléatoire de 5 nombres de 1 à 10, quelle est la probabilité d'atteindre une somme supérieure à 40 ? Dans ce cas l'équation est

3 techniques à connaître une fois l'équation du problème posée:

1. Si la valeur de la somme est supérieure à la moitié du complément il faut passer par le complément, il se calcule de la façon suivante: . Si on reprend l'exemple du tirage cela donnera: . Mais attention car comme c'est un complément l'inéquation va être inversée, si on a un , il devient . Dans l'exemple du tirage, l'équation peut être recrite en:
2. Si la valeur minimum des est supérieur à 0 (dans le cas des dés, c'est 1), alors il faut chercher à réexprimer l'équation avec les qui commencent à 0. (Exemple: s'il y a 3 dés, la somme sera au minimum de 3, et ce minimum non nul nous embête). Pour faire cette transformation, il suffit de descendre la plage min-max possible vers le zéro et adapter le total. Ex: (avec des dés allant de 1 à 6) peut être transformé en , c'est comme si chaque dé allait de 0 à 5 et étaient déjà tirés une fois.
3. Si on a une inéquation, il faut différencier 2 cas: Inéquation avec ou , il faut chercher à revenir sur un égal, il suffit de définir un autre variable "poubelle" qui va de 0 au maximum possible de départ (pas de limite). Cette variable récupérera la différence non attribués. Si l'inéquation est ou , on ne peut pas reformuler directement comme dans le cas . Il faut alors compter séparément les cas possibles en décomposant : par exemple, signifie qu’on doit additionner les cas pour =40, =41, =42, etc..., jusqu'à la valeur maximale de la somme (TODO a vérifier).

Après avoir utilisé une ou plusieurs des techniques décrites ci-dessus, on arrive à une équation qui peut être enfin traité avec un combinaison avec répetitions. où est le nombre de variable et la valeur à atteinde. On peut le voir comme un problème de distribution (comme dans l'excercise avec Picsou et ses neveux).

Il reste toutefois une dernière chose à laquelle faire attention: Si la valeur de la somme excède de peu la valeur maximale de chaque : Alors retirer les cas où un vaut et les autres 0, il y en a autant que de nombre de variable.

Exemple complet du tirage de nombre: Donnée:
Etape 1, avoir un ensemble qui commence à 0:
Etape 2, utiliser le complément:
Etape 3, supprimer l'inéquation:
Le nombre de solution de solution de cette somme est:

Problème en "Quel est la probabilité qu'en tirant au hasard 5 nombres distincts entre 1 et 100, ces 5 nombres soient dans l'ordre croissant ?"

Comme toute probabilité, concentrons nous d'abord sur le nombre de possibilités favorables avant de le diviser par le total de possibilité.

Ici, tenter de faire des choix successifs est vite vain, car si on a pris 1, puis 5, le 3ème nombre va de 6 à 100 et le 4ème nombre on ne sait pas trop comme cela dépend du 3ème nombre. Cette méthode n'est pas adaptée.

La stratégie ici peut être un peu tricky à comprendre mais je vais essayer de bien formuler la réflexion. Pour chaque arrangement de 5 nombres distincts de 1 à 100 possibles prenant les nombres suivants 1, 2, 3, 4 et 5, il y a manières de les ordrer. (12345, 12354, 12435, ..., 54321) mais il n'y a qu'un seul arrangement possible (12345) où les nombres sont dans l'ordre croissant !

Autrement dit, pour chaque combinaison de 5 nombres distincts, on va avoir qu'une seule possibilité de les ordrer dans l'ordre croissant, la réponse est donc égal au nombre de combinaisons de 5 nombres parmi 100 (1 à 100 => 100 nombres disponibles): .

Pour le réexpliquer encore une fois différement, c'est comme si on devait prendre 5 nombres distincts parmi 100 sans se préoccuper de l'ordre et qu'ensuite on définirait l'ordre "qui nous arrange" (croissant, décroissant, autre) parmi ces combinaisons. L'ordre ici n'impacte donc pas le nombre de possibilités.

Le nombre de possibilités totale est , donc notre probabilité est

Problème de permutations d'éléments avec contraintes sur les positions

Contexte: Combien y a-t-il de permutations de 5 lettres distinctes ABCDE, avec certaines contraintes.

Contraintes et stratégies

1. A doit toujours être avant avant B (pas forcèment suivi) Il suffit de voir que pour chaque cas où A est avant B (ex: ACEDB ou ADBEC), si on retourne le mot dans l'autre sens, B est avant A. On a autant de cas avec A avant B que l'inverse, cette symétrie permet donc de savoir que la réponse est simplement la moitié du nombre de cas total:
2. A doit être immédiatement suivi de B Au final si AB sont toujours collés, on peut considérer qu'ils ne sont qu'une seule lettre, ainsi nous avons que 4 lettres à permuter:
3. A, B et C doivent se suivre, peu importe l'ordre On part du même concept qu'avant, c'est à dire de considérer que nos 3 lettres sont un groupe, il reste ainsi 3 parties à permuter (ABC, D et E): , cependant cette fois ABC n'est pas le seul ordre possible du groupe ABC puisque l'ordre ne compte pas. Il faut ainsi multiplier notre résultat par l'ordre interne du groupe ABC (3! également ici). Au final:

TODO: Au moins:

• parfois le au moins il suffit de faire comme si exactement et le reste est tout seul calculé.

Exemples:

• "au moins une lettre répétée" -> transformer en "aucune lettre répétée/toutes les lettres différents"

Choix successifs

• faire des choix un après l'autre
• attention: si combinaison successives avec prises d'éléments parmi les mêmes groupes (éléments peut être pris dans la comb de gauche, puis celle de droite) cela rajoute de l'ordre et donc des dupliqués !!!

Problème de trouver le terme constant dans un développement d'un binôme de Newton

Probabilités

Une fois qu'on sait faire des énumérations, on peut faire des probabilités en prenant le nombre de cas favorables/gagnants et en divisant par le nombre total de possibilités afin de calculer des probabilités.