L'analyse combinatoireDie Kombinatorik
Compter sans énumérer. Combien de podiums, de mots de passe, de mains de cartes, de poignées de main ? Quatre formules suffisent, et deux questions les départagent : l'ordre compte-t-il, la répétition est-elle permise ? Tout le chapitre tient dans ce réflexe. Zählen ohne aufzuzählen. Wie viele Podeste, Passwörter, Kartenhände, Händedrucke? Vier Formeln genügen, und zwei Fragen entscheiden zwischen ihnen: zählt die Reihenfolge, ist Wiederholung erlaubt? Das ganze Kapitel steckt in diesem Reflex.
0Les symbolesDie Zeichen
Peu de signes, mais chacun encode une situation de comptage précise. Voici le dictionnaire.
Wenige Zeichen, aber jedes kodiert eine präzise Zählsituation. Hier ist das Wörterbuch.
| Symbole | Français | Deutsch |
|---|---|---|
| n! | « Factorielle n » : le produit 1 · 2 · 3 ⋯ n. Le nombre de façons d'ordonner n objets distincts. | «n Fakultät»: das Produkt 1 · 2 · 3 ⋯ n. Die Anzahl Arten, n verschiedene Objekte anzuordnen. |
| 0! = 1 | Une convention indispensable : il y a exactement une façon d'ordonner zéro objet, ne rien faire. | Eine unentbehrliche Konvention: es gibt genau eine Art, null Objekte anzuordnen, nämlich nichts zu tun. |
| Pₙ | Les permutations de n objets : Pₙ = n!. Tous les objets, chacun une fois, l'ordre compte. | Die Permutationen von n Objekten: Pₙ = n!. Alle Objekte, jedes einmal, die Reihenfolge zählt. |
| Aₙᵏ | Les arrangements : k objets tirés parmi n, sans remise, en tenant compte de l'ordre. | Die Variationen: k aus n Objekten, ohne Zurücklegen, mit Beachtung der Reihenfolge. |
| Cₙᵏ | Les combinaisons : k objets choisis parmi n, sans remise, sans ordre. Se lit aussi « n choisir k ». | Die Kombinationen: k aus n Objekten gewählt, ohne Zurücklegen, ohne Reihenfolge. Auch «n über k» gelesen. |
| (ⁿₖ) | Le coefficient binomial : la même chose que Cₙᵏ, en habit de matrice. C'est lui qui peuple le triangle de Pascal. | Der Binomialkoeffizient: dasselbe wie Cₙᵏ, im Matrixgewand. Er bevölkert das Pascalsche Dreieck. |
| nᵏ | Les tirages avec remise et avec ordre : k choix successifs parmi n possibilités à chaque fois. | Die Ziehungen mit Zurücklegen und mit Reihenfolge: k aufeinanderfolgende Wahlen aus jeweils n Möglichkeiten. |
| · | Le principe multiplicatif : des étapes successives se multiplient. Le grand moteur silencieux du chapitre. | Das Produktprinzip: aufeinanderfolgende Schritte multiplizieren sich. Der grosse stille Motor des Kapitels. |
| + | Le principe additif : des cas qui s'excluent s'additionnent. Valable seulement sans recouvrement. | Das Summenprinzip: einander ausschliessende Fälle addieren sich. Nur ohne Überschneidung gültig. |
| (a + b)ⁿ | Le binôme de Newton : son développement est écrit d'avance par les coefficients binomiaux. | Der binomische Lehrsatz: seine Entwicklung ist durch die Binomialkoeffizienten vorgeschrieben. |
1Les deux principesDie zwei Prinzipien
Toutes les formules du chapitre se fabriquent avec deux gestes élémentaires : multiplier des étapes, additionner des cas.
Alle Formeln des Kapitels entstehen aus zwei elementaren Handgriffen: Schritte multiplizieren, Fälle addieren.
1.1 · Multiplier les étapesSchritte multiplizieren
Quand une expérience se déroule en étapes successives et indépendantes dans leur nombre de choix, le total est le produit des choix de chaque étape.
Verläuft ein Experiment in aufeinanderfolgenden Schritten, deren Wahlanzahl unabhängig ist, so ist das Total das Produkt der Wahlen jedes Schrittes.
Parce que chaque issue de la première étape ouvre le même éventail à la seconde : l'arbre a m branches, chacune se ramifie en n. Compter les feuilles, c'est multiplier.
Le nombre de choix doit être le même à chaque branche ; les choix eux-mêmes peuvent différer.
Weil jedes Ergebnis des ersten Schrittes denselben Fächer im zweiten öffnet: der Baum hat m Äste, jeder verzweigt sich in n. Die Blätter zählen heisst multiplizieren.
Die Anzahl der Wahlen muss an jedem Ast gleich sein; die Wahlen selbst dürfen sich unterscheiden.
1.2 · Additionner les casFälle addieren
Quand les issues se répartissent en familles qui ne se chevauchent pas, on compte chaque famille et on additionne.
Verteilen sich die Ergebnisse auf Familien, die sich nicht überschneiden, so zählt man jede Familie und addiert.
2Factorielle et permutationsFakultät und Permutationen
2.1 · n! et les permutationsn! und die Permutationen
Ordonner n objets distincts, c'est remplir n places : n choix pour la première, n − 1 pour la deuxième, et ainsi de suite jusqu'à 1.
Le principe multiplicatif fait le reste : n · (n − 1) ⋯ 1 = n!.
n verschiedene Objekte anzuordnen heisst, n Plätze zu füllen: n Wahlen für den ersten, n − 1 für den zweiten, und so weiter bis 1.
Das Produktprinzip erledigt den Rest: n · (n − 1) ⋯ 1 = n!.
Pourquoi 0! = 1 et non 0 ? Parce qu'un produit vide vaut 1, comme une somme vide vaut 0. Et parce que les formules l'exigent : Cₙⁿ = n!/(n! · 0!) doit valoir 1, il n'y a qu'une façon de tout prendre.
La factorielle explose vite : 10! fait déjà 3'628'800, et 20! dépasse les capacités d'une calculatrice ordinaire. C'est le signe qu'énumérer est sans espoir, et que les formules servent à quelque chose.
Warum 0! = 1 und nicht 0? Weil ein leeres Produkt 1 ergibt, wie eine leere Summe 0. Und weil die Formeln es verlangen: Cₙⁿ = n!/(n! · 0!) muss 1 sein, es gibt nur eine Art, alles zu nehmen.
Die Fakultät explodiert schnell: 10! macht bereits 3'628'800, und 20! übersteigt einen gewöhnlichen Taschenrechner. Das ist das Zeichen, dass Aufzählen hoffnungslos ist und die Formeln etwas taugen.
2.2 · Les anagrammes : permutations avec répétitionsDie Anagramme: Permutationen mit Wiederholung
Quand des objets sont indiscernables entre eux (les trois A d'ANANAS), permuter ces jumeaux ne change rien.
On compte donc n! comme si tout était distinct, puis on divise par les k! de chaque groupe de jumeaux.
Wenn Objekte untereinander ununterscheidbar sind (die drei A von ANANAS), ändert das Vertauschen dieser Zwillinge nichts.
Man zählt also n!, als wäre alles verschieden, und teilt dann durch die k! jeder Zwillingsgruppe.
Le laboratoire compte les anagrammes de n'importe quel mot : il regroupe les lettres, écrit la division et, quand la liste reste courte, énumère les anagrammes pour de vrai.
Das Labor zählt die Anagramme eines beliebigen Wortes: es gruppiert die Buchstaben, schreibt die Division hin und zählt die Anagramme, wenn die Liste kurz bleibt, tatsächlich auf.
3Les arrangementsDie Variationen
Un arrangement, c'est un tirage ordonné : k places à remplir avec des objets pris parmi n.
Sans remise, l'éventail rétrécit à chaque place : n, puis n − 1, jusqu'à n − k + 1. Avec remise, il reste n à chaque place : nᵏ.
Eine Variation ist eine geordnete Ziehung: k Plätze, gefüllt mit Objekten aus n.
Ohne Zurücklegen schrumpft der Fächer mit jedem Platz: n, dann n − 1, bis n − k + 1. Mit Zurücklegen bleibt er bei n pro Platz: nᵏ.
En pratique, on n'utilise presque jamais la forme n!/(n − k)! : on écrit directement le produit décroissant, k facteurs à partir de n.
A₁₀³ : trois facteurs à partir de 10, soit 10 · 9 · 8. Fini avant d'avoir sorti la calculatrice.
In der Praxis benutzt man die Form n!/(n − k)! fast nie: man schreibt direkt das fallende Produkt, k Faktoren ab n.
A₁₀³: drei Faktoren ab 10, also 10 · 9 · 8. Fertig, bevor der Taschenrechner draussen ist.
4Les combinaisonsDie Kombinationen
Une combinaison, c'est un tirage sans ordre : on choisit un paquet de k objets parmi n, et le paquet n'a pas de première place.
On part de l'arrangement Aₙᵏ, puis on divise par k! : chaque paquet y était compté une fois par ordre possible.
Eine Kombination ist eine ungeordnete Ziehung: man wählt ein Paket von k Objekten aus n, und das Paket hat keinen ersten Platz.
Man geht von der Variation Aₙᵏ aus und teilt durch k!: jedes Paket war dort einmal pro möglicher Reihenfolge gezählt.
Choisir les k objets que l'on prend, c'est exactement choisir les n − k que l'on laisse. Deux descriptions du même geste, donc le même nombre.
C'est l'argument type du chapitre : compter la même chose de deux façons. Aucun calcul, et la formule tombe.
Die k Objekte wählen, die man nimmt, heisst genau die n − k wählen, die man liegen lässt. Zwei Beschreibungen derselben Handlung, also dieselbe Zahl.
Das ist das Musterargument des Kapitels: dasselbe auf zwei Arten zählen. Keine Rechnung, und die Formel fällt heraus.
Fixez un objet vedette parmi les n. Chaque choix de k objets ou bien le contient (reste k − 1 à prendre parmi n − 1), ou bien l'ignore (reste k à prendre parmi n − 1).
Deux cas disjoints, principe additif : la formule de Pascal. C'est elle qui engendre le triangle du laboratoire suivant.
Fixieren Sie ein Sternobjekt unter den n. Jede Wahl von k Objekten enthält es entweder (bleiben k − 1 aus n − 1) oder ignoriert es (bleiben k aus n − 1).
Zwei disjunkte Fälle, Summenprinzip: die Pascalsche Formel. Sie erzeugt das Dreieck im nächsten Labor.
5La fabrique de tiragesDie Ziehungsfabrik
Les quatre formules côte à côte, sur de vrais objets. Choisissez n, k et le mode de tirage : la machine écrit la formule, donne le total, et énumère les tirages eux-mêmes tant qu'ils tiennent à l'écran.
Comparez les quatre modes à n et k fixés : mêmes lettres, quatre mondes différents. Et regardez ABC et BCA fusionner quand l'ordre cesse de compter.
Die vier Formeln nebeneinander, an echten Objekten. Wählen Sie n, k und den Ziehungsmodus: die Maschine schreibt die Formel, gibt das Total und zählt die Ziehungen selbst auf, solange sie auf den Bildschirm passen.
Vergleichen Sie die vier Modi bei festem n und k: dieselben Buchstaben, vier verschiedene Welten. Und sehen Sie zu, wie ABC und BCA verschmelzen, sobald die Reihenfolge nicht mehr zählt.
6Le triangle de Pascal et le binômeDas Pascalsche Dreieck und der Binom
Rangez les Cₙᵏ en pyramide : chaque case est la somme des deux cases au-dessus d'elle, c'est la formule de Pascal devenue image. Cliquez une case : ses deux parents s'allument, ainsi que sa jumelle symétrique.
Ordnen Sie die Cₙᵏ als Pyramide: jedes Feld ist die Summe der beiden Felder darüber, die Pascalsche Formel als Bild. Klicken Sie ein Feld: seine beiden Eltern leuchten auf, ebenso sein symmetrischer Zwilling.
Développer (a + b)ⁿ, c'est distribuer n parenthèses : chaque terme du résultat choisit a ou b dans chacune. Un terme aⁿ⁻ᵏbᵏ apparaît autant de fois qu'il y a de façons de choisir les k parenthèses qui donnent b.
Ce nombre est Cₙᵏ. Le binôme n'est pas une formule d'algèbre avec un peu de combinatoire : c'est de la combinatoire pure. Et la ligne n du triangle donne 2ⁿ en posant a = b = 1 : le nombre de sous-ensembles d'un ensemble à n éléments.
(a + b)ⁿ zu entwickeln heisst, n Klammern auszumultiplizieren: jeder Term des Ergebnisses wählt in jeder Klammer a oder b. Ein Term aⁿ⁻ᵏbᵏ erscheint so oft, wie man die k Klammern wählen kann, die b liefern.
Diese Zahl ist Cₙᵏ. Der binomische Lehrsatz ist keine Algebraformel mit etwas Kombinatorik: er ist reine Kombinatorik. Und die Zeile n des Dreiecks ergibt mit a = b = 1 gerade 2ⁿ: die Anzahl Teilmengen einer n-elementigen Menge.
7La méthodeDie Methode
Le réflexe central tient dans un carré à deux questions. Il choisit la formule à votre place.
Der zentrale Reflex passt in ein Quadrat mit zwei Fragen. Es wählt die Formel an Ihrer Stelle.
8Les six erreursDie sechs Fehler
9Se testerSich prüfen
Huit questions, une seule bonne réponse à chaque fois. L'explication tombe après votre choix.
Acht Fragen, jeweils genau eine richtige Antwort. Die Erklärung erscheint nach Ihrer Wahl.
10Lexique FR/DEWortschatz FR/DE
| Français | Deutsch |
|---|---|
| l'analyse combinatoire / le dénombrement | die Kombinatorik / das Abzählen |
| la factorielle | die Fakultät |
| la permutation | die Permutation |
| l'arrangement | die Variation |
| la combinaison | die Kombination |
| le coefficient binomial | der Binomialkoeffizient |
| « n choisir k » | «n über k» |
| avec / sans répétition | mit / ohne Wiederholung |
| avec / sans remise | mit / ohne Zurücklegen |
| l'ordre compte | die Reihenfolge zählt |
| le principe multiplicatif | das Produktprinzip |
| le principe additif | das Summenprinzip |
| des cas disjoints | disjunkte Fälle |
| le complémentaire | das Komplement |
| l'anagramme | das Anagramm |
| indiscernable | ununterscheidbar |
| le triangle de Pascal | das Pascalsche Dreieck |
| la formule de Pascal | die Pascalsche Formel |
| le binôme de Newton | der binomische Lehrsatz |
| le développement | die Entwicklung |
| le sous-ensemble | die Teilmenge |
| l'arbre de dénombrement | das Zählbaumdiagramm |
| énumérer | aufzählen |
| le tirage | die Ziehung |