Combien de chemins ?
Pour aller du coin haut-gauche au coin bas-droit d'une grille en n'allant que vers la droite ou vers le bas, il y a C(2n, n) chemins. Bouge le curseur et clique Nouveau chemin pour en voir un.
Nombre de chemins C(2n, n) = 20
🎯 C'est quoi la Combinatoire ?
La combinatoire, c'est l'art de compter sans compter. Au lieu de lister toutes les possibilités une par une (ce qui prendrait une éternité), on utilise des formules mathématiques pour calculer directement le nombre de cas possibles.
💡 La grande question à toujours se poser : "Est-ce que l'ORDRE compte ?"
→ Si oui : Permutation / Arrangement
→ Si non : Combinaison
Permutations (n!)
Définition : Combien de façons d'ordonner TOUS les éléments d'un ensemble ?
Exemple : 3 personnes sur un podium ?
3! = 3 × 2 × 1 = 6 arrangements
Arrangements A(n,k)
Définition : Combien de façons de choisir k éléments parmi n, en tenant compte de l'ordre ?
Exemple : Podium avec 3 places parmi 10 coureurs ?
A(10,3) = 10 × 9 × 8 = 720
Combinaisons C(n,k)
Définition : Combien de façons de choisir k éléments parmi n, sans tenir compte de l'ordre ?
Exemple : Choisir 3 joueurs parmi 10 pour une équipe ?
C(10,3) = 10!/(3!×7!) = 120
Avec Répétition
Définition : Quand on peut réutiliser les mêmes éléments.
Exemple : Code PIN à 4 chiffres (0-9) ?
10⁴ = 10 000 codes possibles
Le Studio du Dénombrement
Chaque formule de la fiche, jouée avec de vrais objets. Choisis un cas : les jetons se réordonnent et la formule se construit. Re-clique pour rejouer.
✖️ Le Principe Multiplicatif
C'est la base de tout ! Si tu as a façons de faire une chose, et b façons d'en faire une autre (indépendante), alors tu as a × b façons de faire les deux.
🍔 Menu burger
3 pains × 4 viandes × 2 sauces = 24 burgers
👕 Tenues
5 hauts × 4 pantalons × 3 chaussures = 60 tenues
🔺 Le Triangle de Pascal
Une façon visuelle de calculer les combinaisons. Chaque nombre est la somme des deux nombres au-dessus.
Lecture : Pour C(5,2), on regarde la ligne n=5, position k=2 (en partant de 0) → 10
Construis-le toi-même : chaque case naît de la somme des deux cases au-dessus. Touche une case pour lire son C(n,k).
Ligne n=0 : un seul chemin, C(0,0) = 1.
📋 Aide-Mémoire : Quelle formule utiliser ?
| Situation | Ordre ? | Répétition ? | Formule |
|---|---|---|---|
| Ranger n objets | Oui | Non | n! |
| Choisir k parmi n (podium) | Oui | Non | A(n,k) |
| Choisir k parmi n (équipe) | Non | Non | C(n,k) |
| Code PIN, mot de passe | Oui | Oui | n^k |
❗ La Factorielle (n!)
La factorielle est le produit de tous les entiers de 1 à n. Elle grandit extrêmement vite !
⚠️ Attention : 20! dépasse déjà 2 × 10¹⁸ ! C'est pour ça que les algorithmes "brute force" (qui testent toutes les permutations) sont souvent impossibles en pratique.
1. La Vitesse d'Exécution
Big O Notation
Imagine que tu cherches un livre dans une bibliothèque.
- O(1) Flash : Tu connais l'emplacement exact. Peu importe la taille de la bibliothèque, ça prend 1 seconde.
- O(n) Lecture : Tu dois lire tous les titres un par un. Si la bibliothèque double, ton temps double.
- O(n²) Le Cauchemar : Pour chaque livre, tu le compares à tous les autres (ex: trier à la main). Si la biblio double, le temps quadruple !
Applications Pro
-
Google Search
Google indexe des milliards de pages. Ils doivent utiliser des algos en O(log n) ou O(1). Si c'était O(n), chaque recherche prendrait des mois.
-
High Frequency Trading
En bourse, chaque microseconde compte. Un algorithme mal optimisé (O(n²)) perd de l'argent face à un algo optimisé.
⚡ Le Benchmark
Augmente le nombre de données (N) et regarde comment le temps de calcul explose.
2. L'Art du Dénombrement
La Question à 1 Million
"L'ordre compte-t-il ?"
OUI : ARRANGEMENTS / PERMUTATIONS
🔒 Code de cadenas : 1-2-3 est différent de 3-2-1.
La position est vitale.
NON : COMBINAISONS
🥗 Salade de fruits : Banane + Fraise, c'est pareil que Fraise + Banane.
C'est juste un groupe.
🔐 Brute Force Estimator
HACKING TOOLSLongueur du mot de passe (lettres minuscules uniquement) :
*Basé sur 1 milliard de tests/seconde
🎯 Mission : Lead Developer
Optimise le système et sécurise l'accès.