Produktregel der Kombinatorik

Auswahlmöglichkeiten an mehreren Stellen zählen

Die $Produktregel$ zählt vollständige Ergebnisse, indem sie $die Anzahl der gültigen Möglichkeiten$ bei jedem aufeinanderfolgenden Schritt multipliziert. Sie gilt, wenn jedes Ergebnis durch eine feste Folge von Entscheidungen entsteht.

Ein Formular mit mehreren Feldern folgt demselben Muster. Jedes Feld ist eine Stelle und jeder zulässige Eintrag eine Möglichkeit. Das Produkt dieser Anzahlen ergibt die Zahl der gültigen vollständig ausgefüllten Formulare.

Auswahlmöglichkeiten in einer Tabelle auflisten

Die Tabellenmethode listet $jede Kombination$ auf. Die Zeilen stehen für Möglichkeiten aus einer Kategorie und die Spalten für Möglichkeiten aus einer anderen.

Ein Schüler möchte ein Online-Lernpaket auswählen. Es gibt drei Plattformen (Plattform A, Plattform B, Plattform C) und vier Fächer (Mathematik, Physik, Chemie, Biologie).

Die Tabelle enthält alle möglichen Kombinationen:

Plattform	Mathematik	Physik	Chemie	Biologie
Plattform A	A-Mathe	A-Phys	A-Chem	A-Bio
Plattform B	B-Mathe	B-Phys	B-Chem	B-Bio
Plattform C	C-Mathe	C-Phys	C-Chem	C-Bio

\begin{aligned} \text{Gesamtkombinationen} &= 3 \times 4 \\ &= 12 \text{ Wege} \end{aligned}

Auswahl in einem Baumdiagramm

In einem $Baumdiagramm$ steht jeder Zweig für eine Auswahl. Ein vollständiger Pfad vom Startpunkt bis zu einem Endpunkt entspricht einem vollständigen Ergebnis.

Für dasselbe Lernpaket wählen die ersten Zweige die Plattform und die nächsten Zweige das Fach.

Zwei Auswahlstufen für das Lernpaket

Von jeder Plattform gehen vier Fachzweige aus. Damit wählt $jeder vollständige Pfad$ genau eine Plattform und ein Fach. Der Pfad Start → Plattform A → Physik bedeutet zum Beispiel Plattform A für Physik.

3 \times 4 = 12

Zählen mit der Produktregel

Die $Produktregel$ liefert dieselbe Anzahl, ohne jedes Ergebnis einzeln aufzulisten. Gibt es $n$ Stellen und hat Stelle $i$ genau $k_i$ gültige Möglichkeiten, dann ist die Anzahl der vollständigen Ergebnisse:

\begin{aligned} &\text{Anzahl der Ergebnisse} \\ &= k_1 \times k_2 \times k_3 \times \cdots \times k_n \end{aligned}

Für die erste Stelle ist die Anzahl der Möglichkeiten fest. Für jede weitere Stelle muss diese Anzahl $bei jeder zulässigen bisherigen Auswahl gleich sein$ , auch wenn andere Möglichkeiten übrig bleiben. Unterscheiden sich die Anzahlen der Zweige, zählst du die Zweiggruppen getrennt und addierst sie.

Zugangscodes zählen

Eine Schule möchte Zugangscodes für digitale Lernsysteme erstellen. Der Code hat $drei aufeinanderfolgende Stellen$ :

Erste Stelle: $3 \text{ Buchstaben}$ ( $A, B, C$ )
Zweite Stelle: $5 \text{ Ziffern}$ ( $1, 2, 3, 4, 5$ )
Dritte Stelle: $2 \text{ Symbole}$ ( $@, \#$ )

Wir multiplizieren die Möglichkeiten der drei Stellen:

k_1 = 3 \text{(Buchstabenauswahl)}

Fälle mit Einschränkungen

Einschränkungen können die Zahl der Möglichkeiten von einer Stelle zur nächsten verändern. Prüfe für jede Stelle, ob eine $frühere Wahl$ eine Option entfernt, denn davon hängt ab, ob die Faktoren gleich bleiben. Die Beispiele unten rechnen beide Fälle durch.

Wiederholung nicht erlaubt

Wenn dasselbe Objekt $nicht wiederholt verwendet werden darf$ , verringert jede besetzte Stelle die Auswahl für die nächste Stelle.

$Beispiel$ : Bildung einer $3\text{-stelligen}$ Zahl aus den Ziffern $2, 3, 4, 5, 6$ ohne Wiederholung.

Für die erste Stelle gibt es $5$ Möglichkeiten. Ist $1$ Ziffer verwendet, bleiben $4$ Möglichkeiten für die zweite Stelle. Nach $2$ verwendeten Ziffern gibt es für die dritte Stelle noch $3$ Möglichkeiten.

\begin{aligned} \text{Gesamtzahlen} &= 5 \times 4 \times 3 \\ &= 60 \text{ Zahlen} \end{aligned}

Wiederholung erlaubt

Wenn dasselbe Objekt $wiederholt verwendet werden darf$ , bleibt die Zahl der Möglichkeiten an jeder Stelle gleich.

Für den gleichen Fall mit erlaubter Wiederholung:

\text{Jede Stelle} = 5 \text{ Möglichkeiten}

Übungen

Jede Aufgabe besetzt mehrere Plätze nacheinander. Zähle die Möglichkeiten für einen Platz, multipliziere sie und achte auf die Aufgabe $ohne Wiederholung$ .

Ein Elektronikgeschäft verkauft Smartphones von $4$ Marken. Jede Marke ist mit $3$ Speicherkapazitäten und in $5$ Farben erhältlich. Wie viele verschiedene Ausführungen gibt es?
Ein Passwort besteht aus $1$ Buchstaben und danach $2$ Ziffern. Der Buchstabe wird aus A, B, C, D gewählt, die Ziffern ohne Wiederholung aus $\{1, 2, 3, 4, 5\}$ . Wie viele Passwörter sind möglich?
Eine Fahrt von Stadt $P$ nach Stadt $R$ führt über Stadt $Q$ . Von $P$ nach $Q$ gibt es $3$ Straßen und von $Q$ nach $R$ gibt es $4$ Straßen. Wie viele verschiedene Routen sind möglich?
Ein Kennzeichen besteht aus $2$ Buchstaben und danach $3$ Ziffern. Es stehen $26$ Buchstaben und die $10$ Ziffern $0\text{-}9$ zur Verfügung. Wiederholungen sind erlaubt. Wie viele Kennzeichen sind möglich?

Lösungen

$Aufgabe 1$ . Jede Marke lässt sich mit jeder Speicherkapazität und Farbe kombinieren. Deshalb werden die $Anzahlen der Wahlmöglichkeiten multipliziert$ .

Gegeben: $4 \text{ Marken}$ , $3 \text{ Speicherkapazitäten}$ , $5 \text{ Farbauswahl}$

Die Anzahl der Smartphone-Kombinationen beträgt:

4\times3\times5=60

$Aufgabe 2$

Gegeben: $1 \text{ Buchstabe}$ aus $\{A, B, C, D\}$ , $2 \text{ Ziffern}$ aus $\{1, 2, 3, 4, 5\}$ ohne Wiederholung

Für den Buchstaben gibt es $4$ Möglichkeiten und für die erste Ziffer $5$ . Da sich die Ziffern $nicht wiederholen dürfen$ , bleiben für die zweite Ziffer $4$ Möglichkeiten.

\begin{aligned} &\text{Gesamtzahl der Passwörter} \\ &= 4 \times 5 \times 4 \\ &= 80 \text{ Passwörter} \end{aligned}

$Aufgabe 3$ . Auf jede Straße im ersten Abschnitt kann jede Straße im zweiten Abschnitt folgen. Mit der $Produktregel$ zählen wir die vollständigen Routen.

Gegeben: $3 \text{ Straßen}$ von $P$ bis $Q$ , $4 \text{ Straßen}$ von $Q$ bis $R$

\begin{aligned} &\text{Gesamtrouten} \\ &= 3 \times 4 \\ &= 12 \text{ verschiedene Routen} \end{aligned}

$Aufgabe 4$

Gegeben: $2 \text{ Buchstaben}$ aus $26 \text{ Buchstaben}$ , $3 \text{ Ziffern}$ aus $10 \text{ Ziffern}$ , $Wiederholung erlaubt$

\begin{aligned} &\text{Auswahl des ersten Buchstabens} \\ &= 26 \end{aligned}

Für den zweiten Buchstaben gibt es $26$ Möglichkeiten.

\text{Möglichkeiten für jede Ziffer} = 10

Damit ergibt sich folgende Gesamtzahl an Nummernschildern:

\begin{aligned}26\times26\times10\times10\times10 &=676\times1000\\ &=676000\text{ Nummernschilder}\end{aligned}