n über k mit Induktion

27.10.2007, 12:22

kevin...

n über k mit Induktion

Hallo!

Zeige folgendes: Die Anzahl der k-elementigen Teilmengen einer beliebigen n-elementigen
Menge $\begin{eqnarray*} 0 \le k \le n \end{eqnarray*}$ sei gegeben durch $\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$

Wash heißt das genau?

27.10.2007, 12:25

therisen

Auf diesen Beitrag antworten »

Du wählst k aus n Elementen aus ohne Berücksichtigung der Reihenfolge. Dies ist z.B. beim Lotto "6 aus 49" der Fall.

27.10.2007, 12:32

kevin...

Auf diesen Beitrag antworten »

Zitat:

Original von therisen
Du wählst k aus n Elementen aus ohne Berücksichtigung der Reihenfolge. Dies ist z.B. beim Lotto "6 aus 49" der Fall.

Könntest du das wohl noch einmal genauer erklären?

27.10.2007, 12:42

therisen

Auf diesen Beitrag antworten »

$\begin{eqnarray*} n=3, k=2 \end{eqnarray*}$ :

$\begin{eqnarray*} \{1,2\} \end{eqnarray*}$
$\begin{eqnarray*} \{1,3\} \end{eqnarray*}$
$\begin{eqnarray*} \{2,3\} \end{eqnarray*}$

sind alle 2-elementigen Teilmengen der 3-elementigen Menge $\begin{eqnarray*} \{1,2,3\} \end{eqnarray*}$ .

27.10.2007, 13:01

kevin...

Auf diesen Beitrag antworten »

Gut. Das kann ich mir vorstellen. Jedoch wie/was beweise ich das/damit?

Brauche ich nicht noch eine Formel?

27.10.2007, 13:37

therisen

Auf diesen Beitrag antworten »

Du benötigst die Identität

$\begin{eqnarray*} {n+1\choose k}={n\choose k}+{n\choose k-1} \end{eqnarray*}$

um den Induktionsschritt zu schaffen (das Pluszeichen suggeriert bereits, dass du eine Fallunterscheidung vornehmen musst).

Neue Frage »

Antworten »

n über k mit Induktion

Verwandte Themen